Quick Recap on Various Elementary Sorting
This is a quick recap on different elementary sorting including Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, the main point here is to review them and explain why are we interested in each of them.
At least to me, I am quite familiar with say Quick Sort, Merge Sort, Heap Sort, but for Elementary Sorting, it is often I forget what exactly it is and could sometimes mistakenly treat one as another, and sometimes I don’t quite get it why are we even interested in it? This post services to me as a quick recap and hopefully to you too for your convenient references later in the future.
Different Elementary Sorting and the Whole Point:
I list all the key points for which we are interested in each of the four elementary sorting algorithms
(1) Bubble Sort:
- What is it: it works by repeatedly scan the whole array pass by pass and swap any adjacent items if the are in wrong order.
- Why it is called Bubble Sort: because smaller elements “bubble” to the beginning of the list.
- Optimization or key observation: say in j-th pass, the final swap is between A[i - 1] and A[i], then all the elements after i are already sorted, we just need to scan all the elements from 0 to i – 1 during the next j + 1 pass. All those after i and including i don’t have to be checked anymore.
- Something interesting: small elements (turtles) towards the end, move to the beginning extremely slowly while large elements (rabbits) at the beginning of the list could be quickly swapped.
- Any advantages: could be possibly used to determine whether a list is sorted or not (just one pass and see if there is any swaps or not), but still it works no better than Insertion Sort which could do the same thing in linear time to check a list is sorted or not, and Insertion Sort outperforms when the list is partially sorted.
- Suggestion of usage: generally, it should be avoided.
(2) Selection Sort:
- What is it: it works by selecting the minimum value from the remaining unsorted elements in the list and append this value at the tail of the sorted portion until the whole list is in order.
- Why it is called Selection Sort: I only guess the reason, it might be that is just selects the smallest value out of the remaining unsorted portion of the array.
- Any advantages: it only needs O(N) swaps/writes while Insertion Sort needs O(N^2) swaps.
- Optimization: it could be quickly modified into Heap Sort which runs in O(NlogN) time by using a heap to keep the smallest value, and I think it is a good start point for heap sort
- Suggestion of usage: for list of small size (i.e. fewer than 10–20 elements), it it more efficient that those complicated sorting algorithm such as merge sort or quick sort.
- Remarks: while bubble sort sort the list from tail to head (keep the tailing part sorted), selection sort works like sorting the elements from head to tail (keep the heading part sorted before the current elements).
(3) Insertion Sort:
- What is it: it works by insert the current elements into the correct position in the first sorted portion before the current elements.
- Why it is called Insertion Sort: as described in the algorithm, it just inserts elements.
- Any advantages: 1) works quite efficiently if the array or list is already partially sorted. 2) stable; 3) online; 4) in-place
- Suggestion of usage: for list of small size (i.e. fewer than 10–20 elements) or partially sorted list
- Remarks: the number of swaps in Insertion Sort is equal to the number of inverse pairs in the list or array.
(4) Shell Sort:
- What is it: more strictly, I don’t think Shell Sort could be regarded as elementary sort because it involves quite sophisticated techniques and it is just an enhanced version of Insertion Sort. So instead of sort the while array or list at the first place, it would perform several so called J-Sorting which sort every J elements and put them in the right order, each single sort is actually an Insertion Sort, it would perform a 1-Sorting at the last step and it becomes the Insertion Sort, however, since the majority of the list are sorted by the previous passes, the final step of Insertion Sort would be quite efficient, and generally, Shell Sort performs better than simple Insertion Sort.
- This is all I want to say about Shell Sort.
To summarize, I list interesting points for each elementary sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort and Shell Sort. These are all what I think could probably interest people to study the specific sorting algorithm and this post just serves as a quick recap about all the key points we need to know that each of the four sorting algorithm.