aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/algorithms/impl/quicksort.py
diff options
context:
space:
mode:
Diffstat (limited to 'algorithms/impl/quicksort.py')
-rw-r--r--algorithms/impl/quicksort.py17
1 files changed, 17 insertions, 0 deletions
diff --git a/algorithms/impl/quicksort.py b/algorithms/impl/quicksort.py
index 1e835c4..dd0c92b 100644
--- a/algorithms/impl/quicksort.py
+++ b/algorithms/impl/quicksort.py
@@ -8,8 +8,10 @@ import sys
from ..algorithm import SortingAlgorithm
+
seed()
+
def _partition(xs, beg, end, select_pivot):
pivot = select_pivot(xs, beg, end)
xs[pivot], xs[end] = xs[end], xs[pivot]
@@ -20,47 +22,59 @@ def _partition(xs, beg, end, select_pivot):
xs[beg], xs[end] = xs[end], xs[beg]
return beg
+
def _quicksort(xs, beg, end, select_pivot):
if beg < end:
pivot = _partition(xs, beg, end, select_pivot)
_quicksort(xs, beg, pivot - 1, select_pivot)
_quicksort(xs, pivot + 1, end, select_pivot)
+
def _select_first(xs, beg, end):
return beg
+
def _select_second(xs, beg, end):
return beg + 1
+
def _select_middle(xs, beg, end):
return (beg + end) // 2
+
def _select_last(xs, beg, end):
return end
+
def _select_random(xs, beg, end):
return randrange(beg, end + 1)
+
def quicksort_first(xs):
_quicksort(xs, 0, len(xs) - 1, _select_first)
return xs
+
def quicksort_second(xs):
_quicksort(xs, 0, len(xs) - 1, _select_second)
return xs
+
def quicksort_middle(xs):
_quicksort(xs, 0, len(xs) - 1, _select_middle)
return xs
+
def quicksort_last(xs):
_quicksort(xs, 0, len(xs) - 1, _select_last)
return xs
+
def quicksort_random(xs):
_quicksort(xs, 0, len(xs) - 1, _select_random)
return xs
+
_ALGORITHMS = [
SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first),
SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second),
@@ -69,11 +83,13 @@ _ALGORITHMS = [
SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(quicksort_first(list(xs)))
@@ -82,5 +98,6 @@ def main(args=None):
print(quicksort_last(list(xs)))
print(quicksort_random(list(xs)))
+
if __name__ == '__main__':
main()