# Algorithms: Sorting

High level review of classic sorting algorithms with Haskell.

### What do we mean by Sorted?

For a sorted list, every element is smaller or equals to the next one. From this very definition we can check if a list is sorted by

- Checking that the first element is less than or equal to the next one
- Recursively check that the rest is sorted

```
isSorted [] = True
isSorted [x] = True
isSorted (x0:x1:xs) = (x0 <= x1) && isSorted(x1:xs)
```

### Recursive Sorting algorithms

These sorting algorithms divide the given list into 2 subproblems of roughly the same size. There are two prominent algorithms in this category.

**Merge sort**- uses a linear time algorithm to combine the two sorted lists**Quick sort**- uses a linear time algorithm to partition values into left (less than) and right (more than) a pivot.

### Merge Sort

Given 2 already sorted lists, compare only the first element from both lists. The smaller value got appended to the result. Repeat this process with that smaller value removed from consideration.

```
merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
```

The full merge sort algorithm simply halves a given unsorted list, recursive call to sort each half. Afterward, combining the two sorted halves with the merge algorithm defined above.

```
split :: [a] -> ([a], [a])
split [] = ([], [])
split xs = splitAt (length(xs) `div` 2) xs
mSort :: Ord a => [a] -> [a]
mSort [] = []
mSort [x] = [x]
mSort xs = merge (mSort left) (mSort right)
where
(left, right) = split xs
```

### Quicksort

Here is a classic intro in showing the expressive power of Haskell.

- Uses the first value
`x`

as a pivot point. Loop and separate values into`≤ x`

`>x`

group. - Recursively calls quick sort into the two groups
- join the

,`≤ x`

`x`

, and`>x`

group together

There's no guarantee that the two groups are partitioned into equal sizes. There exists a way to do quick sort in-place without additional memory, however.

```
qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort (x:xs) = qSort(left) ++ [x] ++ qSort(right)
where
left = [y | y <- xs, y <= x]
right = [y | y <- xs, y > x]
```

### Quadratic time sorting algorithms

Also known as O(n^2). These algorithms have a similar outline where the problem size is reduced by 1 per iteration of execution. Each iteration itself takes a linear time, making this O (n^2) in total.

### Selection Sort

Finds a min value from a list, adds to answer, repeats on the remaining list excluding the selected min value.

```
sSort :: Ord a => [a] -> [a]
sSort [] = []
sSort xs = min : sSort(remaining)
where min = minimum xs
remaining = delete min xs
```

### Insertion Sort

Maintain a sorted list (the answer), starting from empty. Insert a new value one element at a time from original lists at the right index in the sorted answer.

```
orderedInsert :: Ord a => a -> [a] -> [a]
orderedInsert a [] = [a]
orderedInsert a (x:xs)
| a < x = a:x:xs
| otherwise = x:(orderedInsert a xs)
iSort :: Ord a => [a] -> [a]
iSort [] = []
iSort (x:xs) = orderedInsert x (iSort xs)
```

### Bubble Sort

Closely related to selection sort. Instead of selecting a max value, bubbles the value as we compare each element.

```
bSort :: Ord a => [a] -> [a]
bSort [] = []
bSort xs = bSort(init bubbled) ++ [last bubbled]
where
bubbled = bubble xs
bubble :: Ord a => [a] -> [a]
bubble [] = []
bubble [x] = [x]
bubble (x0:x1:xs)
| x0 < x1 = x0 : bubble( x1:xs )
| otherwise = x1 : bubble( x0:xs )
```