Vincec's Dimension

Sort Review

Word count: 733 / Reading time: 5 min
2019/06/12 Share

Basic for search, with for loops

Bubble Sort

(exchange) rearrange pairs of elements which are out of order, until no such pairs remain.

  • two for search(pos from end to 0, one from 0 to pos)
  • compare value with next, if smaller, swap value
1
2
3
4
5
6
7
8
9
void bubbleSort(){
for(int i = arrSize - 1; i > 1; i--){ //i > 1
for(int j = 0; j < i; j++){ //j < i
if(arr[j]>arr[j+1]){
swap(j, j+1);
}
}
}
}
  • first need sort
  • binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void binarySearch(int value){ //arr is already sorted
int low = 0;
int high = arrSize - 1;

while(low <= high){
int middle = (low + high)/2;
if(arr[middle]<value) low = middle + 1;
else if(arr[middle]>value) high = middle - 1;
else{
//found;
low=high+1;//to stop search
}
}
}

Selection Sort

extract the largest element from the list, exchange with the last element in the current list, and repeat.

  • look for the smallest from pos(init to 1) to end
  • swap smallest with (pos-1)
  • make pos move to next
1
2
3
4
5
6
7
8
9
void selectionSort(){
for(int x = 0; x < arrSize; x++){
int min = x;
for(int y = x; y < arrSize; y++){ //find the smallest from remain in arr
if(arr[y]<arr[x]) x = y;
}
swap(x, min); //swap the smallest to the left with ordered
}
}

Insertion Sort

putting an element in the appropriate place in a sorted list yields a larger sorted list.

  • start from second and always keep sorted
  • if next value is smaller than keep the value, and move all the sorted value to right one by one and then insert to right posiiton
1
2
3
4
5
6
7
8
9
10
11
void insertionSort(){                           //like manage Standard 52-card deck
for (int i = 1; i<arraySize; i++){ //need to sort arr[i]
int j = i; //posible insert position start from i
int toInsert = arr[i];
while((j>0 && arr[j-1]>toInsert)){ //put the next element arr[i] into already sorted list, need to move sorted value to right one by one
arr[j] = arr[j-1];
j--;
}
arr[j] = toInsert; //put the insert to j index; break condition is (j = 0) or (arr[j-1]<=toInsert), insert can either be the smallest or the one right next to arr[j-1]
}
}

Quick Sort

divide-and-conquer algorithm. Its average running time is O(N log N).

Figure Courtesy of Weiss Data Structures Book

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
public static void main(String[] args) {
int[] A = {-4,-1,0,3,9, 45, 10};

A = quicksortII(A, 0, A.length-1);

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

private static int[] quicksortII(int[] A, int start, int end) {
if(start >= end) {
return A;
}

int pIndex = start;
int pivot = A[end];
for(int i = start; i < end; i++) {
if (A[i] < pivot) {
A = swap(A, pIndex, i);
pIndex++;
}
}
A = swap(A, pIndex, end);
A = quicksortII(A, start, pIndex - 1);
A = quicksortII(A, pIndex + 1, end);
return A;
}

private static int[] swap(int[] A, int a, int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
return A;
}

Bucket Sort

桶排序(Bucket sort)

separate into piles based on the first letter, then sort each pile.
place items into various buckets based on a key or partial information about a key.

Radix Sort

radix sort can be applied to data that can be compared partially like integers of characters.
Radix sort cannot be applied to data that needs to be compared as a whole

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

Heap Sort

常见排序算法 - 堆排序 (Heap Sort)

Merging Sort

Two sorted lists can be easily combined to form a sorted list.

Animation

Reference

Author: VINCEC

Permalink: https://vince-amazing/blog/2019/06/12/sort-review/

Date: June 12th 2019, 8:23:00

Copyright license: The article usingCC licensing 4.0

CATALOG
  1. 1. Linear Search
  2. 2. Bubble Sort
  3. 3. Binary Search
  4. 4. Selection Sort
  5. 5. Insertion Sort
  6. 6. Quick Sort
  7. 7. Bucket Sort
  8. 8. Radix Sort
  9. 9. Heap Sort
  10. 10. Merging Sort
  • Animation
  • Reference