# Yekun's Note

Machine learning notes and writeup.

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

### 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.

## 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

## 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.

## 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.

## Merge Sort

Idea: divide-and-conquer.

• Time Complexity: $O(n \log n)$
• Space Complexity: $O(n)$

The array version of merge sort:

## Heap Sort

Process:

1. Build a max heap
2. 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

## Quick Sort

Process: divide-and-conquer

1. Randomly choose one num as the pivot element A[r]
2. Put elements less than A[r] on the left side, whilst numbers no less than A[r] on the righ side
3. Repeat the step2, until there is only one element on the left and right side.
• Time complexity: $O(n \log n)$

## Bucket sort

Bucket Sort is a kind of non-comparison sorting algorithms.

### Count Sort

Process:

1. find the maximum $k$ of the array, and create $k+1$ new buckets
2. Traverse the array for one pass, put the elements into the buckets
3. Traverse all the buckets, take the values from buckets.

## Dutch national flag problem

Dutch national flag problem:

• Given an array with $n$ objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.[1][4]

### 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:

1. Input: array A with values 0,1,2, mid value 1
2. Initilize $i \leftarrow 0, j \leftarrow 0, n \leftarrow sizeof(A)-1$
3. while j<=n:
1. if A[j] < mid:
1. swap A[i] and A[j]
2. $i \leftarrow i+1$
3. $j \leftarrow j+1$
2. else if A[j] > mid:
1. swap A[j] and A[n]
2. $n \leftarrow n-1$
3. else:
1. $j \leftarrow j+1$
• Time complexity: $O(n)$
• Space complexity: $O(1)$

# References

1. 1.
2. 2.
3. 3.
4. 4.
5. 5.
6. 6.Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms, Third Edition.
7. 7.