#011 DS&A - Sorting
Tags: computerscience, datastructures, algorithms
Published: 2020-10-08 19:38:26

## Sorting Techniques

### Insertion sort algorithm and analysis

```pseudocode
Insertion-sort(A)
{
	for j = 2 to A.length
		key = A[j]
		// insert A[j] into sorted sequence A[1...j-1]
		i = j-1
		while(i>0 and A[i] > key)
			A[i+1] = A[i]
			i = i-1
		A[i+1] = key
}
```

every time you visit an element you check the one before it if it's greater swap them , if their is a swap you compare the new element with old elements in array.

Worst case is `Teta(n^2)` is if the sorted list is backward sorted from biggest to lowest  , and best case is `Omega(n)` if array is already sorted , and space complexity is `O(1) ` called `inplace` which mean we don't use extra spaces.

We can't optimize it if we apply binary searching the comparison between new element and old elements is `O(log n)` and movement required is `O(n)` , in doubly linked list it require `O(n)` for comparison and `O(1)` for movement. In both cases we have bottleneck to `O(n)`

### Merge sort algorithm and analysis

```pseudocode
MERGE(A, p , q , r)
{
	n1 = q-p+1
	n2 = r-q
	let L[1...n+1] and R[1 to n2+1] be the new arrays
	for(i=1 to n1)
		l[i] = A[p+i-1]
	for(j=1 to n2)
		R[j] = A[q+j]
	L[n1+1] = inf
	R[n2+1] = inf
	i = 1 , j = 1
	for(k = p to r)
		if(L[i] <= R[j])
			A[k] = L[i]
			i=i+1
		else
			A[k] = R[j]
			j=j+1
}
// A is array , p is start index , q is end of sorted arr1 index , r is last index
```

The merge here work having a main array contain 2 sorted arrays inside of it

| 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1    | 5    | 7    | 8    | 2    | 4    | 6    | 9    |

this will be divided into 2 arrays `L` and `R` 
`L` from `p` to `q`

| 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- |
| 1    | 5    | 7    | 8    | Inf    |
`R` from `q+1` to `r`

| 0    | 1    | 2    | 3    | 4    |
| ---- | ---- | ---- | ---- | ---- |
| 2  | 4   | 6   | 9  | Inf    |

after dividing the main array to 2 it will start to compare `R[j]` with `L[i]` if will increment the index of the lower like if `L[i] < R[j]` `i` will be incremented by `1` , and inserting them into array , and note that `Inf` here is large number with same type of data.

then array will become

| 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1    | 2    | 4    | 5    | 6    | 7    | 8    | 9    |

this algorithm will take `O(n)` for dividing arrays and `n+n` to copy elements back to array is `O(n)` so time taken is `O(n)`

space complexity is `O(n)` also.

```pseudocode
merge-sort(A, p , r) - T(n)
{
	if p<r
		q=L[(p+r)/2]
		merge-sort(A,p,q) - T(n/2)
		merge-sort(A,q+1,r) - T(n/2)
		merge(A,p,q,r) - O(n)
}
```

![Merge-sort-example-300px.gif](https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)

the size of stack required for merge-sort is `log(n)+1` so space complexity is `o(log n)` and merge will require is `O(n)` so total is `O(n) + O(log n)` which `n` is dominated so `O(n)` is space complexity.

`T(n) = 2*T(n/2)+O(n) = O(n*log(n)` we use here the master theorem to calculate time complexity

so what ever is the size of problem it will always take `O(n*log(n))` 

### Quick sort algorithm and analysis

```pseudocode
PARTITION(A,p,r)
{
	x = A[r]
	i = p-1
	for(j=p to r-1)
	{
		if(A[j] <= x)
		{
			i=i+1
			exchange A[i] with A[j]
		}
	}
	exhange A[i+1] with A[r]
	return i+1
}
```

Partition algorithm is about putting the last element of array in it's right place where left of it are values which less (no sorted) of it's value and right is greater (not sorted) . Since the `for` will loop  `n` times so time complexity will be `O(n)`



```pseudocode
QUICKSORT(A,p,r) - T(n)
{
	if(p<r)
	{
		q = PARTITION(A,p,r) - O(n)
		QUICKSORT(A,p,q-1) - T(n/2)
		QUICKSORT(A,q+1,r) - T(n/2)
	}
}
```

