Sorting Algorithms

Summary

Sort type Time Complexity Space complexity stable?
bubble sort $O(n^2)$ $O(1)$ Yes (do not swap on equal val)
selection sort $O(n^2)$ $O(1)$ Yes (do not update max idx on equal value)
insertion Sort $O(n^2)$ $O(1)$ Yes (stop insert on equal val
radix/bucket sort $O(nd)$ d is number of digit for max val $o(n)$ Yes
heap Sort $O(nlogn)$ $O(n)$ No?
merge sort $O(nlogn)$ $O(n)$ Yes
quick sort $O(nlogn)$ $O(logn)$ call stack w/ tail recursion No

bubble sort

algorithm

  • start from left to right, inspect two adjacent elements, swap two element if the value of first is larger than second
  • continue with the next pair until reaching the end of the array
  • the largest element now is at the end of the array
  • repeat above two steps for rest of unsorted portion of the array until the entire array is sorted

complexity

  • Time $O(n^2)$
  • Space $O(1)$

code

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
53
54
55
56
57
58
59
60
61
62
63
64
package sorting;
/**
*
* @author xruan
*
* key idea:
* - two for loops (O(n^2))
* - each inner loop from start to end, compare and swap if a[i] > a[j]
* - each inner loop will put current largest element of the sub-array to the end (1 element sorted)
*
*
* example:
*
* 1, 1, 3, 10, 3, 4, 2, 5 O(n)
* 1, 1, 3, 3, 4, 2, 5, [10] O(n)
* 1, 1, 3, 3, 2, 4, [5, 10] O(n)
* 1, 1, 3, 2, 3, [4, 5, 10] O(n)
* 1, 1, 2, 3, [3, 4, 5, 10] O(n)
* 1, 1, 2, [3, 3, 4, 5, 10] O(n)
* break // less than O(n*n) with break check
*
* pesudo code:
* for i in range(0, len - 1):
* for j in range(0, len - 1 - i):
* if a[j] > a[j+1]:
* swap
* if no swap: // already in sorted order
* break
*
*/

public class BubbleSort {
public static void main(String[] args) {
int[] array = new int[]{1, 1, 3, 10, 3, 4, 2, 5};

int[] sortedArray = bubbleSort(array);
for (int i = 0; i < sortedArray.length; i++) {
System.out.print(sortedArray[i]);
if (i != sortedArray.length - 1) {
System.out.print(", ");
}
}

}
public static int[] bubbleSort(int[] array) {
// [4, 3, 2, 1]
int len = array.length;
boolean swapped = false;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
if (swapped == false) {
break;
}
}
return array;
}
}

selection sort

algorithm

  • find the smallest element using linear scan and move it to the front (via swapping)
  • find the second smallest with same process and move it to the next postion
  • repeat above steps unitl array is sorted

complexity

  • Time: $O(n^2)$
  • Spcae: $O(1)$ no extra space required

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void selSort(int[] array) {
if (array.length == 0 || array.length == 1) {
return;
}
int len = array.length;
int sorted = 0;
for (int i = 0; i < len; i++) {
int min = i;
for (int j = i; j < len; j++) {
min = array[j] < array[min] ? j : min;
}
// swap min to sorted
int tmp = array[min];
array[min] = array[sorted];
array[sorted] = tmp;
sorted++;
}
}

merge sort

Algorithm

  • break down the entire array until it has single.
  • compare and merge the elements in the same group (activation record).
  • after the last merge, you will get a sorted array.

complexity

  • Time: $O(nlog(n))$ in worst case.
  • Space: $O(n)$ auxiliary.

Code

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
public class MergeSort {
public static void main(String[] args) {
int[] array = {5, 5, 4, 3, 1, 3, 1, 0, 5};
int[] sorted = new int[array.length];
System.out.println("Original Array: ");
String sep = "";
for (int n : array) {
System.out.print(sep + n);
sep = ",";
}
mergeSort(array, 0, array.length -1, sorted);
System.out.println("\nSorted Array: ");
sep = "";
for (int i = 0; i < array.length; i++) {
System.out.print(sep + array[i]);
sep = ",";
}
}
public static void mergeSort(int[] array, int start, int end, int[] sorted) {
if (end - start >= 1) {
int mid = start + (end - start) / 2;
mergeSort(array, start, mid, sorted);
mergeSort(array, mid+1, end, sorted);
merge(array, start, mid, end, sorted);
}
}

public static void merge(int[] array, int start, int mid, int end, int[] sorted) {
int i = start;
int j = mid+1;
int k = 0;
while (i <= mid && j <= end) {
if (array[i] <= array[j]) {
sorted[k++] = array[i++];
} else {
sorted[k++] = array[j++];
}
}
while (i <= mid) { // process left half first, stable sort
sorted[k++] = array[i++];
}
while (j <= end) {
sorted[k++] = array[j++];
}
for (int v = 0; v < k; v++) {
array[v+start] = sorted[v];
}
}
}

quick sort

update: 05/12/2019

