Skip to content

Instantly share code, notes, and snippets.

@tdgunes

tdgunes/quicksort.py

Created Dec 10, 2014
Embed
What would you like to do?
import random
def partition(lst, left, right, pivotIndex):
# print pivotIndex
pivotValue = lst[pivotIndex]
lst[pivotIndex], lst[right] = lst[right], lst[pivotIndex]
storeIndex = left
for i in range(left, right):
if lst[i] < pivotValue:
lst[storeIndex], lst[i] = lst[i], lst[storeIndex]
storeIndex += 1
lst[right], lst[storeIndex] = lst[storeIndex], lst[right]
return storeIndex
def median3(lst, left, right):
# print left, right
center = (left + right) / 2
# print "center", center
if lst[center] < lst[left]:
lst[center], lst[left] = lst[left], lst[center]
#print "a"
if lst[right] < lst[left]:
lst[left], lst[right] = lst[right], lst[left]
#print "b"
if lst[right] < lst[center]:
lst[center], lst[right] = lst[right], lst[center]
#print "c"
lst[center], lst[right - 1] = lst[right - 1], lst[center]
#print "right",lst[right]
return lst[right - 1]
def select(lst, left, right, k):
if left + 10 <= right:
pivotIndex = median3(lst, left, right)
pivotIndex = partition(lst, left, right, pivotIndex)
if k == pivotIndex:
return lst[pivotIndex]
elif k < pivotIndex:
return select(lst, left, pivotIndex-1, k)
else:
return select(lst, pivotIndex+1, right, k)
else:
insertionSort(lst, left, right)
return lst[k]
def insertionSort(lst, left, right):
for i in range(left, right):
j = i
while j > 0 and lst[j - 1] > lst[j]:
lst[j], lst[j - 1] = lst[j - 1], lst[j]
j -= 1
def quickSelect(lst, k):
return select(lst, 0, len(lst) - 1, k)
print [quickSelect(a, i) for i in range(0, 9)]
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.