Last Updated: June 23, 2017
·
15.41K

# QuickSort in Python

###### quicksort

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])  ``````

#### 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) xs``````
over 1 year ago ·

I 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])

over 1 year ago ·