Just for fun 博主《被忽视的 partition 算法》 一文对partiton算法进行了深入的研究,提供的partition算法 1. 更加高效(删去了swap 方程中tmp的使用,每一次的swap减少了一次的拷贝)2. 更加简洁 (代码量更少)3. 更容易解释算法每一步的用途(解决了v2中 right, left, 和pivot位置都是模糊点,v1对此可以清晰的解释)。有时间再仔细研究Partition 进阶算法部分(TODO)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void quickSort(int[] arr, int l, int r) {
if (l < r) { // l == r 已经没必要partition了
int mid = partition(arr, l, r);
quickSort(arr, l, mid - 1); // mid the piviot idx, which alreay in its pos, hence mid - 1
quickSort(arr, mid + 1, r); // mid the piviot idx, which alreay in its pos, hence mid + 1
}
}

public static int partition(int[] arr, int l, int r) {
int pivot = arr[l]; // 首元素作pivot
while (l < r) {
while (l < r && arr[r] >= pivot) r--; // pivot can be at either side of the piviot, further parition will put val the same as pivot into place
arr[l] = arr[r];
while (l < r && arr[l] <= pivot) l++; // pivot can be at either side of the piviot, further parition will put val the same as pivot into place
arr[r] = arr[l];
}
arr[l] = pivot; // 此时 l == r, arr[l] == arr[r] 已备份,因此pivot可以复写arr[l]
return l; // l == r after break from while(), pivot location
}

key idea

  • each operation takes $O(n)$ in worst case (at first step, every value compare to piviot)
  • the height of the tree is $O(N)$ in worst case (either piviot is smallest/largest value), and $O(logN)$ in best case.
  • hence, total time complexity is $O(N^2)$ in worst case, $Nlog(N)$ in best case.

How to choose the piviot element?

  • why not choosing pivot randomly?

randomly select pivot will work, however, the worst case time complexity of the algorithm will become $O(n^2)$.

Time Complexity Analysis

  • Worst case $O(n^2)$:
    everytimes pivit picked is either the smallest or the largest elements of the array. From $n->n-1->n-2-> \dots -> 1$
  • Average/best case $O(nlog(n))$:
    pivit split array evenly so the number of steps is less. From $n -> 2 n/2->4 n/4 \dots$. The height of the tree is $log(n)$ Hence, $O(nlog(n))$.

Algorithm

  • select the middle value as the pivot.
  • maintain two pointers left and right.
  • left pointer traverse from left to right until found element larger than pivot.
  • right pointer traverse from right to left until found element smaller than pivot.
  • swap element at index left with right.
  • continue until left > right.
  • recursively quickSort the part smaller than pivot and the part larger than pivot.

Code Short Version

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
public Random rand;
public void sortIntegers2(int[] A) {
rand = new Random();
// write your code here
quickSort(A, 0, A.length - 1);
}

public void quickSort(int[] A, int start, int end) {
if (start < end) {
int p = partition(A, start, end);
quickSort(A, start, p);
quickSort(A, p + 1, end);
}
}

public int partition(int[] A, int start, int end) {
// key1: rand.nextInt(2) returns [0, 1]
int index = rand.nextInt(end - start + 1) + start;
// int index = start + ((end - start) >> 1);
// key2: pivot is A[index]
int pivot = A[index];
int left = start;
int right = end;

// key3: NOT left < right
while (left <= right) {
// key4: NOT A[left] <= pivot
while (left <= right && A[left] < pivot) { // left <= right is required to prevent indexOutOfBound exception by `A[left]`
left++;
}
while (left <= right && A[right] > pivot) {
right--;
}

if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;

left++;
right--;
}
}
return right;
// // A[start... right]
// quickSort(A, start, right);
// // A[left ... end]
// quickSort(A, left, end);
}

Algorithm

  • similar process as the version above.
  • instead of randomly choosing pivot from the middle value.(which could possible be the largest/smallest, to lead to worst time performance [quickSort not able to break into even workload to utilize the parallelism.])
  • we choose following three values: array[low], array[mid], array[high].
  • return the median of three as pivot.
  • re-value array[0] with smallest, array[length - 1] = largest, array[mid] = array[length - 2], finally move pivot to array[length - 2].

Code Faster Version

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
53
54
55
56
57
58
59
60
61
62

public class QuickSort {
public static void main(String[] args) {
int[] A = {3, 4, 5, 9, 1, 2, 10, 6, -1, 8, 10, 9, 15, 23, 18, 0, 2};
quickSort(A, 0, A.length - 1);
for (int i = 0; i < A.length; i++) {
System.out.print(A[i] + ", ");
}
}
public static void quickSort(int[] array, int low, int high) {
// pick pivot
if (low < high) {
int pivot = partion(array, low, high);
quickSort(array, low, pivot);
quickSort(array, pivot+2, high);
}
}
public static int partion(int[] A, int low, int high) {
int pivot = medianOfThree(A, low, high);
int left = low + 1;
int right = high - 2;
// partition
while (left <= right) {
while (A[left] < pivot) left++;
while (A[right] > pivot) right--;
if (left <= right) {
swap(A, left, right);
left++;
right--;
}
}
swap(A, right + 1, high - 1);;
return right;
}
public static void swap(int[] array, int low, int high) {
int temp = array[high];
array[high] = array[low];
array[low] = temp;
}
/**
* Choose median from array[low], array[high], array[(high + low)/2] as pivot
* Rearrange value high, low, pivot
* @param array
* @param low
* @param high
* @return pivot value
*/
public static int medianOfThree(int[] array, int low, int high) {
int left = array[low];
int right = array[high];
int mid = array[low + (high - low)/2];
// initialization: reorder three elements
array[low] = Math.min(Math.min(left, right), mid); array[high] = Math.max(Math.max(left, right), mid);
array[low + (high - low)/2] = array[high - 1];
int pivot = Math.max(Math.min(left,right), Math.min(Math.max(left,right),mid));
// special case for array less than 3 elements
if (high - low + 1 > 2) {
array[high - 1] = pivot;
}
return pivot;
}
}

