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
Return type: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
Return type: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
Return type: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
Return type: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
Return type: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
Return type: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
Return type: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
Return type: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
Return type:

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
Return type: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
Return type: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
Return type:

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
Return type:

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
Return type: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
Return type: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
Returns:

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