Last Updated: June 23, 2017
·
16.34K
· lukasz-madon

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

2 Responses
Add your response

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 ·