# Sorting Algorithms

## Algorithm Properties

In-place refers to memory usage. An in-place algorithms needs only constant ($$O(1)$$) memory beyond the items being sorted. In-place sorting algorithms usually work within and overwrite the input array. Note that sometimes $$O(\log{}n)$$ additional memory is considered in-place.

A stable sorting algorithm maintains the relative order of the input. For example, suppose one has an array of people. Each person has an age and a name. Using a stable sorting algorithm, the array is sorted first on age, then on name. When you look at the cluster of people named "John," you'll notice that they are still organized by age.

## Algorithms

### Bubble Sort

#### Overview

Bubble sort compares adjacent neighbors, and if out of order, exchanges them. At the end of the first pass, the largest is at the end. Sorting usually requires passes proportional to the input.

 Best Complexity $$O(n)$$ Average Complexity $$O(n^2)$$ Worst Complexity $$O(n^2)$$ Memory Usage In-place ($$O(n)$$) Stability Stable

#### Implementation

def bubble_sort(list):
while True:
modified = False
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
list[i], list[i + 1] = list[i + 1], list[i]
modified = True
if not modified:
return list


### Selection Sort

#### Overview

Selection sort maintains a sorted and an unsorted portion of the list. Initially the sorted portion is of length zero. Each iteration of the algorithm selects the smallest element in the unsorted portion and places it at the end of the sorted portion.

 Best Complexity $$O(n^2)$$ Average Complexity $$O(n^2)$$ Worst Complexity $$O(n^2)$$ Memory Usage In-place ($$O(n)$$) Stability Stable

#### Implementation

def selection_sort(list):
for i in range(len(list)):
for j in range(i, len(list)):
if list[i] > list[j]:
list[i], list[j] = list[j], list[i]
return list


### Insertion Sort

#### Overview

Just like selection sort, insertion sort maintains a sorted and an unsorted portion of the list. Initially the sorted portion is of length zero. Each iteration of the algorithm takes the first element in the unsorted portion and inserts it into the correct location in the sorted portion.

 Best Complexity $$O(n)$$ Average Complexity $$O(n^2)$$ Worst Complexity $$O(n^2)$$ Memory Usage In-place ($$O(n)$$) Stability Stable

#### Implementation

def insertion_sort(list):
for i in range(len(list)):
for j in range(i, 0, -1):
if list[j] < list[j - 1]:
list[j], list[j - 1] = list[j - 1], list[j]
else:
break
return list


### Shellsort

#### Overview

Shellsort repeatedly applies another sorting algorithm (usually insertion sort) to subsections of the list. The subsections are defined by a gap sequence. Let's say our list is [x1, x2, x3, x4, x5, x6, x7] and our gap sequence is [3, 1]. In the first pass, Shellsort would have a gap of 3 and therefore sort [x1, x4, x7]. In the second pass, Shellsort would have a gap of 1 and sort [x1, x2, x3, x4, x5, x6, x7] (the entire list).

 Best Complexity Depends on gap sequence Average Complexity Depends on gap sequence Worst Complexity Depends on gap sequence Memory Usage In-place ($$O(n)$$) Stability Unstable

#### Implementation

The following function uses a $$2^k - 1$$ gap sequence. This gap sequence gives the algorithm a complexity of $$O(n)$$.

def shellsort(list):
gaps = [2**k - 1 for k in range(1, int(math.log(len(list) + 1) /
math.log(2)))]
for gap in reversed(gaps):
for i in range(0, len(list), gap):
for j in range(i, 0, -gap):
if list[j] < list[j - gap]:
list[j], list[j - gap] = list[j - gap], list[j]
else:
break

return list


### Mergesort

#### Overview

Mergesort is a divide and conquer algorithm. The algorithm first divides the input into smaller and smaller lists. At the base case (list length = 1) the list is sorted. These sorted sublists are progressively merged until we have sorted the original list.

 Best Complexity $$O(n\log{}n)$$ Average Complexity $$O(n\log{}n)$$ Worst Complexity $$O(n\log{}n)$$ Memory Usage $$O(n)$$ Stability Stable

#### Implementation

def mergesort(list):
if len(list) < 2:
return list
else:
middle = len(list) / 2
left, right = list[:middle], list[middle:]
sorted_left, sorted_right = mergesort(left), mergesort(right)
return merge(sorted_left, sorted_right)

def merge(list1, list2):
"Combine two sorted lists into one sorted list."
to_return = []
while list1 or list2:
if not list1:
to_return.append(list2.pop(0))
elif not list2:
to_return.append(list1.pop(0))
elif list1[0] < list2[0]:
to_return.append(list1.pop(0))
else:
to_return.append(list2.pop(0))


### Quicksort

#### Overview

Like mergesort, quicksort is a divide and conquer algorithm. In mergesort, the hard part is combining the sublists. In quicksort, the hard part is dividing the list. Quicksort first chooses a pivot. The input is then divided into two parts: one with elements smaller than the pivot and one with elements larger than the pivot.

 Best Complexity $$O(n\log{}n)$$ Average Complexity $$O(n\log{}n)$$ Worst Complexity $$O(n^2)$$ Memory Usage Extra $$O(\log{}n)$$ Stability Stable

Extra memory is required for the stack.

#### Implementation

The following implementation uses the leftmost element as the pivot. Unfortunately, this choice produces worst-case performance on sorted lists. Most implementations will therefore select a different pivot.

def quicksort(list):
if len(list) < 2:
return list
else:
pivot = list[0]
left = [x for x in list[1:] if x <= pivot]
right = [x for x in list[1:] if x > pivot]
return quicksort(left) + [pivot] + quicksort(right)


Note that the implementation makes new lists at each logarithmic step. It's possible to implement quicksort with only $$O(\log{}n)$$ extra memory. See the Hoare partition scheme for an approach that progressively switches elements around a central pivot.