Common Sorting Algorithms
2020, Mar 02
Summary & Comparisons for Common Sorting Algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Shell Sort, Bucket Sort, Heap Sort, Count Sort
Summary:
| Algorithm | Description | Complexity |
|---|---|---|
| BubbleSort | Two layers of for loop for sorting an array, keep bubble up the current round of max items to the end of the array | Space: O(1), Time: (N^2) |
| SelectionSort | Similar to bubble sort, but instead of bubbling up, identify the next max/min items from the unsorted section of the array and append it to the edge of the sorted section | Space: O(1), Time: (N^2) |
| InsertionSort | Keep a sorted area in the beginning section/end section of the array, increasing the sorted erea by inserting element from the unsorted section and hence reduce the unsorted side of the section and increase the sorted area | Space: O(1), Time: (N^2) |
| Merge Sort | Divide the array into sub arrays until each array contains only 1 element, then merge the array back | Time Complexity: O(nlogn), Space: (N) |
| Quick Sort | Choose pivot from the array, and create a pivot, a sub-array which is smaller than the pivot and sub-array which element larger than the pivot. recursively call the quick sort on the subarrays | as compare to merge sort, quick sort provides similar levels of Time complexity (nLogn), but it supports in-place sort, hence no additional cost on memory can be achieved. |
| Shell Sort | ShellSort is a optimied version of insertion sort, split the array into sub arrays, based on the gap n, where n starts from floor(array.count/2) and keep devided by 2 until to 1. | |
| Heap Sort | For an array, converted it to heap first, then shift the root (max) to the end of the array and keep shiftdown and swaping process | Time: nLogn, Space: 1 |
| Count Sort | Count the appearance of elements in arrays, based on the count, reproduce the sorted array | Time: n, Space: n (not in-place sort) |
| Bucket Sort | Distributed algorithm, split the array into different trunks and sort each separately |