pyalo

This project implements some of popular search and sort algorithms. This is on-going project; more algorithms and improvements will be added in the future.

Documentation

Substring search

There are 3 substring search algorithms are currently implemented which are Knuth-Morris-Patt, Boyer More and Rabin Karp.

Knuth-Morris-Patt algorithm

kmp_search(text, pattern) Return the index of the first occurrence of the pattern in the text. If the pattern does not exist, return -1.

Example

>>> from pyalgo import search
>>> text = "ABBAACBCB"
>>> search.kmp_search(text, "ACDCB")
4
>>> search.kmp_search(text, "EDEF")
>>> -1

Rabin-karp algorithm

rabin_karp_search(text, pattern, q=37) Return the index of the first occurrence of the pattern in the text. If the pattern does not exist, return -1. q is the modular constant. Setting q to a large prime to avoid collisions. Default value of q is 37

Example

>>> from pyalgo import search
>>> text = "ABBAACBCB"
>>> search.rabin_karp_search(text, "ACDCB")
4
>>> search.rabin_karp_search(text, "EDEF")
>>> -1

Boyer-Moore algorithm

boyer_moore_search(text, pattern) Return the index of the first occurrence of the pattern in the text. If the pattern does not exist, return -1.

Example

>>> from pyalgo import search
>>> text = "ABBAACBCB"
>>> search.boyer_moore_search(text, "ACDCB")
4
>>> search.boyer_moore_search(text, "EDEF")
>>> -1

Sort

There are 4 sorting algorithms are implemented: merge sort, heap sort, quick sort and insertion sort

Heap sort

heap_sort(array, compare=lambda x, y: x > y) Return the sorted array. The order depends on the compare function. Best: O(n log n)

Worst: O(n log n)

Avg: O(n log n)

Example

>>> from pyalgo import serial_sort
>>> array = [1, 0, 2, 4, 5, 10, 8, 6, 3, 7, 9]
>>> serial_sort.heap_sort(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Quick sort

quick_sort(array, compare=lambda x, y: x > y) Return the sorted array. The order depends on the compare function. Best: O(n log n)

Avg: O(n log n)

Worst: O(n^2)

Example

>>> from pyalgo import serial_sort
>>> array = [1, 0, 2, 4, 5, 10, 8, 6, 3, 7, 9]
>>> serial_sort.quick_sort(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Merge sort

merge_sort(array, compare=lambda x, y: x > y) Return the sorted array. The order depends on the compare function. Best: O(n log n)

Avg: O(n log n)

Worst: O(n log n)

Example

>>> from pyalgo import serial_sort
>>> array = [1, 0, 2, 4, 5, 10, 8, 6, 3, 7, 9]
>>> serial_sort.merge_sort(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Insertion sort

insertion_sort(array, compare=lambda x, y: x > y) Return the sorted array. The order depends on the compare function.

Best: O(n)

Avg: O(n^2)

Worst: O(n^2)

Example

>>> from pyalgo import serial_sort
>>> array = [1, 0, 2, 4, 5, 10, 8, 6, 3, 7, 9]
>>> serial_sort.insertion_sort(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]