[Algorithms] Sorting#2 — Shell Sort, Quick Sort
To check Bubble, Selection, and Insertion sort, visit [Algorithms] Sorting#1.
4. Shell Sort
Concept
Shell sort, Donald L. Shell came up with, is mainly a variation of Insertion Sort. Insertion sort has the following pros and cons:
- pros: If the array is almost sorted or completed to sort, the performance is very high.
- cons: When an element has to be moved far ahead, many movements are required since we move only one position ahead in insertion sort.
Shellsort is to allow the exchange of far items. In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.
< Shell Algorithm>
- Divide the array into several groups.
- Do insertion sort for each group.
- Reduce the number of movements by combining the groups.
- Repeat 1~3 until the number of groups is 1.
- Group by two elements which are 4 spaces apart from each other and sort each group using insertion sort. ( Sort {8,7}, {1,6}, {4,3}, {2,5} groups)
- We call this ‘4-sorted’
- It is not completely sorted yet, but it is getting closer to being sorted.
- After ‘4-sort’, make 2 groups with elements which are 2 spaces apart from each other as above and then sort them using insertion sort. ( Sort {7,3,8,4}, {1,2,6,5})
- We call this ‘2-sorted’
Finally, do normal insertion sorting, which can be called ‘1-sorted’.
Although the number of times to be sorted increases, the total number of element movements decreases, it can be more efficient than insertion sort.
Implementation
5. Quick Sort
Concept
Quick Sort is a Divide and Conquer algorithm, like merge sort. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot.
- Pick a random element as pivot.
- Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
<Properties>
- Time complexity: Omega(nlogn), Theta(nlogn), O(n²)-(since it needs n times of recursive call and n times of comparison operations)
- Space complexity: Average-O(log n), Worst — O(n)
- Unstable sorting: When the array has equivalent values, their order can be varied after sorting.
- The fastest algorithm even compared to other O(nlog n) sorting algorithms.
- If the array is already sorted, quickSort performs slowly.
