# 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(n2).

```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(n2).

```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(n2).

```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(n2).

```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(n2). 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.