# Sorting¶

## Bogo Sort¶

A naive sorting that picks two elements at random and swaps them.

Time Complexity: O(n * n!)

Space Complexity: O(1) Auxiliary

Stable: No

Psuedo code: None

WARNING: This algorithm may never sort the list correctly.

`algorithms.sorting.bogo_sort.``is_sorted`(seq)[source]

Takes a list of integers and checks if the list is in sorted order.

Parameters: seq – A list of integers Boolean
`algorithms.sorting.bogo_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Bubble Sort¶

A naive sorting that compares and swaps adjacent elements.

Time Complexity: O(n**2)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo code: http://en.wikipedia.org/wiki/Bubble_sort

`algorithms.sorting.bubble_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Cocktail Sort¶

A bidirectional bubble sort. Walks the elements bidirectionally, swapping neighbors if one should come before/after the other.

Time Complexity: O(n**2)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo Code: http://en.wikipedia.org/wiki/Cocktail_sort

`algorithms.sorting.cocktail_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Comb Sort¶

Improves on bubble sort by using a gap sequence to remove turtles.

Time Complexity: O(n**2)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo code: http://en.wikipedia.org/wiki/Comb_sort

`algorithms.sorting.comb_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Gnome Sort¶

A sorting algorithm similar to insertion sort except that the element is moved to its proper place by a series of swaps.

Time Complexity: O(n**2)

Space Complexity: O(1) auxillary

Stable: No

Psuedo code: http://en.wikipedia.org/wiki/Gnome_sort

`algorithms.sorting.gnome_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Heap Sort¶

Uses the max heap data structure implemented in a list.

Time Complexity: O(n log n)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

`algorithms.sorting.heap_sort.``build_heap`(seq)[source]

Continously calls max_heapify on the list for each subtree.

Parameters: seq – A list of integers
`algorithms.sorting.heap_sort.``max_heapify`(seq, i, n)[source]

The function of max_heapify is to let the value at seq[i] “float down” in the max-heap so that the subtree rooted at index i becomes a max-heap.

Parameters: seq – A list of integers i – An integer that is an index in to the list that represents the root of a subtree that max heapify is called on. n – length of the list
`algorithms.sorting.heap_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Insertion Sort¶

A sort that uses the insertion of elements in to the list to sort the list.

Time Complexity: O(n**2)

Space Complexity: O(n) total

Stable: Yes

Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

`algorithms.sorting.insertion_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of integers

## Merge Sort¶

Uses divide and conquer to recursively divide and sort the list

Time Complexity: O(n log n)

Space Complexity: O(n) Auxiliary

Stable: Yes

Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

`algorithms.sorting.merge_sort.``merge`(left, right)[source]

Takes two sorted sub lists and merges them in to a single sorted sub list and returns it.

Parameters: left – A list of sorted integers right – A list of sorted integers A list of sorted integers
`algorithms.sorting.merge_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Quick Sort¶

Uses partitioning to recursively divide and sort the list

Time Complexity: O(n**2) worst case

Space Complexity: O(n**2) this version

Stable: No

Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

`algorithms.sorting.quick_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Quick Sort in Place¶

Uses partitioning to recursively divide and sort the list

Time Complexity: O(n**2) worst case

Space Complexity: O(log n) this version

Stable: No

Psuedo Code: http://rosettacode.org/wiki/Quick_Sort

`algorithms.sorting.quick_sort_in_place.``partition`(seq, left, right, pivot_index)[source]

Reorders the slice with values lower than the pivot at the left side, and values bigger than it at the right side. Also returns the store index.

Parameters: seq – A list of integers left – An integer representing left index right – An integer representing left index pivot_index – An integer that we’re pivoting off An stored_index integer
`algorithms.sorting.quick_sort_in_place.``sort`(seq, left, right)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers left – An integer representing the beginning index right – An integer representing the end index A list of sorted integers

## Selection Sort¶

A sorting that uses in-place comparison.

Time Complexity: O(n**2)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo Code: http://en.wikipedia.org/wiki/Selection_sort

`algorithms.sorting.selection_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers

## Shell Sort¶

Comparision sort that sorts far away elements first to sort the list

Time Complexity: O(n**2)

Space Complexity: O(1) Auxiliary

Stable: Yes

Psuedo Code: http://en.wikipedia.org/wiki/Shell_sort

`algorithms.sorting.shell_sort.``sort`(seq)[source]

Takes a list of integers and sorts them in ascending order. This sorted list is then returned.

Parameters: seq – A list of integers A list of sorted integers
`algorithms.data_structures.lcp_array.``lcp_array`(t_str, s_array, rank)[source]
Parameters: t_str – the string to calculate the lcp array for s_array – the suffix array of the string rank – the suffix array reversed the lcp array
`algorithms.data_structures.lcp_array.``suffix_array`(t)[source]

Suffix array of a string t :param t: the string to extract suffix array from :return (s_array, rank): return a tuple that contain the suffix array and the rank array which is the reversed version of the suffix array