Sorting Algorithms

June 16, 2019

Understanding sorting algorithms is a must for software engineers. This topic is also common in a programming interview. There is a lot of sorting algorithms out there, and I want to cover some of them here. I also gave some examples in C.

Selection Sort

Select and compare an element with other elements at each iteration. The complexity of Selection Sort is O(n²).

void selection_sort(int *list, int length) {
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            if (list[i] > list[j]) {
                int tmp = list[i];
                list[i] = list[j];
                list[j] = tmp;
            }
        }
    }
}

Bubble Sort

Select and compare an element with its neighbor then swap if it is not in order. The complexity of Bubble Sort is O(n²).

void bubble_sort(int *list, int length) {
    for (int i = 0; i < length - 1; i++) {
        int swap = 0;
    
        for (int j = 0; j < length - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                int tmp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = tmp;
                swap = 1;
            }
        }
    
        if (!swap) break;
    }
}

Insertion Sort

Similar to Bubble Sort. It inserts the next element into the sorted sublist. The complexity of Insertion Sort is O(n²).

void insertion_sort(int *list, int length) {
    for (int i = 1; i < length; i++) {
        int element = list[i];
        int j = i - 1;
    
        while (j >= 0 && list[j] > element) {
            list[j + 1] = list[j];
            j--;
        }
    
        list[j + 1] = element;
    }
}

Shell Sort

Shell Sort partitions the list into sublists where a sublist is elements that are separated by a gap. The gap keeps reducing the value until it becomes one. Each sublist is sorted using Insertion Sort. The complexity of Shell Sort is O(n²).

void shell_sort(int *list, int length) {
    for (int gap = length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < length; i++) {
            int tmp = list[i];
            int j;
        
            for (j = i; j >= gap && list[j - gap] > tmp; j -= gap) {
                list[j] = list[j - gap];
            }
        
            list[j] = tmp;
        }
    }
}

Merge Sort

Merge Sort is a Divide and Conquer algorithm. Divide the unsorted list into sublists then repeatedly merge sublists to produce new sorted list. The complexity of Merge Sort is O(n log n).

void merge(int *list, int left, int mid, int right) {
    int l, r, m;
    int left_n = mid - left + 1;
    int right_n = right - mid;
    int left_list[left_n], right_list[right_n];

    for (int l = 0; l < left_n; l++) {
        left_list[l] = list[left + l];
    }

    for (int r = 0; r < right_n; r++) {
        right_list[r] = list[mid + 1 + r];
    }

    l = 0;
    r = 0;
    m = left;

    while (l < left_n && r < right_n) {
        if (left_list[l] <= right_list[r]) {
            list[m] = left_list[l];
            l++;
        } else { 
            list[m] = right_list[r];
            r++;
        }

        m++;
    }
    
    while (l < left_n) {
        list[m] = left_list[l];
        l++;
        m++;
    }

    while (r < right_n) {
        list[m] = right_list[r];
        r++;
        m++;
    }
}
    
void merge_sort(int *list, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        merge_sort(list, left, mid);
        merge_sort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

Quick Sort

Quick Sort is similar to Merge Sort. It is a Divide and Conquer algorithm. It partitions the list at every step based on a pivot. The complexity of Quick Sort is O(n log n).

int partition(int *list, int low, int high) {
    int pivot = list[high];
    int i = (low - 1);
    int tmp;
    
    for (int l = low; l <= high - 1;l++) {
        if (list[l] <= pivot) {
            i++;
        
            tmp = list[i];
            list[i] = list[l];
            list[l] = tmp;
        }
    }
    
    tmp = list[i + 1];
    list[i + 1] = list[high];
    list[high] = tmp;
    
    return i + 1;
}
    
void quick_sort(int *list, int low, int high) {
    if (low < high) {
        int part = partition(list, low, high);
    
        quick_sort(list, low, part - 1);
        quick_sort(list, part + 1, high);
    }
}

Conclusion

It is also important to understand Big-O notation, to understand the time complexity of an algorithm. Most of them are O(n²). But some recursive sorts such as Merge and Quick Sort have O(n log n). There is still a lot of sorting algorithms that I didn't cover here. But these are the famous ones.

There is a question that asks you to sort in some programming interview. Whatever the sorting algorithm that you choose is up to you. I prefer the Insertion or Merge Sort.

References

Most of the resources I got are from Wikipedia and GeeksforGeeks.org. I wrote my C codes on repl.it.