Data Structures and Algorithms in Python

Implementations of some Data Structures, with different approaches and some practical applications. Designed to be used as consulting material for those who want to learn about Data Structures and Algorithms and have a preference for the Python programming language.

Here is a checklist of the Data Structures and Algorithms we have or we are planning to add. If you would like to add more to the checklist, just create a Pull Request with your additions and we will review it.

Data Structures:

• Stack: A stack is an abstract data type that serves as a collection of elements, with two main operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that was not yet removed.

• Trie: A trie is an ordered data structure, a type of search tree used to store associative data structures.

• Heap: A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property

• Union-Find

• Graphs: A graph is a non-linear kind of data structure made up of nodes or vertices and edges.

• Linked List: A linked list consists of a data element known as a node. And each node consists of two fields: one field has data, and in the second field, the node has an address that keeps a reference to the next node.

Algorithms:

Sorting Algorithms:

• Bubble Sort: A sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed

• Heap Sort: A comparison-based sorting technique based on Binary Heap data structure. Is used when the smallest (shortest) or highest (longest) value is needed instantly

• Merge Sort: A sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array

• Quick Sort: A divide and sort algorithm

• Insertion Sort: A simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons.

• Selection Sort: An effective and efficient sort algorithm based on comparison operations.

• Radix Sort: A non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix.

• Counting Sort: A a sorting technique based on keys between a specific range

• Shell Sort: A sorting algorithm that is highly efficient and is based on the insertion sort algorithm

• Bogo Sort: A sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted

• Tim Sort: A hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

• Gnome Sort

Search Algorithms:

• Linear Search: A method for finding an element within a list where sequentially the code checks each element of the list until a match is found or the whole list has been searched.
• Binary Search: A method for finding an element that finds a position of a target value within a sorted array, and compares the target element to the middle element of the array.
• Ternary Search: A search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function

String Algorithms

• Knuth-Morris-Pratt: An algorithm campares character by character from left to right. But whenever a mismatch occurs, it uses a preprocessed table called "Prefix Table" to skip characters comparison while matching.

• Naive: An algorithm used to find the longest palindromic substring in any given string

• Manacher

• Z-Function

Number Theory Algorithms

• Greatest Common Divisor

• Extended Greatest Common Divisor

• Euler's Phi Function

• Eratosthenes Sieve

• Miller-Rabin

• Modular Arithmetics

Algebra/Numerical Algorithms

• Gauss
• Simplex
• Simpson
• Fast Fourier Transform

Graph Algorithms:

• Breadth-First Search
• Depth-First Search

Contributing

We would love to see you contribute to this project. No matter if it is fixing a bug, adding some tests, improving documentation, or implementing new algorithms and data structures. See CONTRIBUTING.md so you can have a better understanding of our contribution guidelines.