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).
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) |
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 |
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: