Index:
1. Insertion Sort
2. Quicksort
3. Merge Sort
4. Heapsort
5. Bubble Sort
6. Counting Sort
Time Complexity Table
1. Insertion Sort
For an array arr[0:n], sort arr[0:i] from i = 1 to i = n. For each arr[i], insert it into the correct position by comparing it with all the previous elements which are sorted.
Insertion Sort in C++
void insertionSort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
2. Quicksort
Quicksort is a recursive algorithm that partitions the array arr[0:n] into two subarrays by choosing a pivot element and placing all elements less than or equal to it before it and all elements greater than it after it. Recursively performing the same procedure for subarrays until the whole array is sorted.
Quicksort in C++
int partition(int arr[], int p, int r) {
int x = arr[r];
int i = p - 1;
for (int j = p; j <= r - 1; j++) {
if (arr[j] <= x) {
i++;
int key = arr[i];
arr[i] = arr[j];
arr[j] = key;
}
}
int key = arr[i+1];
arr[i + 1] = arr[r];
arr[r] = key;
return i + 1;
}
void quickSort(int arr[], int p, int r) {
if (p < r) {
int q = partition(arr, p, r);
quickSort(arr, p, q - 1);
quickSort(arr, q + 1, r);
}
}
3. Merge Sort
Merge sort algorithm halves the array recursively until the array is broken up into single elements, then merges them back to the full array. During the merging process, the elements are joined in order such that every merged subarray is sorted.
Merge Sort in C++
4. Heap Sort
Refer to the post Elementary Data Structures – section x.x for more information.
Algorithm | Average | Worst-case | Best-case |
Insertion Sort | O(n2) | O(n2) | O(n) |
Quick Sort | O(n log n) | O(n2) | O(n log n) |