View Code? Open in Web Editor
NEW
Python implementation of various searching and sorting algorithms
searching-and-sorting-algorithms's Introduction
Implementation of Searching and Sorting Algorithms in Python
- Search items in sequence.
- Complexity of the sequential search, is O(n).
- Sequential search can be improved by ordering the list in the case when the searched item is absent.
- Take greater advantage of the ordered list.
- Complexity of the sequential search, is O(nlogn)
- A great example of a divide and conquer strategy
- Hash table is a collection of items and aach position of the hash table, often called a slot.
- The mapping between an item and the slot where that item belongs in the hash table is called the hash function.
- Hash function formation methods include folding method, mid-square method, linear probing, quadratic probing etc
- Complexity of the sequential search, is O(1)
- Compares adjacent items and exchanges those that are out of order
- Complexity is O(n^2)
- Makes only one exchange for every pass through the list.
- Complexity is O(n^2)
- Builds the final sorted list one item at a time
- Always maintains a sorted sublist in the lower positions of the list
- Complexity is O(n^2)
- Divide and conquer strategy
- Requires extra space to hold the two halves
- Complexity is O(nlogn)
- Divide and conquer strategy
- Not using additional storage.
- Complexity is O(n^2)
searching-and-sorting-algorithms's People
Contributors
Watchers
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent