Quicksort with Python

Question

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code?

I do not know how to concatenate the three arrays and printing them.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

Solution 1

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Solution 2

Quick sort without additional memory (in place)

Usage:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
print(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in range(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

Solution 3

There is another concise and beautiful version

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]])
        + [arr[0]]
        + qsort([x for x in arr[1:] if x >= arr[0]])

Let me explain the above codes for details

1. pick the first element of array arr[0] as pivot

   [arr[0]]

2. qsort those elements of array which are less than pivot with List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort those elements of array which are larger than pivot with List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

Solution 4

This answer is an in-place QuickSort for Python 2.x. My answer is an interpretation of the in-place solution from Rosetta Code which works for Python 3 too:

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

And if you are willing to forgo the in-place property, below is yet another version which better illustrates the basic ideas behind quicksort. Apart from readability, its other advantage is that it is stable (equal elements appear in the sorted list in the same order that they used to have in the unsorted list). This stability property does not hold with the less memory-hungry in-place implementation presented above.

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

Solution 5

Quicksort with Python

In real life, we should always use the builtin sort provided by Python. However, understanding the quicksort algorithm is instructive.

My goal here is to break down the subject such that it is easily understood and replicable by the reader without having to return to reference materials.

The quicksort algorithm is essentially the following:

1. Select a pivot data point.
2. Move all data points less than (below) the pivot to a position below the pivot - move those greater than or equal to (above) the pivot to a position above it.
3. Apply the algorithm to the areas above and below the pivot

If the data are randomly distributed, selecting the first data point as the pivot is equivalent to a random selection.

Readable example:

First, let's look at a readable example that uses comments and variable names to point to intermediate values:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

To restate the algorithm and code demonstrated here - we move values above the pivot to the right, and values below the pivot to the left, and then pass those partitions to same function to be further sorted.

Golfed:

This can be golfed to 88 characters:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

To see how we get there, first take our readable example, remove comments and docstrings, and find the pivot in-place:

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

Now find below and above, in-place:

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

Now, knowing that and returns the prior element if false, else if it is true, it evaluates and returns the following element, we have:

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

Since lambdas return a single epression, and we have simplified to a single expression (even though it is getting more unreadable) we can now use a lambda:

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

And to reduce to our example, shorten the function and variable names to one letter, and eliminate the whitespace that isn't required.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Note that this lambda, like most code golfing, is rather bad style.

In-place Quicksort, using the Hoare Partitioning scheme

The prior implementation creates a lot of unnecessary extra lists. If we can do this in-place, we'll avoid wasting space.

The below implementation uses the Hoare partitioning scheme, which you can read more about on wikipedia (but we have apparently removed up to 4 redundant calculations per partition() call by using while-loop semantics instead of do-while and moving the narrowing steps to the end of the outer while loop.).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

Not sure if I tested it thoroughly enough:

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

Conclusion

This algorithm is frequently taught in computer science courses and asked for on job interviews. It helps us think about recursion and divide-and-conquer.

Quicksort is not very practical in Python since our builtin timsort algorithm is quite efficient, and we have recursion limits. We would expect to sort lists in-place with list.sort or create new sorted lists with sorted - both of which take a key and reverse argument.

View more solutions

Comments

[Mark Mishyn]

To combine lists you can use plus operator my_list = list1 + list2 + .... Or unpack lists to new list my_list = [*list1, *list2]

[Yves Daoust]

Quicksort is meant to be an in-place algorithm, which you code is not at all. Not counting that the append operation is not necessarily performed in constant time.

[Brionius]

@user2687481 Could you either add that to this question, or write a new question? It's too hard to tell what your code says, since the comment box removes the formatting and whitespace.

[FedeN]

By the way, the concise version has less performance than the long one, since it is iterating the array twice to in the list comprehensions.

[Scott 混合理论]

O(N!)? is this a 'slowSort'?

[Alice]

I believe in the first code example it should be 'lesser' and 'greater' instead of '[lesser]' and '[greater]' - else you'll end up with nested lists instead of a flat one.

[Palec]

Please include explanation of what your code does and how it answers the question. Especially how does it relate to the code posted in the question. Answer should give the OP and future visitors guidance on how to debug and fix their problem. Pointing out, what the idea behind your code is, greatly helps in understanding the issue and applying or modifying your solution. Stack Overflow is not a code writing service, it’s a teaching and learning place.

[SlimPDX]

You could also swap out the 2nd ifs in the for loop with elif and else to avoid doing unnecessary comparisons

