# Sorting Algorithms¶

Module containing the most common sorting algorithms
• bubble sort
• selection sort
• insertion sort
• shell sort
• quicksort
• merge sort
• heapsort

For the record, Python built-in sorted uses by default timsort which is a hybrid stable sorting algorithm, running in O(n) for best case (list already sorted) to O(n log n). It does so by taking advantage of the fact that real-life lists often have some partial ordering.

`src.classic_algo.sort.``bubble_sort`(a)[source]

In this algo, the i-th pass starts at the first element and compare sequencially each element to the next, swapping them if necessary, up to n-i. The biggest element ‘bubbles up’ to the n-i position. This runs in O(n^2): n-1 passes of O(n) comparisons.

Note the use of the pythonic swap operation “a, b = b, a”, not requiring the use of a temporary storage variable.

`src.classic_algo.sort.``heap_sort`(list_to_order)[source]
`src.classic_algo.sort.``insertion_sort`(a)[source]

The insertion sort uses another strategy: at the i-th pass, the i first terms are sorted and it inserts the i + 1 term where it belongs by shifting right all elements greater one notch right to create a gap to insert it. It also runs in O(n^2)

`src.classic_algo.sort.``merge`(a, b)[source]

helper function used by merge_sort combines two sorted lists into one sorted list

`src.classic_algo.sort.``merge_sort`(a)[source]

Based on the divide and conquer approach, this algorithm runs in O(n log n). The array is split by the middle and each half is recursively sorted using merge_sort. The two sorted halves are then efficiently merged using the helper function above.

`src.classic_algo.sort.``partition_helper`(a, first, last)[source]

A left_mark index are initiated at the leftmost index available (ie not the pivot) and a right_mark at the rightmost. The left_mark is shifted right as long as a[left_mark] < pivot and the right_mark left as long as a[right_mark] > pivot. If left_mark < right_mark, the values at which the marks are stopped are swaped and the process continues until they cross. At this point, a[right_mark] and the pivot are swapped and the index of the right_mark is returned.

`src.classic_algo.sort.``quick_sort`(a)[source]

Another divide and conquer algorithm, quick sort relies on choosing a pivot value. The list is then partitioned using the scheme described in partition_helper. This placed the pivot in its correct position in the sorted list, the function is then called on the sublist a[:right_mark - 1] and a[right_mark+1:]

`src.classic_algo.sort.``quicksort_helper`(a, first, last)[source]

Helper function splitting the list at the pivot and recursively calling itself on the left and right parts of this splitpoint.

`src.classic_algo.sort.``selection_sort`(a)[source]

Swapping values can be an expensive operation. At the i-th pass, the selection sort finds the largest values and swap it with the value at n - i performing faster than bubble sort. Note this can be shortened same as above (not shown here for clarity)

`src.classic_algo.sort.``shell_sort`(list_to_order)[source]
`src.classic_algo.sort.``short_bubble_sort`(a)[source]

Variant of the short bubble, taking advantage of the fact we know that if no value has been swaped, the list is sorted and we can return early.