Sorting Algorithm Overview
- This chapter introduces commonly used sorting algorithm (Covered all sorting algorithm in COMP90038 course).
- Covered:
SelectSort (Brute Force)
- [ABS] Swap the index one and the Selected the smallest one
- [Pseudocode]
function SelectSort(A[~],n) n<-lengthfor i <- 0 to n-2 do min <- i for j <- i+1 to n-1 do if A[j] < A[min] then //Find the smallest one! min <- j t <- A[i] //Swap A[i] and A[min] A[i] <- A[min] A[min] <- t - [Time Complexity]
Basic Operation(A[j] < A[min]), its efforts(1)
Worst recursive times(n^2)
So worst TC belongs to O(n^2) - [Property]
In-Place? Y
Stable? N
Input-insensitive? Y(No sensitive)
InsertionSort (Decrease and Concur)
- [ABS] Take the index one, and downward to left to find a place to insert.(swap the elements inside the scope if they are not the target to be inserted in)
- [Pseudocode]
function insertionsort(A[~],n)for i <- 1 to n-1 do v <- A[i] //take the index one j <- i - 1 //make a index of comparison target while j >= 0 and v < A[j] do // skip those non-target A[j+1] <- A[j] //swap the non-target to right to make a place j <- j-1 //downward then A[j+1] <- v //insert the target to the place(already empty) - [Improvement]
when the minimum element is known, we can put it in the first element, so the j >= 0 statement can be thowrn, just keep v < A[j] is enough. - [Time Complexity]
Basic Operation(v < A[j]), its efforts(2)
Worst(Reverse order) recursive times(n)
So worst TC belongs to O(2n * n) ->> O(n^2)
Best recursive times(0)
So best TC belongs to O(n) - [Property]
In-Place? Y
Stable? Y
Input-insensitive? N(sensitive)
ShellSort (Based on InsertionSort)(Decrease and Concur)
- [ABS]Based on InsertionSort, it first evenly grouped the elements into K sub-group, and in each group execute the insertionsort, and finally use the insertionsort to finalise the overall result. ##Left element has priority!See code!
- [Pseudocode] NOT EXAMINABLE
- [Time Complexity]
Worst case TC belongs to O(nSQRT(n)) - [Property]
In-Place? Y
Stable? N
Input-insensitive? N(sensitive)
MergeSort (Divide and concur) - inluding divide and combine
- [ABS]First divide into piece of size 1, and then do the merge function(Visually, it is from the left most two pair(initial size is 1) and sorting).
- [Pseudocode] - Divide
function mergesort(A[.],n)if n > 1 then //State the stopping condition for i <- 0 to BOTTOM(n/2 -1) do // Divide the left part to B B[i] <- A[i] for i <- 0 to UPPER(n/2 - 1) do // Divide the right part to C C[i] <- A[BOTTOM(n/2) + i] mergesort(B[.],BOTTOM(n/2)) mergesort(C[.],UPPER(n/2)) merge(B[.],BOTTOM(n/2),C[.],UPPER(n/2),A[.]) //Combine - [Pseudocode] - Combine
function merge(B[.],p,C[.],q,A[.])i <- 0, j <- 0, k <- 0 //init three indexes while i < p and j < q do //avoid out of bounds //copy the minimal element to A //see <= , so left element has priority to copy to A when B&C same if B[i] <= C[j] A[k] <- B[i] i <- i + 1 else A[k] <- C[j] j <- j + 1 k <- k + 1 if i = p then copy C[j]...C[q-1] to A[k]...A[p+q-1] else copy B[i]...B[p-1] to A[k]...A[p+q-1] - [Time Complexity]
Divide costs logn, Merge costs n
Total TC belongs to Theta(nlogn) - [Property]
In-Place? N
Stable? Y (because left element always has priority)
Input-insensitive? Y(insensitive)
QuickSort (Divide and concur) - inluding divide and combine - most efficient one
- [Pseudocode] - Main
function quicksort(A[.],lo,hi)if lo < hi then s <- partition(A,lo,hi) // Remember to assigned the return to s quicksort(A,lo,s-1) quicksort(A,s+1,hi) // Remember it is s+1 - [Pseudocode] - Partition
function partition(A[.],lo,hi)p <- A[lo] i <- lo j <- hi repeat while i < hi and A[i] <= p do i <- i + 1 while j >= lo and A[j] > p do j <- j - 1 swap(A[i],A[j]) until i >= j swap(A[i],A[j]) // undo last swap swap(A[lo],A[j]) // bring pivot to j position return j - [Improvement 1]
When analysing quicksort in the lecture, we noticed that an already sorted array is a worst-case input. Is that still true if we use median-of three pivot selection?
Answer: This is no longer a worst case; in fact it becomes a best case! In this case the median-of-three is in fact the array’s median. Hence each of the two recursive calls will be given an array of length at most n/2, where n is the length of the whole array. And the arrays passed to the recursive calls are again already-sorted, so the phenomenon is invariant throughout the calls. - [Improvement 2]
Slides<<P62
- [Time Complexity]
Worst Case O(n^2)
Best Case O(nlogn) - [Property]
In-Place? Y
Stable? N
Input-insensitive? N(sensitive)
HeapSort (Transform and Concur)
- [ABS] Heapsort = 构建最大堆 + 删除最高优先级元素
- [Time Complexity]
Insert elements to a heap costs logn + Make it Heighest Heap cost n + deltete the highest priority element cost logn
TC OVERALL O(nlogn) - [Step]
1.插入后的最大堆平衡 ：右 -> 左 -> 右（最下面的孩子->父母（若有变）->孩子重新回去验证）
2.删除最高优先级元素：第一个元素放在最末尾，然后按照插入的步骤重新平衡验证（次最大的接着放在倒数第二个，以此类推） - [Property]
In-Place? Y
Stable? N
Input-insensitive? Y(insensitive)
Sort by Couting (Use Space to Reduce Time)
- [Must Sutisfy] the length N >> number scope! It is not efficient to use when k > nlogn!
- [Time Complexity and steps]
OVERALL COMPLEXITY IS O(n+k) ->> O(n)- construct a array B(length k+1), initial all value to 0.[cost O(k+1)]
- from left to right to traverse, and count each element appear times to record in B.[cost O(n)]
- In B, accumulation from left to right.[cost O(k)]
- Construct a array C(length n), left its defalt. [cost O(1)]
- Regard the value of B as index in C, add the value to C.[cost O(n)]
- Overall, cost O(2k+2n+2) ->> O(n+k) ->> O(n) [Linear Complexity]
Comparison of Sorting algorithms
- Comparison
BF SelectSort | Y | N | Y | O(n^2)In-Place? | Stable? | Input-Insensitive? | Time Complexity
DeC InsertiSort | Y | Y! | N! |Be-O(n) Wor-O(n^2)
DeC ShellSort | Y | N | N! |Wor-O(nSQRT(n))
DiC mergesort | N | Y | Y | O(nlogn)
DiC quicksort | Y | N | N |Be-O(nlogn)Wor-O(n^2)
TrC HeapSort | Y | N | Y | O(nlogn)
2017 Sample
- Stable means the order of input elements is unchanged except where change is required to satisfy the requirements. A stable sort applied to a sequence of equal elements will not change their order.
2017 Sample
- In-place means that the input and output occupy the same memory storage space. There is no copying of input to output, and the input ceases to exist unless you have made a backup copy. This is a property that often requires an imperative language to express, because pure functional languages do no have a notion of storage space or overwriting data.