[m02ph3u5]

please provide some explaination or background information instead of just the plain code

[dimonb]

It's pretty simple. We choose any element, first for example. And than divide list on two parts (left part with less than selected element and right is greater). Repeat this operation with left and right part and so on.

[rnevius]

Welcome to Stack Overflow. It's recommended that you include code in your answer, as links may become broken over time.

[ForeverLearner]

Thanks for sharing this solution. Can you please help us understand the time-complexity? I see that the recursion will call it 15 times. Of these 8 are valid calls to the function. Does that mean the time-complexity is O(n) for the first solution and space complexity is O(1) as its in-place sort ?

[alisianoi]

@Tammy it looks like you misunderstand the big-O notation. Moreover, I do not really understand your question. Could you perhaps ask it as a separate one? Finally, Quicksort as an algorithm runs in O(n logn) time and O(n) space.

[alisianoi]

Welcome to Stack Overflow. In python, it is a good idiom to exchange objects without introducing a tepmorary name in one line like so: alist[i], alist[j] = alist[j], alist[i]

[ForeverLearner]

My Bad. Why on earth was i counting recursions ?? :-) Well, 15 recursions is [1 call (Level 0) + 2 call (Level 1 partition) + 4 call (Level 2 partition) + 8 call (Level 3 partition or Leaf nodes). So , we still have height as (lg8 + 1) = lgn. Total computation in each level is for c1(some cost) * n. Hence O(n lgn). Space complexity, for one in-place exchange = O(1). Hence for n elements = O(n). Thanks for the pointer.

[Emad Mokhtar]

This is sound like merge sort not quick sort

[Chrispy]

@Scott混合理论 I'm still learning time complexity, can you elaborate why this implementation is O(N!)? Assuming the nested list [lesser] and [greater] are typos, wouldn't it be average O(3N logN) which would reduce to the expected average O(N logN)? Granted, the 3 list comps do unnecessary work..

[Scott 混合理论]

@Chrispy what if you sort a inverted order list, like 5,4,3,2,1

[cmantas]

It's actually the best and most readable python code I found for quicksort anywhere. No indices, no helper functions, clearly shows the gist of the algorithm (divide and conquer). (The default value for the array is rather unnecessary)

[alisianoi]

@zangw possible reasons for a downvote: 1) Quadratic runtime on already sorted or reversed arrays 2) The solution is not in-place. Therefore, a terrible implementation, sorry.

[Brionius]

Wow, wrote this a while ago. @MaxMarchuk - you're right, those extra comparisons are unnecessary, and should be part of one if...elif...else block, although I feel weird editing it after so long, after so many votes.

[jsmedmar]

not readable at all, are you truly trying to minimize the number of lines? Code is interpreted by machines, but understood by humans.

[Igor]

very readable, I wonder, one of below(post written by zangw) comments have nice short pythonic quick sort which use comprehension list, it is fast but still slower then above one. would it be that standard for loop has better performance then [comprehension list] ?

[Teepeemm]

18 other answers, more than half of which answer OP's original question of "how to concatenate the three arrays". Does your answer add anything new?

[John]

@jsmedmar it will use more memory than an in place version, see suquant's answer for an in place quick sort.

[Lungang Fang]

@Scott混合理论 you are right that worst-case run time of quick sort is slow Θ(n^2), but according to "introduction to algorithm", the average-case running time is Θ(n lg n). And, more importantly, quick sort generally outperforms heap sort in practice

[Rasmi Ranjan Nayak]

So, straight way we can write sort(array). Then what is the meaning of implementing quicksort?? Though many people liked it but I don't think this will help. I liked stackoverflow.com/a/27461889/1105805

[Maksood]

Very readable but does not this defeat the purpose of quick-sort since this won't achieve 'in place' sort? @RasmiRanjanNayak sort here is the user defined function (its a recursive call), not any built in function.

[Rasmi Ranjan Nayak]

@Maksood: Yes you are right. The built in function is sorted not sort

[brandonscript]

While this code snippet may answer the question, it doesn't provide any context to explain how or why. Consider adding a sentence or two to explain your answer.

[Padraic Cunningham]

@AlfredoGallegos, the whole point of quicksort is it happens in place, you may as well implement merge-sort if you are going to do this.

[aerin]

@cmantas But wouldn't it consume additional memory which might become an issue for really large arrays?

[Gillespie]