![Sorting quicksort anim.gif](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)

![img](https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Quicksort-diagram.svg/200px-Quicksort-diagram.svg.png)

it will keep sub-Quick-sorting and return every time it will face  `p==r` or  `p>r` 

worst space complexity is `O(n)` and average is `O(log n)`

time complexity is `T(n)=2*T(n/2)+O(n) = Teta(n log(n) )`  using the master theorem

the worst case is where the number the last element is in the right order.

time complexity will be

```
T(n) = T(n-1) + O(n)
	 = T(n-1)+cn
	 = T(n-2)+c*(n-1)+c*n
	 = T(n-3)+c*(n-2)+c(n-1)+c*n
	 ...
	 = c+2c+3c+...+c*n
	 = O(n^2)
```

### Introduction to heaps

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/1280px-Max-Heap.svg.png" alt="img" style="zoom: 33%;" />

heap trees are is a binary tree or 3-ary tree or n-ary tree.

let's talk about binary tree heap only , heap have their root is max heap and all nodes sub-tree should be smaller than the parent node.

A complete Binary tree of height **h** has 2h-1 nodes. Out of these 2h-1 are leaf nodes and rest (2h-1-1 are non-leaf)

![complete binary tree](https://www.ritambhara.in/wp-content/uploads/2016/06/complete-binary-tree.png)

![complete binary tree_1](https://www.ritambhara.in/wp-content/uploads/2016/06/complete-binary-tree_1.png)

### Canonical labeling of nodes

Label the Nodes in the level-wise fashion from left to right, as shown below:
 ![canonically labeled](https://www.ritambhara.in/wp-content/uploads/2016/06/canonically-labeled.png)
 The advantage of canonical labeling is that such a tree can be stored in an array where value of a node is stored at the index equal to its  label in the tree.
 ![Binary heap](https://www.ritambhara.in/wp-content/uploads/2016/06/Binary-heap.png)
 This way we will save a lot of memory because we do not need to store  all the pointers. If you have noticed, there is a relationship  between the labels of a node and its children above:
 ![Binary heap_1](https://www.ritambhara.in/wp-content/uploads/2016/06/Binary-heap_1.png)

`2*a` is nothing but left shifting , so it's easy to implement in computer. `10` is a binary number represent `2` in decimal if i left shift it  it will become `100` which is `4` in decimal.

This way, it becomes easy to move in either upward or downward direction of a tree, even when it is stored in an array.

![almost complete binary tree](https://www.ritambhara.in/wp-content/uploads/2016/06/almost-complete-binary-tree.png)

Below trees are **NOT** almost complete binary trees (the labeling has no meaning, because there are gaps).
 ![NOT almost complete binary tree](https://www.ritambhara.in/wp-content/uploads/2016/06/NOT-almost-complete-binary-tree.png)

-- [source](https://www.ritambhara.in/almost-complete-binary-tree/)

The input of an Algorithm affect the time complexity a lot let's take those cases

|                      | insert   | search   | find min | delete      |
| -------------------- | -------- | -------- | -------- | ----------- |
| unsorted array       | O(1)     | O(n)     | O(n)     | O(n)        |
| sorted array         | O(n)     | O(log n) | O(1)     | O(n)        |
| unsorted linked list | O(1)     | O(n)     | O(n)     | O(n+1)=O(n) |
| min heap             | O(log n) |          | O(1)     | O(log n)    |

### Max heapify algorithm and complete binary tree

to build A heap in first place we should re-arrange it in a way that the parent always bigger than children.

```pseudocode
max-HEAPIFY(A,i)
{
    l = 2*i;
    r = 2*i+1;
    largest = i;
    
    if(l <= A.heap-size and A[i] > A[i]) largest = l; // check if it's have a left child 
    if(r <= A.heap-size and A[r] > A[largest]) largest = r; // check if it's have a right child
    if(largest != i)
    {
    	exchane A[i] with A[largest]
    	max-HEAPIFY(A,largest)
    }
}
```

the heart of this Algorithm is if we have sub-trees are max-heap but we need to make the root max-heap also.

![https://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module2/images/Heaps_Heapify.png](https://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module2/images/Heaps_Heapify.png)

time complexity is `O(log n)` which is the height of the tree , space complexity is the number of recursive calls `O(log n)`

### Build max heap algorithm and analysis

```pseudocode
BUILD-max-heap(A)
{
	A.heap-size = A.length
	for( i = floor(A.length/2) down to 1) 
		max-HEAPIFY(A,i)
}
```

take this array `A` as an example `9,6,5,0,8,2,1,3`

![image-20200929063938553](https://i.loli.net/2020/09/29/hAHJLKq7Y8skxMp.png)

length of `A` is 8 `floor(8/2)+1 = 4+1 = 5` (we add 1 because we start from 1 not 0)

so from index 5 to 1 we need to apply `max-HEAPIFY(A,i)` , index 5 is already a leaf so nothing to do go to index 4 `0<8` so swap them

![image-20200929064304354](https://i.loli.net/2020/09/29/D5gVrRZvGCUFwxL.png)

then in index`3` we have `5 > 2 > 1` so nothing to do , go to index `2` we have `6<8` so swap

![image-20200929064415220](https://i.loli.net/2020/09/29/U4macJExoQGN5fK.png)

and index 1 is already the biggest so nothing to do.

what is the total time taking to build this max-HEAP ?

height of tree is `log n` and we are applying it n times so you will think that will take `O(n log n)` but it's not the time complexity is not the way to do it.

the number of nodes at height ![h](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)  is ![{\displaystyle \leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5051ad1ea862f8357779fc9ad08e03be88ec7fbf)

Therefore, the cost of heapifying all subtrees is:

![{\displaystyle {\begin{aligned}\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {n}{2^{h}}}O(h)&=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {h}{2^{h}}}\right)\\&=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b1f5dac83f79e16b8794611e4b4a91594c422d8)

where ![image-20200929065158664](https://i.loli.net/2020/09/29/aEbUMAHt6x2VdNz.png) is nothing than 2 (there is a proof for this)

and for space complexity required will be `O(log n)` 

### Extract max from heap

```pseudocode
Heap-extract-max()
{
	if A.heap-size < 1
		error "heap underflow"
	max = A[1]
	A[1] = A[A.heap-size]
	A.heap-size = A.heap-size - 1
	max-HEAPIFY(A,1)
	return max
}
```

Now that we have the Heapify procedure, the Extract-Max procedure isn't hard to define at all. Suppose we have the following heap.



![img](https://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/extract-1.gif)

Extracting the node with maximum value is easy enough - by the definition of a heap, it is at the top. So we return it. Fine. Now the question is how to turn what remains,



![img](https://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/extract-2.gif) ,

back into a heap. We can almost run the heapify procedure on the whole thing, except that we have *two* complete binary trees, not one.

So we move the node at the bottom right to the top.



![img](https://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/extract-4.gif)

Now we can perform the Heapify procedure on the whole tree.

time taking is `O(log n)` and same for space.

### Heap - increase key

```pseudocode
Heap-Increase-Key(A, i, key)
// Input: A: an array representing a heap, i: an array index, key: a new key greater than A[i]
// Output: A still representing a heap where the key of A[i] was increased to key
// Running Time: O(log n) where n =heap-size[A]
1 if key < A[i]
2 	error(“New key must be larger than current key”)
3 A[i] ← key
4 while i > 1 and A[Parent(i)] < A[i]
5 	exchange A[i] and A[Parent(i)]
6 	i ← Parent(i)
```

because it's increase a key we don't need from our key to be less than element so we return error, and we loop until we reach the root , and for every node we see it's parent if it's less or bigger than the key we exchange it.

if we need to decrease a node we need to max-heapify for the tree in that node , which in worst case will take `O(log n)`

### Heap Sort

```pseudocode
HEAP-sort(A)
{
	BUILD-max-HEAP(A)
	for(i = A.length down to 2)
	{
		exchange A[1] with A[i]
		A.heap-size = A.heap-size-1
		max-HEAPIFY(A,1)
	}	
}
```

we are running max-HEAPIFY `n` times so time complexity is `O(n * log(n))` where `log n` is time complexity of max-HEAPIFY

### Bubble sort

```c
BubleSort(int a[] , n)
{
    int swapped,i,j;
    for(i=0;i<n;i++) {
        swapped = 0;
        for(j=0 ; j<n ; j++) {
            if(a[j] < a[j+1]){
                swap(a[j] , a[j+1]);
                swapped = 1;
            }
        }
        if(swapped == 0) break;
    }
}
```

![Bubble sort algorithm](https://www.studytonight.com/data-structures/images/basic-bubble-sort.png)

the worst case is reversed sorted array which is `O(n^2)`

and average case is `O(k*n)` and best case is `O(n)`

### Bucket sort

bucket sort generally use to solve kind of problem where numbers are float and range from `a` to `b` with `a` and `b` are float.

`0.35 , 0.12 , 0.43 , 0.15 , 0.04 , 0.50 , 0.132`

![image-20201008134820976](https://i.loli.net/2020/10/08/agUnzTSv7K2DyfR.png)

it will take first number `.` and put it in it's place if is already an element there it will sort them then printing them in order.

`0.04 , 0.12 , 0.132 , 0.15 , 0.35 , 0.43 , 0.50`

in best case where the numbers will be inserted without need to sort to place new item in cell so every insertion will take `O(1)` , so all the insertion will take `O(n)` and space complexity will be `O(n+k)` 

the worst case `O( (n/k) * n ) = O(n^2)`

### Counting sort

Counting sort have restrictions to apply , the restriction is that the input is in a range.

let's say our range is from `1` to `5`

so we will take an array of 5 elements `2 2 3 4 1 5 1 5`

| INDEX | appearance |
| ----- | ---------- |
| 1     | 2          |
| 2     | 2          |
| 3     | 1          |
| 4     | 1          |
| 5     | 2          |

then we print them in order ` 1 1 2 2 3 4 5 5`

time complexity is`O(n+k)` and space complexity is `O(k)`

the disadvantage we can not go outside range and if the range is big , and the elements are few

`1 1000 2 3` so the amount of space we need is `1000` for only `4` elements.

 ### Radix sort

Do following for each digit i where i varies from least significant digit to the most significant digit. 

- Sort input array using counting sort (or any stable sort) according to the i’th digit.

**Example**

Original, unsorted list:
`170, 45, 75, 90, 802, 24, 2, 66`

Sorting by least significant digit (1s place) gives: 
[*Notice that we keep 802 before 2, because 802 occurred 
before 2 in the original list, and similarly for pairs 
170 & 90 and 45 & 75.]

Sorting by next digit (10s place) gives: 
[*Notice that 802 again comes before 2 as 802 comes before 
2 in the previous list.]

`802, 2, 24, 45, 66, 170, 75, 90`

Sorting by the most significant digit (100s place) gives:
`2, 24, 45, 66, 75, 90, 170, 802`


![scene00577](https://media.geeksforgeeks.org/wp-content/cdn-uploads/scene00577.jpg)

 

![scene00649](https://media.geeksforgeeks.org/wp-content/cdn-uploads/scene00649.jpg)

 ![scene00793](https://media.geeksforgeeks.org/wp-content/cdn-uploads/scene00793.jpg)
 ![scene01009](https://media.geeksforgeeks.org/wp-content/cdn-uploads/scene01009.jpg)
 ![scene01225](https://media.geeksforgeeks.org/wp-content/cdn-uploads/scene01225.jpg)

Let there be d digits in input integers. Radix Sort takes `O(d*(n+b))`  time where `b` is the base for representing numbers, for example, for the  decimal system, `b` is 10. What is the value of `d`? If `k` is the maximum  possible value, then `d` would be `O(logb(k))`. So overall time complexity is `O((n+b) * logb(k))`. Which looks more than the time complexity of comparison-based sorting  algorithms for a large `k`. Let us first limit `k`. Let `k <= nc` where `c` is a constant. In that case, the complexity becomes `O(nLogb(n))`. But it still doesn’t beat comparison-based sorting algorithms. 
What if we make the value of `b` larger?. What should be the value of b to  make the time complexity linear? If we set `b` as `n`, we get the time  complexity as `O(n)`. In other words, we can sort an array of integers  with a range from `1` to `nc` if the numbers are represented in base `n` (or every digit takes `log2(n)` bits). 

-- [source](https://www.geeksforgeeks.org/radix-sort/)