A summary of sorting algorithms.
Basic sorting algorithms
Algorithms | Time complexity(Avg) | Time complexity(worst) | Time complexity(best) | Space complexity | Stability |
---|---|---|---|---|---|
Bubble Sort | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | Stable |
Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Untable |
Insertion Sort | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | Stable |
Shell Sort | $O(n^1.3)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | Unstable |
Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | stable |
Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Unstable |
Quick Sort | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(n \log n)$ | Unstable |
Count Sort | $O(n+k)$ | - | - | $O(1)$ | Stable |
Bubble Sort
Idea: Bubble the least element to the front position $i=j-1$ at each episode $j$.(j= 1,2,…, len(A))
- Time complexity: $O(n^2)$
- Space Complexity: $O(1)$, in place
1
2
3
4
5
6
7
8
9
10
11
12
13def BubbleSort(A):
"""
Time Complexity: O(n^2)
Space Complexity: O(1), in place
:param A: List(int)
:return: List(int)
"""
for j in range(len(A)): # len(A)-1 episodes
# bubble the least element to the most front position, at i-th index
for i in range(len(A) - 1, j, -1):
if A[i] < A[i - 1]:
A[i], A[i - 1] = A[i - 1], A[i]
return A
Bubble Sort with swap flag
- Problems: The above version of bubble sort would always do len(A)-1 times episodes even though all elements are sorted before that.
- Solution: set a flag to record whether there exists swap during the current episode. If there is no swap in the previous iteration, ilustrating that elements are already in order, it is no need to continue the bubble process.
1 | def BubbleSort_with_flag(A:list): |
Selection Sort
Process: find the least value from A[i:] and swap it with the front (i-th) element at $i$-th episode. (i= 1,2,…, len(A)).
- Time complexity: $O(n^2)$
- Space Complexity: $O(1)$, in place
1 | def SelectionSort(A: list): |
Insertion Sort
Process: keep the former section in order. From the index 1 on, insert the current value at the correct place in previous section.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def InsertionSort(A: list):
"""
Time Complexity: O(n^2)
Space Complexity: O(1), in place
:param A: List(int)
:return: List(int)
"""
for j in range(1, len(A)):
key = A[j]
i = j - 1
while i >= 0 and key < A[i]:
A[i + 1] = A[i]
i -= 1
A[i + 1] = key
return A
Shell Sort
Process: divide the array into len(A)//$h$ groups, and sort separately; the reduce the step $h$ and sort, until the step size reaches to 1.
- It can be seen as an improvement of Insertion Sort.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18def ShellSort(A: list):
"""
:param A: List(int)
:return: List(int)
"""
n = len(A)
h = 1
while h < n / 3:
h = 3 * h + 1
while h >= 1:
# insertion sort
for i in range(h, n):
j = i
while j >= h and A[j] < A[j - h]:
A[j], A[j - h] = A[j - h], A[j]
j -= h
h //= 3
return A
Merge Sort
Idea: divide-and-conquer.
- Time Complexity: $O(n \log n)$
- Space Complexity: $O(n)$
The array version of merge sort:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37def merge(L, R):
"""
:param L: List(int)
:param R: List(int)
:return c: List(int)
"""
c = []
i = j = 0
for _ in range(len(L) + len(R)):
# check whether L or R reaches its end
if i == len(L):
c.append(R[j])
j += 1
elif j == len(R):
c.append(L[i])
i += 1
elif L[i] <= R[j]:
c.append(L[i])
i += 1
else:
c.append(R[j])
j += 1
return c
def MergeSort(A: list):
"""
merge sort from top down (with recursion)
Time Complexity: O(NlogN)
Space Complexity: O(n)
:param A: List(int)
:return: List(int)
"""
if len(A) <= 1: return A
mid = len(A) >> 1
left = MergeSort(A[:mid])
right = MergeSort(A[mid:])
return merge(left, right)
Linked List version [7] :1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
# divide the linked list into two parts
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
second = slow.next
# cut down the fist part
slow.next = None
l = self.sortList(head)
r = self.sortList(second)
return self.merge(l, r)
def merge(self, l, r):
"""
merge sort helper func
:param l: the left part of linked list
:param r: the right part of linked list
:return:
"""
if not l or not r:
return l or r
if l.val > r.val:
l, r = r, l
head = pre = l # define the return head node
l = l.next
while l and r:
if l.val < r.val:
pre.next = l
l = l.next
else:
pre.next = r
r = r.next
pre = pre.next
# at least one of l or r is None
pre.next = l or r
return head
Heap Sort
Process:
- Build a max heap
- Swap the top element of max heap with the end element, heaptify the max heap followed by heapsize -1 , until the array in order.
- Time complexity: $O(n \log n)$
- Space complexity: $O(1)$, in place
1 | def Parent(i: int): return (i - 1) >> 1 |
Quick Sort
Process: divide-and-conquer
- Randomly choose one num as the pivot element A[r]
- Put elements less than A[r] on the left side, whilst numbers no less than A[r] on the righ side
- Repeat the step2, until there is only one element on the left and right side.
- Time complexity: $O(n \log n)$
1 | def partition(A: list, p: int, r: int): |
Bucket sort
Bucket Sort is a kind of non-comparison sorting algorithms.
Count Sort
Process:
- find the maximum $k$ of the array, and create $k+1$ new buckets
- Traverse the array for one pass, put the elements into the buckets
- Traverse all the buckets, take the values from buckets.
1 | def CountSort(arr: list): |
Advance
Dutch national flag problem
Dutch national flag problem:
Solution: three-way partitioning
Three-way partitioning [2][3] divides the arrays into four sections:
- A[:lo]: all of 0s (red)
- A[lo:mid]: all of 1s (white)
- A[mid:hi]: unclassified
- A[hi:]: all of 2s (blue)
The pseudocode:
- Input: array A with values 0,1,2, mid value 1
- Initilize $i \leftarrow 0, j \leftarrow 0, n \leftarrow sizeof(A)-1$
- while j<=n:
- if A[j] < mid:
- swap A[i] and A[j]
- $i \leftarrow i+1$
- $j \leftarrow j+1$
- else if A[j] > mid:
- swap A[j] and A[n]
- $n \leftarrow n-1$
- else:
- $j \leftarrow j+1$
- if A[j] < mid:
- Time complexity: $O(n)$
- Space complexity: $O(1)$
1 | def sortColors(nums:list): |
References
- 1.Wiki:Dutch national flag problem ↩
- 2.Dutch National Flag, U of Monash ↩
- 3.Three-way quicksort solution ↩
- 4.Leetcode 75 Sort Colors ↩
- 5.Heap Sort blog ↩
- 6.Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms, Third Edition. ↩
- 7.Leetcode 148. Sort List ↩