if end is None: is going to be checked a lot of times, and only once is it going to be True. You should put this in a wrapper function so it is only called once.

[cmantas]

@ToussaintLouverture. Sure, this neither "production ready" nor space-efficient. However my (strictly personal) opinion is that it manages to "show off" the conceptual structure of the algorithm very neatly.

[yeulucay]

This is not quick sort. It's big O notation is n.logn and similar to merge sort

[Kunthar]

list is reserved in python 3. see modified version of your code here: gist.github.com/kunthar/9d8962e1438e93f50dc6dd94d503af3d

[max]

It's probably better not to take the first item of the array as the pivot. This is guaranteed quadratic runtime on a sorted (or reverse sorted) input. For illustration purposes, it's fine, but for any real use you'd want to do something like "median of three".

[zangw]

@Adrienne, I have updated my answer, hope it will make my answer more clearly

[joshuatvernon]

akarca and @Kunthar Both these solutions in either python2 or python3 will pop an element from the list each time it is run, therefore destroying the list. Here is a fixed version: gist.github.com/joshuatvernon/634e0d912401899af0fdc4e23c9419‌​2b

[greybeard]

Nice (far as undocumented code goes), if similar to acarca's, Arnaldo P. Figueira Figueira's and Birger's answers from years gone by. Not sure this is an answer when the question reads … complete my code?. Using lambda to define sublist() doesn't look strictly necessary.

[lifebalance]

@greybeard Actually, Arnaldo's code did not compile in Python 3. Also, how can sublist be defined only using filter? Is that even possible?

[greybeard]

(Temporary comment: thinkin' of def - didn't start tinkering yet as I'm trying to figure out whether there's a more efficient way to "distribute" the elements of an iterable to separate lists (or, alternatively, one list with one "category" after the other).)

[Kenan]

Although this approach is easy to read, the purpose of quick sort is to be in place.

[TamerB]

It does the job and it's clean and readable. But it doesn't apply in place replacement, this is definitely not Quick sort.

[DragonKnight]

As @max said you better to chose the pivot element randomly to reach O(nlogn): pivot = random.choice(array), what @Brionius has written guarantees n(n-1)/2 = O(n2)

[Chris Conlan]

I may be missing something here, but how is this quicksort when Python's sort() function is called? Python's sort() uses Timsort. en.wikipedia.org/wiki/Timsort I was looking for more of the classically-indexed version for education's sake.

[pass-by-ref]

The best and simplest example I've ever seen for quick sort.

[Madu Alikor]

One Major advantage of the quicksort over merge sort is the space complexity ie the amount of memory required to solve the problem excluding the input, The algorithm above allocated three additional arrays potentially summed together being as big as the original input giving this a space complexity of O(n) rather than if the sort was done in place which would have the space complexity of O(1)

[Omar Einea]

please explain your code/additions so that OP and future views can benefit more.

[Nobilis]

Are these comment for real? If you want performance, use sorted, this is clearly for educational purposes. And it is readable, more readable than the accepted answer.

[SolveIt]

FWIW, I thought this was the most readable implementation of them all. It shows the recursive structure of the algorithm better than any other answer. Of course, the performance isn't going to be too great.

[matino]

Your partition function seem not to work correctly for: partition([5,4,3,2,1], 0, 4). Expected return index is 4, while it returns 3.

[Russia Must Remove Putin]

@matino Where did that expectation come from? I believe I simplified the algorithm (as stated on wikipedia when writing this answer), though I could be wrong, or perhaps less efficient. If you could find a test-case for which the entire quicksort function fails, that would be helpful.

[Sasha Kondrashov]

this is far and away the best python quicksort on the internet, and it's sad to see it buried under so many O(n) space solutions :(

[alisianoi]

Thanks for the kind words @Timofey. You might want to take a look at my algorithms repo, it has other versions of sorts, graph algorithms, etc. etc. github.com/alisianoi/algos-py

[Cloud]

Number is immutable in Python, so new list that reference to the original numbers will only add reference count. So I think this algorithm is memory efficient as placing.

[Ryan J McCall]

Ackchyually, bruhs, @mksteve is right and this line is incorrect. Additionally, array[pivot], array[begin] = array[begin], array[pivot] should replace begin with end.

[Almenon]

Although in-place is good, this is slow and it errors out due to hitting the max recursion depth when there is a lot of items. see repl.it/@almenon/quicksorts?language=python3

[Almenon]

@alisianoi this solution isn't actually that bad. It performs just as fast as the top voted solution and it is much less lines. See repl.it/@almenon/quicksorts?language=python3

