# Sorting Algorithms

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^{2}).

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^{2}).

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^{2}).

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^{2}).

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^{2}). 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.