QuickSort in Python
I've been doing some rehearsal for a job interview. I started with the basics: QuickSort. I choose Python, because it's a really great language for an interview. If you have an option always go with Python. Clear and concise syntax lets you focus on the problem and helps with managing space on the whiteboard which is real scare resource during the interview. When I finished I googled other possible solutions. Sadly, most of them were overly complicated. Here is my codez:
from random import randrange
def partition(lst, start, end, pivot):
lst[pivot], lst[end] = lst[end], lst[pivot]
store_index = start
for i in xrange(start, end):
if lst[i] < lst[end]:
lst[i], lst[store_index] = lst[store_index], lst[i]
store_index += 1
lst[store_index], lst[end] = lst[end], lst[store_index]
return store_index
def quick_sort(lst, start, end):
if start >= end:
return lst
pivot = randrange(start, end + 1)
new_pivot = partition(lst, start, end, pivot)
quick_sort(lst, start, new_pivot - 1)
quick_sort(lst, new_pivot + 1, end)
def sort(lst):
quick_sort(lst, 0, len(lst) - 1)
return lst
print sort([])
print sort([1, 2, 3, 4])
print sort([-5, 3, -2, 3, 19, 5]) Written by lukas
Related protips
2 Responses
I had cannot understand quick sort until I found Haskell and this:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xsI think mine is easier
from statistics import median
def q_sort(array):
print(array)
if len(array)<=1:#return array when the length is less than and equal to 1, as sublist will have 0 and 1 length at the end
return array
else:
# best way to take a pivot is by median of first ,last and the middle element
pivot = median([array[0],array[int((len(array)-1)/2)],array[len(array)-1]])
array.remove(pivot)#removing the pivot from the list
list_r,list_l=[],[]# creating left and right list
for i in array:
if (i<=pivot):
list_l.append(i)
else:
list_r.append(i)
print(list_l,list_r,pivot)
return q_sort(list_l) + [pivot] +q_sort(list_r)q_sort([9,5,1,-5,10,0,23])
Have a fresh tip? Share with Coderwall community!
