On this page you will find several notes and code snippets about popular sorting algorithms.

Sort `n`

numbers stored in array `A`

by finding the smallest element of `A`

and
exchanging it with the element in `A[1]`

. Then find the second smallest element
of `A`

and exchange it with `A[2]`

. Continue in this manner for the first ```
n -
1
```

elements of `A`

.

```
for i = 1 to A.length - 1
// sI stands for smallestIndex
sI = i
for j = i + 1 to A.length
if A[j] < A[sI]
sI = j
// swap (if necessary)
if (sI != i)
tmp = A[i]
A[i] = A[sI]
A[sI] = tmp
```

The best-case for this algorithm is an already sorted data
array. The worst-case would be produced by a sorted array with the first element
moved to the last position and all the other elements moved one place to the
left. Note that the only thing that varies is the amount of swaps made, the
algorithm has Θ(n^{2}) time-complexity even for sorted input.

Heapsort is great: it is simple to program and has worst-case O(n log n) (the
best that can be expected from a comparison-based sorting algorithm). It is also
an example of how a data structure can make dramatic algorithmic improvements.
**Heapsort can be thought as a variation of selection sort that uses a priority
queue to
speed up the process**.

Removing an item from an unsorted array – given its index – takes constant time
(because you can write the last element over the element you wish to remove and
reduce the length by one in constant time), whilst finding the minimum of an
unsorted array takes O(n) time (through linear search). This makes selection
sort a O(n^{2}) average-case algorithm, as it finds the minimum **n**
times.

Some data structures provide these operations with better time complexities.
**Heaps** and **balanced binary trees** (these are not *abstract* data
structures, such as the aforementioned priority queue) provide both operations
with O(lg n) time complexity, making the sorting algorithm (that operates on
**n** elements) take O(n lg n) time.

Heaps work by maintaining a partial order of the elements, which is weaker than the sorted order (so it is easier to maintain) yet stronger than random order (so the minimum element can be quickly identified). A min heap establishes that the parent node has a smaller value than its children, while the parent nodes of a max heap dominate by being bigger.

Heaps are slick data structures that enable us to represent binary trees
without using pointers. Specifically, a heap is usually represented as an array
where the positions of the keys implicitly take the roles of pointers. If we
are using a zero-indexed array, the n-th level of the tree starts in the
2^{n-1} - 1 element and ends at the 2^{n} - 2 element. The root
is stored in the first position of the array and its left and right children in
the second and third.

Any binary tree can be stored in an array without the use of pointers. The
downside is that sparse trees end up occupying huge amounts of space as
“missing” nodes still take up space. Space efficiency demands that each level
is as dense as it can be. Therefore, only the last level may be incomplete. It
is possible to store a tree of **n** keys using an array of exactly **n**
elements (as long as all the elements of the last level are packed to the
left).

Representing binary trees using this structure saves memory, but does not allow
some *tricks* such as moving a subtree around by manipulating a single pointer.
This illustrates why arrays are not a good representation for binary search
trees, but a great representation for heaps.

Incremental insertion is the simplest way to construct heaps. Inserting the new
element in the leftmost empty position of the array ensures that the shape of
the tree is correct, but may violate the right ordering of keys. To solve this
problem, some children nodes may need to be swapped with their parents in a
process known as *bubbling up*.

Identifying the dominant element is as simple as getting the first element of
the underlying array. To fill the hole left by the removal of the first element
the rightmost leaf can be used. The new root may eventually be dominated by its
children. In order to fix this, the new root may be swapped with its children
until it dominates all its children, perhaps by becoming a leaf (in a process
know as *bubbling down*). This operation is sometimes called **heapify**, as it
merges two heaps – the subtrees below the old root – with a new key.

There is a faster way to construct heaps than incremental insertion. The core
idea is that, after getting **n** keys to construct a heap from, we just insert
them at the beginning of the array. This makes the right shape for our array
(it is not sparse), but the dominance order may be completely wrong. In order
to fix the dominance order, all we need to do is to call the bubble down
procedure to all elements that are not leaves (trivially, all the leaves are
dominant).
This is faster because it can be proven with analysis that all bubble down
calls are bounded by a constant. As the number of bubble down calls is O(n),
this solution is O(n).

This is my implementation of a priority queue and heapsort using Python 3.