The Angry Birds
The angry birds, or more specifically, the sorting algorithms.
This series of articles inspired by Algorithms, Part I course from Princeton University & Algorithms, 4th Edition. The full series of articles can be found here.
Sorting is important in programming for the same reason it’s important in our daily life. It is easier and faster to locate items in a sorted list than unsorted, or, It might be necessary to traverse the items in order.
Thus, sorting algorithms can be used in a program to sort an array for later searching or displaying the items in order.
Animations
Before moving on, you can visualize the sorting algorithms, and see how it works at the following link. Use it while following along.
Selection Sort
The idea is to select the smallest value in the array, and swap it with the leftmost unsorted element. In each iteration, we start from the leftmost unsorted element, ignoring all the values that are already sorted on the left.
This way, it divides the array into two parts; part of elements already sorted on the left, and another part contains the elements on the right remaining to be sorted.
Implementation
for (int i = 0; i < N; i++) {
int min = i; // Iterate through all entries starting from i.
for (int j = i+1; j < N; j++) { // Find index min; the index with the smallest value.
if (less(a[j], a[min])) min = j;
} // Swap a[i] with a[min].
swap(a, i, min);
}
Conditions
The selection sort algorithm states that at the end of each loop, elements on left of a[i](including a[i]) are in ascending order, and no elements on right of a[i] is smaller than elements on the left of a[i](including a[i]).
Analysis
Time → It takes (N-1) + (N-2) + … + 0 = N * (N-1 /2) ~ (N² /2). This means it has a complexity of O(N²). It always use O(N²) even if the array is sorted.
It takes N number of swaps, and therefore minimal number of data movements.
Memory →It’s an in-place comparison sort; no additional arrays needed for data to be temporarily stored, as in other sorting algorithms.
An algorithm is sorting in-place when it uses ≤ c LogN extra memory.
Insertion Sort
It divides the array in to two parts, same as selection sort. In each iteration, it picks up the leftmost unsorted element, and finds the location it belongs within the sorted part on the left, and inserts it there.
Implementation
for (int i = 0; i < N; i++) { // Iterate through elements from right to left
for (int j = i; j > 0; j--) { // Swap a[j] with a[j-1] as long as a[j] < a[j-1]
// Otherwise, break.
if(less(a[j], a[j-1])) swap(a, j, j-1);
else break;
}
}
Another Implementation — Less Number of Exchanges
for (int i = 0; i < N; i++){
// Store leftmost unsorted element in a temporary variable
int temp = a[i];
int j = i;
for(; j > 0; j--){ // Assign a[j] to a[j-1] as long as temp < a[j-1]
// Otherwise, break.
if(a[j - 1] > temp) a[j] = a[j - 1];
else break;
} // Insert the element in it's sorted position
a[j] = temp;
}
Conditions
The insertion sort algorithm states that at the end of each loop, elements on left of a[i](including a[i]) are in ascending order, and elements on right of a[i] haven’t been checked yet.
Analysis
Time → It’s more complicated to compute because it depends on the elements order; if they are random or not.
- It takes ~ (1/4 N²) in average case, if randomly ordered array with distinct keys. So, it’s twice faster than the selection sort in average.
- It takes ~ (1/2 N²) in worst case, if they are in descending order.
- It takes (N-1) in best case, if the data is sorted. So, it will just take N-1 compares and 0 swaps.
Memory →It’s an in-place comparison sort same as selection sort.
Partially Sorted
Maybe you’ve noticed that insertion sort performs well if the array is almost sorted, and Yes, It’s efficient in case of partially sorted array.
We define that an array is partially sorted when each element is no more than some constant k places away from its sorted position, and thus, it takes linear time; the time complexity is O(kN).
Bubble Sort Vs Insertion Sort
In Bubble sort , it divides the array in to two parts, same as insertion sort. In each iteration, it starts with the first element in the left part, swaps every two adjacent elements as long as the a[j] is less than a[j-1], ignoring all the values that are already sorted on the right.
It repeats until no elements remain to be sorted on the left, which indicates that the array is sorted.
The bottom line is, In Insertion sort, elements are compared with the sorted section, while in bubble sort, they are compared with the unsorted section.
That’s why Insertion sort is faster, and, if the array is partially sorted, it will perform better.
Bubble sort has worst-case and average complexity both О(N²), and when the list is already sorted (best-case), the complexity of bubble sort is only O(N).
Shell Sort
Some of you may have noticed the advantage of Insertion sort when the array is partially sorted, and some other may also think of inventing an algorithm that tries to partially sort the array in minimum amount of time.
This is what the Shell sort tries to do. It partially sorts the array by iterating over it several times, using the same algorithm of Insertion sort, but, instead of comparing every two adjacent elements; j & j-1, we compare between elements at j & j-h.
In every iteration, we choose a value for h. So, the question is, which sequence of values for h(increments) should we use?
- (power of 2) -1 = 1, 3, 7, 15, …
- 3x + 1 = 1, 4, 13, 40, …
- Sedgewick = 1, 5, 19, 41, …
The sequence of values for h begin from greater to smaller, right to left.
Implementation
int h = 1;// h will be strictly less than the array size.
while(h < N/3) h = h*3 + 1 // 1, 4, 13, ... (3x + 1) sequence.while(h >= 1){
for(int i = h; i < N; i++){ // h-sort the array
// Iterate through elements from right to left, moving h steps back.
for(int j = i; j >= h; j-=h){ // Swap a[j] with a[j-h] as long as a[j] < a[j-h]
// Otherwise, break.
if(less(a[j], a[j-h])) swap(a, j, j-h);
else break;
}
} // Use the next number in the (3x + 1) sequence.
h = h/3;
}
Now, If N = 15, using the (3x + 1) sequence, the array after sorting it with h=13 and h=4 will be partially sorted. So, when h=1 so it won’t take much time to have it fully sorted.
That’s how Shell sort take the advantage of Insertion sort when array is partially sorted.
Conditions
If the array is g-sorted, then it will remain g-sorted after h-sorting it. Meaning, if the array is 7-sorted(h=7), then it will remain 7-sorted after 3-sorting it. That’s how Shell sort gains it’s efficiency.
Analysis
Time →The worst case number of compares with (3x+1) sequence is O(N^(3/2)). In practice, it’s much less than O(N^(3/2)), but, there is no proven accurate number of compares.
It’s fast, unless the array is huge, and It doesn’t take much code.
Iterating over each value of h in a large sequence of values will take much time.
Memory →It’s an in-place comparison sort same as insertion sort.
Shell Sort Vs Insertion Sort
The idea depends on the increments h; instead of going one by one step backward, we go in a specific sequence, which increase the chances of having an early sorted array with the least amount of time.
