Basic Sorting Algorithms One
Theory
Ascending order is smallest to largest, descending order is largest to smallest.
We will find that non comparison based sorting algorithms are faster than their comparison based counterparts.
An array with N elements is considered below:
Why do comparison based algorithms take O(N log N) time? If we take an array of size 3 with the values a, b, and c, we can construct the following possibility tree, showing us all the possible comparisons and their results:
Here we see that there are 6 possible outcomes, depending on the outcome of the various comparisons. If we were to extrapolate this from 3 items to N items, we would see that the number of possible outcomes is N!. As we go down the decision tree, we eliminate possibilities so the eventual lower bound is log N! (base, as each node has two possible branches). Using Stirling’s formula we can simplify this to N log N.
Comparison based sorting algorithms have O(N log N) time complexity. The comparison, if/else, creates two possibilities, and the possibility tree created from these possibilities is a binary tree. The minimum number of nodes in this tree is n! and the max is 2^n. Solving for n in the equation n! ≤ 2^n we get log (base 2) of n! (I am now making this up as I go along, so this needs to be double checked!). According to this:
log n! == n log n. And there you go. (check this!)
Non comparison based algorithms don’t have this problem and re usually O(N).
Time complexity break down of sorting algorithms
Memory complexity break down of sorting algorithms. In place means no additional memory is needed.
What is Stability in Sorting
What if we need to sort the following “database” by the two columns shown
Here it is sorted by the first column
When we sort by the second column, because we used a stable sorting approach, the relative order of the first column is not lost, as shown
An unstable sorting algorithm would not follow these rules and would thus be unsuitable for double column sorting, as shown here
Adaptive Sorting Algorithms
Bogo Sort Algorithm
Bubble Sort Algorithm
For descending order change the greater than sign in the comparison to a less than sign
Selection Sort
Insertion Sort
Shell Sort
Quicksort Algorithm
Timsort combines insertion sort and merge sort.
Example
5 is randomly chosen as the pivot.
So we need to go through the array (O(N)?) and make sure that everything on the left side of the array is less than the pivot and everything on the right side is greater than the pivot. These values are not necessarily in sorted order, just those on the left are less than the pivot and those are the right are greater than the pivot
Then we call quick sort recursively on the left and right sides of the array
Example
Concrete Example
We set i = low, which is the first index of the array. We then go from low to high, and check to see if each item in the array is less than or equal to array[high] which now holds the pivot value
We swap i and j if array[j] ≤ array[high] (array[high] has the pivot we swapped in line 2 of the partition function).
We then increment i.
If we do this over the course of the whole array we ensure that everything before i (the final value it has after the for loop is done) is less than the pivot and everything after is greater than the pivot
Then we swap array[i] with array[high] to put the pivot in its proper place.
We then repeat the process for the left sub array and the right sub array recursively.
Problems with Quick Sort
Merge Sort Algorithm
Breaking the array into smaller and smaller sub arrays. One can divide until there is one item left in the array, this array is sorted by default, or we can divide until we get to a small number of items (say 10) and use insertion sort.
In the conquer phase, we create a new array of length len(arr1) + len(arr2). We run through the two divided arrays starting with index 0 = index1 = index 2, compare them arr1[index1] < arr2[index2]. If arr1[index1] is smaller, then we store that value in the new array, and increment index1, we do the same for index2 if arr2[index2] is smaller.
Hybrid Sorting Algorithms
The same problem here being sorting. So using combinations of sorting algorithms to solve sorting problems.
Non Comparison Based Algorithms
Counting Sort
Only good for integers
Initial set up. Array to sort is on top, the constructed array, where the index is the value of the array to sort is constructed below.
The final result after we go through the array to sort (O(N)) and count all the values
We then go through the counter array and print out the sorted results. We print out 1 three times, then 2 zero times then 3 one time, then four one time, then 5 zero times, then 6 zero times, then 7 two times, then 8 zero times, then 9 zero times, then 10 one time. This involves traversing the counter array (O(k) where k is the difference between the max and min of the array to sort.
Radix Sort
If k > N, then counting sort (O(N + k) may be larger than O(N²)
So here, sorting this using counting sort would take 1004 steps, while with a quadradic time sorting algorithm it would only take 16 steps.
You can also sort strings as well as integers if you follow this rubric
Each line represents one number. The most significant digit is on the left, the least, on the right.
Then we order them based on the counting sort algorithm, and we get this
Then we consider the next digit
Then using the counting sort algo to order them
Then we move to the third digit
Then we order them
Then the next digit
Then order them
Then finally the most significant digit
Then the final order is the sorted order
If the integers are not the same, then leading 0s are used, from what it looks like.
