Quick sort can be distributed into two sub-tasks (quick sort left and right partitions) but can be also be distributed into three sub-tasks (or even more).
boulethao
boulethao
/ mergesort_inplace.py
Last active
July 24, 2018 20:31
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # IN PLACE MERGE SORT | |
| def mergesort(arr): | |
| if arr is None or len(arr) <= 1: | |
| return arr | |
| _mergesort(arr, 0, len(arr)-1) |
boulethao
/ kthelement_qsort.py
Last active
July 9, 2018 18:21
Find the element of rank k using qsort type algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def find_kth_element(a, lo, hi, k): | |
| if lo >= hi: | |
| return a[lo] | |
| p = partition(a, lo, hi) | |
| if (k-1) == p: | |
| return a[p] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def iterative_quicksort(arr): | |
| """ | |
| Iterative quick sort | |
| :param arr: arr to be sorted | |
| :return: | |
| """ | |
| if arr is None or len(arr) <= 1: | |
| return | |
| lo = 0 |
boulethao
/ K-way-partition.md
Last active
March 9, 2022 19:07
Quicksort algorithm is extendable to k-way partition
boulethao
/ Median of Three.md
Last active
July 8, 2018 18:36
The median of three numbers is the one that has the middle value of all three. In other words, if the three numbers are sorted, the one in the middle is the median.
There are several ways of comparing operations among variable a, b and c to determine which one is the median.
One brute force way is to directly represent verify the following formula: