Sorting
Table of contents
Selection Sort
block-beta
columns 10
block:group1:1
0 1 2
end
block:group2:3
5 9 3 4 6 8 7
end
3 --> 5
style group1 fill:#fee,stroke:#333,stroke-width:2px
style group2 fill:#fff,stroke:#333,stroke-width:1px,stroke-dasharray: 5, 5
Find the smallest element in the array and swap it with the first element.
If we have $n$ elements, the first loop only needs to go up to $n-1$, because the last one is already in place.
To find the smallest element index, you could use another loop, etc.
#include <vector>
#include <algorithm>
using namespace std;
void SelectionSort(vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int i = 0; i < n - 1; ++i) {
auto it = arr.begin() + i;
auto min_it = min_element(it, arr.end()); // or additional loop j: i to n
swap(*it, *min_it); // or iter_swap(it, min_it);
}
}
Complexity is $O(n^2)$.
Insertion Sort
block-beta
columns 10
block:group1:1
0 1 5
end
block:group2:3
2 9 3 4 6 8 7
end
2 --> 1
style group1 fill:#fee,stroke:#333,stroke-width:2px
style group2 fill:#fff,stroke:#333,stroke-width:1px,stroke-dasharray: 5, 5
Left side of the array is already sorted. Insert the next unsorted element into the sorted part at the correct position.
Each iteration results in inserting (hence the name) one more element to the sorted part.
The actual insertion is carried out by swapping elements to the left until the correct position is found.
I like to think of it as swap-to-the-left sort, because technically, that’s what we’re doing.
The loop starts at index 1, because a single element is always sorted.
void InsertionSort(vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
else break;
}
}
}
Complexity is $O(n^2)$. Usually a bit slower than selection sort, but faster for partially (almost) sorted arrays.
Bubble Sort
block-beta
columns 10
block:group2:3
6 2 1 5 3 4 0
end
block:group1:1
7 8 9
end
2 --> 6
1 --> 2
5 --> 1
3 --> 5
4 --> 3
0 --> 4
style group1 fill:#fee,stroke:#333,stroke-width:2px
style group2 fill:#fff,stroke:#333,stroke-width:1px,stroke-dasharray: 5, 5
Somewhat similar to insertion sort, but instead of swapping to insert an element at the front, you’re swapping adjacent elements such that the largest element ends up at the end.
The algorithm simply swaps adjacent elements. The largest elements ending up at the right is the result of the swap.
void BubbleSort(vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int j = n - 1; j > 0; --j) {
for (int i = 0; i < j; ++i) {
if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
}
}
}
Complexity is $O(n^2)$.
Merge Sort
block-beta
columns 10
block:group1:2
0 1 5 6 7
end
block:group2:2
2 3 4 8 9
end
style group1 fill:#fee,stroke:#333,stroke-width:2px
style group2 fill:#fee,stroke:#333,stroke-width:2px
Recursively divide the array into two halves, sort each half, and merge them back together.
Top-Level Merge Sort Function
Just like many recursive algorithms, we need a top-level function that will call the recursive helper.
void MergeSort(vector<int>& arr) {
int n = static_cast<int>(arr.size());
MergeSortHelper(arr, 0, n - 1);
}
Recursive Merge Sort Helper
Merge sort helper takes the full array and the inclusive range indices as the argument.
The functions is basically saying:
- “Sort the array elements in range
[l, r]in place”.
And the way we’re going to achieve this is by:
- Divide
[l, r]into two halves - Sort each half
- Merge the two sorted halves
void MergeSortHelper(vector<int>& arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
MergeSortHelper(arr, l, mid);
MergeSortHelper(arr, mid + 1, r);
Merge(arr, l, mid, r); // Up next
}
Merge Function
This part is straightforward.
In C++, you could just use the merge/inplace_merge function from the <algorithm> library:
Keep in mind that merge and inplace_merge expects ranges to be [begin, middle) and [middle, end).
auto l_it = arr.begin() + l;
auto m_it = arr.begin() + mid + 1; // Note the +1
auto r_it = arr.begin() + r + 1; // Note the +1
inplace_merge(l_it, m_it, r_it);
Or you could implement it yourself:
#include <cassert>
void Merge(vector<int>& arr, int l, int mid, int r) {
vector<int> sub1(arr.begin() + l, arr.begin() + mid + 1);
vector<int> sub2(arr.begin() + mid + 1, arr.begin() + r + 1);
int n1 = static_cast<int>(sub1.size());
int n2 = static_cast<int>(sub2.size());
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (sub1[i] <= sub2[j]) arr[k++] = sub1[i++];
else arr[k++] = sub2[j++];
}
// Take care of leftovers, if any
while (i < n1) arr[k++] = sub1[i++];
while (j < n2) arr[k++] = sub2[j++];
assert(k == r + 1);
}