# Sorting

Here are implementations of a few array sorting algorithms.

```
a = list('sortingexample')
```

### 1. Selection Sort

- Iteratively put the ith smallest element at ith location from the left.
- We maintain a sorted section from the left.
- In each iteration, we expand the sorted section by swap the smallest element from the unsorted section into the location.

```
def selection_sort(a):
n = len(a)
for i in range(n):
s = i
for j in range(i + 1, n):
if a[j] < a[s]:
s = j
a[i], a[s] = a[s], a[i]
```

### 2. Bubble Sort

- Iteratively put the ith largest element to ith location from the end.
- We maintain a sorted seciton from the right.
- In each iteration, we compare adjacent pairs of elements and swap larger values to the right until we reach the sorted part.
- Bubble sort can have O(N) best case time complexity, with a bit more code to detect if the array is sorted and terminates early.

```
def bubble_sort(a):
n = len(a)
for i in range(1, n):
swapped = False
for j in range(n - i):
if a[j] > a[j + 1]:
a[j + 1], a[j] = a[j], a[j + 1]
swapped = True
if not swapped: break
```

### 3. Insertion Sort

- Iteratively insert new element into the sorted part.
- We maintain a sorted section from the left.
- In each iteration, we sink one new element from the right to the correct location in the sorted part.

```
def insertion_sort(a):
n = len(a)
for i in range(n):
for j in range(i, 0, -1):
if a[j] < a[j - 1]:
a[j - 1], a[j] = a[j], a[j - 1]
```

### 4. Merge Sort

- Recursively divide the array into two halves, sort both(recursively) and then merge the two sorted array.
- It follows the Divide-and-Conquer paradigm.

```
# A quick and dirty non-inplace version
def merge_sort(a):
def merge(left, right):
merged = []
while left and right:
merged.append(left.pop() if left[-1] > right[-1] else right.pop())
merged.extend(left + right)
return merged[::-1]
if len(a) <= 1: return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right)
# A in place version
def merge_sort(a):
temp = a.copy()
def merge(low, mid, high):
for i in range(low, high + 1):
temp[i] = a[i]
i, j = low, mid + 1
for k in range(low, high + 1):
if i > mid:
a[k] = temp[j]
j += 1
elif j > high:
a[k] = temp[i]
i += 1
elif temp[j] < temp[i]:
a[k] = temp[j]
j += 1
else:
a[k] = temp[i]
i += 1
# bottom-up version
# n = len(a)
# step_size = 1
# while step_size < n:
# for low in range(0, n, 2 * step_size):
# mid = low + step_size - 1
# high = min(n - 1, low + 2 * step_size - 1)
# merge(low, mid, high)
# step_size *= 2
# # top-down version
def _merge_sort(low, high):
if low >= high: return
mid = (low + high) // 2
_merge_sort(low, mid)
_merge_sort(mid + 1, high)
merge(low, mid, high)
_merge_sort(0, len(a) - 1)
```

### 5. Quick Sort

- Pick a random pivot item, put it in the right place by moving items smaller than it to its left and items larger than it to its right.
- Use the pivot item(since its in the right location now), to cut the problem in two halves and recursively sort the whole thing.

```
import random
# an inplace implementation, with random pivot item instead of shuffle and alwasy pick leftmost as pivot.
def quick_sort(a):
def partition(l, h):
if l >= h: return
p = random.randint(l, h)
a[l], a[p] = a[p], a[l]
pivot = a[l]
i, j = l, h
while i < j:
while i < h and a[i] <= pivot: i += 1
while j > l and a[j] >= pivot: j -= 1
if j > i and a[i] > a[j]: a[i], a[j] = a[j], a[i]
a[j], a[l] = a[l], a[j]
return j
def sort(l, h):
if h > l:
j = partition(l, h)
sort(l, j - 1)
sort(j + 1, h)
sort(0, len(a) - 1)
```

### 6. Heap Sort

- Heapify the array then poping item one at a time.
- See Heap section for how heap works.