ACE Take-Away: Lecture No.5 Sorting Algorithms
Ch'i YU Lv3
  2022-10-19 13:46:40 2022-10-19 13:46      4 Mins  

Take-Away Notes for Module COMP2048.

Bubble Sort, Selection Sort, Insertion Sort;

  • Proofread
  • Reviewed
  • Add Figures

Simple Sorting Algorithms

Bubble Sort

Bubble Sort repeatedly compares and swaps(if required) adjacent elements in every pass.

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int[] arr) {
    int temp;

    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Complexity

(Worst) Time Complexity:

Note: For the ith pass through the all n-1 passes, there would be n-i comparisons and swaps.

(Worst) Space Complexity: .

In-Place Sort.

Selection Sort

Selection Sort selects ith smallest/biggest element from the unsorted sub-sequence and places it at ith position. Arena-Driven.

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
void  selectionSort(int[] arr){   
    int temp, pos_greatest; 
    for(int i = arr.length-1; i > 0; i--){       
        pos_greatest = 0;       
        for(int j = 0; j <= i; j++){         
            if( arr[j] > arr[pos_greatest])             
            pos_greatest =  j;        
        }      
        temp = arr[i];      
        arr[i] = arr[pos_greatest];      
        arr[pos_greatest] = temp;
    }  
}

Complexity

(Worst) Time Complexity:

Note: For the ith pass through the all n-1 passes, there would be n-i comparisons but 1 swap only.

(Worst) Space Complexity: .

In-Place Sort.

Insertion Sort

Selection Sort inserts every element from the unsorted sub-sequence and inserts it in a appropriate position within a sorted subsequences.

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(int[] arr){   
    int j, temp;   
    for(int i = 1; i < arr.length; i++){      
        temp = arr[i];
        j = i;
        while(j >= 1 && arr[j-1] > temp){         
            arr[j] = arr[j-1];        
            j--;
        }      
    arr[j] = temp;
    }
}

Complexity

(Worst) Time Complexity:

Note: Must make comparisons and shifts to the right.

(Worst) Space Complexity: .

In-Place Sort.

Advanced Sorting Algorithms

Merge Sort

Divide-and-Conquer based sorting algorithms. - Divide: Divide the input data in two (or more) disjoint subsets - Conquer: Solve the sub-problems recursively - Combine: Combine the solutions to sub-problems into a solution for the problem

Code Implementation

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
void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    sort(arr, 0, arr.length - 1);
}

void sort(int[] arr, int left, int right) {
    if (left == right) {
        return;
    }

    int mid = left + ((right - left) >> 1); // i.e. mid = (left + right) / 2

    sort(arr, left, mid);
    sort(arr, mid + 1, right);              // divide method

    merge(arr, left, mid, right);
}

void merge(int[] arr, int left, int mid, int right){
    int[] temp = new int[right - left + 1];

    int i = 0;
    int p1 = left;
    int p2 = mid + 1;

    while (p1 <= mid && p2 <= right) {
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        //  result = <expression> ? <statement1> : <statement2>
        // if expression is true then result is statement 1 otherwise statement 2
    }

    while (p1 <= mid) {
        temp[i++] = array[p1++];
    }

    while (p2 <= mid) {
        temp[i++] = array[p2++];
    }

	for (int j = 0; j < temp.length; i++) {
		array[left + j] = temp[j];
	}
}

Complexity

(Average) Time Complexity:

Merge Sort Analysis

(Worst) Space Complexity: .

Out-Place Sort.

Heap Sort

TBC.

See also in: Runoob.com

Quick Sort

Divide-Recur-Conquer based randomized sorting algorithms. - Divide

Pick a random element (called pivot) and partition the array into:

  • elements less than

  • elements equal to

  • elements greater than

  • Recur

    Sort and

  • Concur

    Join , and .

Code Implementation

Quick Sort

Time Complexity

Note: See also in Textbook, Section 12.2, Page 544 for further calculation

In-place Quick Sort

TBC. See also in the textbook, section 12.2.2, "Additional Optimizations for Quick Sort"

Summary

Algorithm Time Complexity Notes
Selection Sort In-Place; For little inputs
Insertion Sort In-Place; For little inputs
Quick Sort In-Place; Randomized Ideally; For large inputs; Fastest
Heap Sort , ideally as expected In-Place; For large inputs; Fast
Merge Sort Out-Place; Sequential Data Access(e.g. Queue); For huge inputs; Fast