[aljgom]

@mksteve and Ryan, I tested these changes and it breaks the sortings

[Harshith Rai]

please provide some explanation

[Gabriel Fair]

For anyone looking to have qsort return a list of numbers and not a list of arbitrary nested sublists, consider flattening it using this method: stackoverflow.com/a/53778278/635160

[vineeshvs]

Correction in the code: Change the line "else x > pivot: " to "else:" as else statement doesn't accept any conditions and the code will give error if you put one.

[vineeshvs]

For a large array, I am getting the following error for the above code: "if x < pivot: RuntimeError: maximum recursion depth exceeded in cmp "

[Rock]

I would be strongly against this piece of code. The performance is super, super bad compared to a migrated C++ version. I am talking about 3-4x worse.

[Rock]

If you talk about performance, both this answer and the top voted solution have horrible performance. Some C++-like python code can easily beat this with 3-4x speed-up.

[nuriselcuk]

@dtypist due to recursion function every function calls create space on heap. If you have larger array, it calls sort() function more and python interpreter prevent to run this.

[Kelly Bundy]

@Almenon Well you're not fair there. You run the sorts 100 times with the same input, meaning the in-place sort gets an already sorted input the second time you call it. If you use timeit('randomList[:]=qsort(randomList)', ...) for the first two sorts to make it fair, then they hit the max recursion depth as well.

[Qiulang]

@AaronHall when I chose pivot = a_list[high] but I just can't figure it out how to make it work then. Can you help ?

[gebbissimo]

@alisianoi : Thanks for the great and clean code. However, can it be that some unnecessary operations are performed in case of lists with duplicate values? When you call "qsort(l, fst, j) and qsort(l, i, lst)" I would have expected that (j-i)=2, but often (j-i)=1. Testd with nums = [5, 4, 2, 1, 1, 1, 0, 7, 6, 9, 8] and random.seed(0).

[alisianoi]

For the duplicate values, there is a separate variation of QuickSort with Bentley and McIlroy partitioning. I believe you can find it somewhere in Sedgewick & Wayne "Algorithms" but the code is also here: github.com/alisianoi/algos-py/blob/…

[alisianoi]

@gebbissimo ah, I understand your question now. No, (j - 1) = 1 if you have an even number of elements in list and (j - 1) = 2 if you have an odd number. In the example above, you have an odd number of elements. You're probably making the mistake that the pivot element will end up exactly in the middle, that is wrong.

[palaѕн]

While this code may provide a solution to problem, it is highly recommended that you provide additional context regarding why and/or how this code answers the question. Code only answers typically become useless in the long-run because future viewers experiencing similar problems cannot understand the reasoning behind the solution.

[Karan Alang]

nice explanation .. however, does this not take extra space ? Quick sort is supposed to be in-place sorting.

[Dror Speiser]

@matino I had the same confusion! The partition function is fine, the invariant it satisfies is weaker than what you're expecting - it doesn't have to find the exact place that separates left and right to smaller and larger than the pivot. It only guarantees a non trivial partition and that all left of returned index are smaller than right of returned index.

[Alex]

Great answer! The problem of duplicate pivots was mind-boggling for me. I spent quite a time to figure out solution like yours without success. The standard solution is also correct of course, but is not so clear from my point.

[Alex]

In the second variant without recursion the 'ranges' parameter is not needed. It should be introduced as variable in the function body.

[Azat Aleksanyan]

thanks for the answer, could you please tell me how it understands when it should stop the loop and give the sorted answer. as in the return sort(less)+equal+sort(greater) it is going to perform the loop endlessly? if I understand it right

[Brionius]

@AzatAleksanyan Sure - that code only executes when len(array) > 1 (because of the if statement that return statement is contained in). When the function has finished recursing down to the point where the subarrays only contain one element, then instead the return array statement executes, which ends the recursion.

[Alex]

In the second variant instead of [start, end] = ranges[0] ranges = ranges[1:] one can do: [start, end] = ranges.pop(0)

[D Hudson]

Have to be a bit careful with this implementation. If the length of input list is 1 or 0 then it returns a reference to the inputted list, otherwise it returns a new list. I can imagine all kinds of confusing bugs resulting from this. Should either always sort in-place or always return a new list.

[Mokarrom Hossain]

@AaronHall, according to the linked Wiki's article, pivot choice must avoid the final element. So you shouldn't choose pivot = a_list[high].