Skip to content

Instantly share code, notes, and snippets.

@N02870941 N02870941/sorting.py
Created Sep 12, 2018

Embed
What would you like to do?
A few sorting algorithms in Python
import math
import random
#-------------------------------------------------------------------------------
'''
Default comparator that sorts
numeric values in their natural order.
'''
def comparator(one, two):
return one - two
#-------------------------------------------------------------------------------
'''
Comparator that sorts numeric
values in descending order.
'''
def reverse(one, two):
return two - one
#-------------------------------------------------------------------------------
'''
Sorts an array of values with a specified comparator.
'''
def msort(array, comparator=comparator):
mergesort(array, 0, len(array)-1, comparator)
#-------------------------------------------------------------------------------
'''
Merge sort on a sub-array.
'''
def mergesort(a, lo, hi, compare=comparator):
if lo < hi:
mid = math.floor(lo + (hi - lo) / 2)
mergesort(a, lo, mid, compare)
mergesort(a, mid+1, hi, compare)
i = lo
j = mid+1
k = lo
b = [None] * (len(a) * 2)
while i <= mid and j <= hi:
if compare(a[i], a[j]) < 0:
b[k] = a[i]
i += 1
else:
b[k] = a[j]
j += 1
k += 1
while i <= mid:
b[k] = a[i]
k += 1
i += 1
while j <= hi:
b[k] = a[j]
k += 1
j += 1
for m in range(lo, k):
a[m] = b[m]
#-------------------------------------------------------------------------------
'''
Sorts an array of values with a specified comparator.
'''
def qsort(array, comparator=comparator):
quicksort(array, 0, len(array)-1, comparator)
return array
#-------------------------------------------------------------------------------
'''
Quicksort using Hoare partitioning scheme.
'''
def quicksort(a, lo, hi, compare=comparator):
if lo >= hi:
return
i = lo
j = hi
r = random.randint(lo, hi - 1)
pivot = a[r];
while i <= j:
while compare(a[i], pivot) < 0:
i += 1
while compare(a[j], pivot) > 0:
j -= 1
if i <= j:
t = a[i]
a[i] = a[j]
a[j] = t
i += 1
j -= 1
if lo < j:
quicksort(a, lo, j, compare)
if i < hi:
quicksort(a, i, hi, compare)
#-------------------------------------------------------------------------------
'''
Selection sort with an optional comparator.
'''
def ssort(a, compare=comparator):
n = len(a)
for i in range(0, n):
min = i
for j in range(i, n):
if compare(a[j], a[min]) < 0:
min = j
if min != i:
t = a[i]
a[i] = a[min]
a[min] = t
return a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.