Sorting Algorithms & Data Structures
Project description
cs-algorithms
Goal
The main goal is to familiarize with common Algorithms and Data Structures. Folowing an added benefit is that this code will be accessible and re-useable.
Currently Implemented
Numbers:
Fibonacci Sequence
The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
Fn = Fn-1 + Fn-2
with seed values
F0 = 0 and F1 = 1.
Sorting Algorithms:
Is Sorted
Check if a given array is sorted (works for ascending and descending order).
Bubble Sort (Original)
Repeatedly swapps adjacent elements if they are in wrong order. (uses two nested for loops)
Bubble Sort (Optimized)
Repeatedly swapping the adjacent elements if they are in wrong order (stops when array is sorted).
Selection Sort
Repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
Insertion Sort
The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Merge Sort
It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
Quick Sort
It picks an element as pivot and partitions the given array around the picked pivot.
Search Algorithms:
Linear Search
Start from the leftmost element of arr[] and one by one compare x with each element of arr[] If x matches with an element, return the index. If x doesn’t match with any of elements, return -1.
Binary Search (Iterative)
Search a sorted array by repeatedly dividing the search interval in half. Begin wiht an intreval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the intreval to the lower half. Otherwise narrow it to the upper half. Repaetadly check until the value is found or the interval is empty.
Binary Search (Recursive)
See Binary Search (Iterative).
Jump Search
The basic idea is to check fewer elements by jumping ahead fixed steps or skipping some elements in place of searching all elements.
Interpolation Search
The Interpolation Search is an improvement over the Binary Search for instance, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle elemnt to check. On the other hand, Interpolation Search may go to different positions according to the value of the key being searched.
Exponential Search
The idea is to start with subarray size 1, compare its element with the key value, then try size 2, then try size 4 and so on until the last element of subarray is not greater. Once we find an index i, we know that the element must be present between i/2 and i.
Fibonacci Search
The idea is to find the smallest Fibonacci number that is greater than or equal to the length of the given array. Let the found Fibonacci number be fib. We can use the (m-2)'th Fibonacci number as the index. Let (m-2)'th Fibonacci number be i, we compare arr[i] with the key value. If the key value is same, we return i. Else if the key value is greater, we recur for subarray after i, else we recur for the subarray before i.
Data Structures:
Queue
Stack
Binary Tree
Binary Search Tree
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for cs_algorithms-0.0.4-py3-none-any.whl
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | bbd4d8c491678e43c26ca464232ceaa83840777313faf24014b47b6b23943c1f |
|
| MD5 | ce9369e9f85500c96658a25b9dcad179 |
|
| BLAKE2b-256 | 9595ee1481c0bf34bbd8b6c7ff2d1d7316c0770f45ead33ba8059877ea94d66f |