radix/bucket sort

https://www.youtube.com/watch?v=Uey0-GOMtT8

key idea

  • can only be used for sorting integers, can be used when range of number is known
  • take adavatage of known integer has finite bit
  • key: during each pass, order of lower bit perserve (by queue) while new pass for higher bit is performing
  • it has to be from lower to higher. (if we process higher bit first, lower bit will mess up the order of higher bit, since most sig bit are important to determine order, we process it last)
  • array in sort order once all bits are passed once

algorithms

  • find largest element, ex. 100
  • number of passes k, determine by the number of digit of largest element, in this example, k=3
  • zero pad all smaller values with less than k bit
  • prepare 10 buckets (queue, for example, since need to retrive value from buttom after each pass)
  • each pass, put value with corresponding digit into corresponding bucket.

for example 023, 012, 100. after first pass:

  • 23 will put into bucket 3
  • 12 puts into bucket 2
  • 100 put into bucket 0

repeat above process for all k passes will result in sorted order

https://www.youtube.com/watch?v=YXFI4osELGU

complexity

  • time: $O(kn)$ where k is the number of bit of max number
  • space: $O(n)$
1
2


Insertion Sort

Algorithm

  • start from $i = 1$
  • move every elements that is larger than currKey to its right until postion found to insert currKey.
  • insert currKey to $j+1$ index, where index $j$ is the last postion check that not meet the requirement (either $j \leq 0$ or currKey $< A[j]$)

Analysis

  • worst case complexity $O(n^2)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static void main(String[] args){
int[] A = {10, 3, 1, 2, 6, 5, 4};
for (int i = 1; i < A.length; i++) {
int currKey = A[i];
int j = i - 1;
while (j >= 0 && currKey < A[j]) {
A[j+1] = A[j];
j--;
}
A[j+1] = currKey;
}
print(A);
}

public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ",");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// descending version

public static void main(String[] args){
int[] A = {10, 3, 1, 2, 6, 5, 4};
for (int i = 1; i < A.length; i++) {
int currKey = A[i];
int j = i - 1;
while (j >= 0 && currKey > A[j]) {
A[j+1] = A[j];
j--;
}
A[j+1] = currKey;
}
print(A);
}

public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ",");
}
}

Heap Sort

  • Sort algorithm based on heap data structure
  • Heapsort is an in-place algorithm, but it is NOT a stable sort.

Algorithm

  • repeatedly swaps the first value(max) of the list with the last value
  • decreases the range of values considered in the heap operation by one (so that prev max will not be reheapify to top)

complexity

time: $O(nlogn)$ for both best & worst case
space: $O(1)$ in place sort

ref: https://en.wikipedia.org/wiki/Heapsort#Algorithm

Lexicographical/Dictionary Sort

  • sort integers from 1 to 13 [1,10,11,12,13,2,3,4,5,6,7,8,9]
  • treating integers as strings and use Arrays.sort() or Collection.sort() will work but have $O(NLogN)$ time complexity
  • below is an O(n) algorithm, n is the number. Since it constructs a tree and does a pre-order traversal, each node(i.e. each number) is visited exactly once.
1
2
3
4
5
1        2       3      4
/ |
10,11,12.. 20,21...
/
100,101,102
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> lexicalOrder(int n) {
// 1,2,3,4,5,6,7,8,9,10,,,,
// 1, 10, 11, 12,13,14,15,16,17,18,19,2,20,21,
List<Integer> res = new ArrayList<>();
for (int i = 1; i < 10; i++) {
dfs(n, i, res);
}
return res;
}

private static void dfs(int n, int curr, List<Integer> res) {
if (curr > n) return;
res.add(curr);
for (int i = 0; i < 10; i++) {
dfs(n, curr * 10 + i, res);
}
}

logs

  • created on 08/30/2016
  • updated quick sort 01/02/2017
  • added selection sort
  • 01/23/18 add bubble sort
  • 01/23/18 add radix/bucket sort
  • 01/23/18 add “key idea” for quicksort
  • 02/08/18 refactored code for quicksort short version
  • 03/18/18 update quicksort key idea
  • 05/05/18 add heap sort idea
  • 05/05/18 add stability sort chart
  • 05/05/18 add shorter quicksort version
  • 09/03/19 add Lexicographical sort

Reference:

经典排序算法 - 归并排序Merge sort
Selection Sort