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

Maxia

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

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. – Confidence

Answer 1

def sort(array):
    """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

Plautus

@Maxia 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. – Plautus

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

This is sound like merge sort not quick sort – Centromere

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) – Ideally

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. – Plautus

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] ? – Incisor

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

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 https://mcmap.net/q/187914/-quicksort-with-python – Dairen

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. – Agueweed

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

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

@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. – Ideally

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

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". – Incident

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

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

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

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. – Hijoung

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

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) – Grimmett

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. – Katt

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. – Cynthea

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

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. – Turbinate

@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. – Flaviaflavian

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

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 – Shoon

@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. – Plautus

Can I get a little help understanding how efficient this code would be in the worst and best case scenarios? Say that you had the best case: [1, 2, 3, 4, 5] and picked 3 as the Pivot. Then this would call: sorted(left(1, 2)) + equal(3) + sorted(right(4, 5)). And if you had the worst case scenario [5, 4, 3, 2, 1] and picked 5 as the pivot, you would need to call: Sorted(left(4, 3, 2, 1) + equal(5) + sorted(right()). Say you continuously picked the left most pivot here, you would still need to run the same amount of method calls. No? – Phenol

Using that same example, and if I'm not mistaken: [1, 2, 3, 4, 5]. If you used middle (3) as the pivot, you would have recursive calls on sections with values [1, 2] and [4, 5]. However, if you repeatedly chose the leftmost value as your pivots for this same data set you would have recursive calls [2, 3, 4, 5], [3, 4, 5], [4, 5] which is an extra operation. If you double that list to 10 items, it's 2 extra operations (8 instead of 6), and if you double it again to 20 items it's 3 extra (18 instead of 15). Larger data makes it easier to demonstrate – Tribade

..though, an even bigger problem with the worst-case scenario is stack overflow from recursion depth. In the best case of ~median pivot, it operates like DFS of a balanced tree, and you can process 100M+ items without stack overflow. But the worst-case scenario is like DFS of an unbalanced tree with everything on one side and the recursion depth is n, and you can stack overflow with just 997 items. Using your same example, [1, 2, 3, 4, 5] with middle pivot goes to [1, 2], then goes back up to do right, so the depth is 2. If you always choose left most, it's 4: [2, 3, 4, 5], [3, 4, 5], [4, 5] – Tribade

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

Creedon

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. – Deaton

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

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 – Doolittle

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

@Doolittle 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. – Maxson

Answer 3

There is a 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]])

Allow me to explain the above code:

1. Select the first element of the array as the pivot:

   [arr[0]]
   

2. Sort those elements of the array that are less than the pivot using list comprehension:

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

3. Sort those elements of the array that are larger than the pivot using list comprehension:

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

Mesmerism

@Mesmerism 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. – Gentleness

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

@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. – Lyceum

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

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. – Rolandrolanda

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. – Shaefer

@Gentleness 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 – Doolittle

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. – Turbinate

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. – Pang

Answer 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

Gentleness

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 ? – Mariannemariano

@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. – Gentleness

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. – Mariannemariano

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 :( – Chapatti

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 – Gentleness

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: https://mcmap.net/q/36065/-how-do-i-make-a-flat-list-out-of-a-list-of-lists – Frequent

@Gentleness : 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). – Sheliasheline

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/… – Gentleness

@Sheliasheline 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. – Gentleness

How come the time-complexity for this method is not O(n^2), since we clearly have nested while loops ?? – Tricksy

@Tricksy because those nested while loops do not look at all elements on every iteration. Instead, the inner while loops "meet in the middle" – Gentleness

Answer 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.

Tamar

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. – Hydrogenate

@Hydrogenate 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. – Tamar

@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 ? – Euphoria

@Hydrogenate 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. – Unset

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

Answer 6

There are many answers to this already, but I think this approach is the most clean implementation:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

You can of course skip storing everything in variables and return them straight away like this:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

Hermia

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

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. – Motive

@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.. – Flamingo

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

@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 – Transom

Answer 7

functional approach:

def qsort(lst):
    if len(lst) < 2:
        return lst

    pivot = lst[0]
    left = list(filter(lambda x: x <= pivot, lst[1:]))
    right = list(filter(lambda x: x > pivot, lst[1:]))
    
    return qsort(left) + [pivot] + qsort(right)

Spotty

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

akarca and @Tinfoil 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/634e0d912401899af0fdc4e23c94192b – Pithead

Answer 8

This is a version of the quicksort using Hoare partition scheme and with fewer swaps and local variables

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Grimmett

Answer 9

Easy implementation from grokking algorithms

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

Motive

Answer 10

functional programming aproach

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Godoy

Answer 11

I think both answers here works ok for the list provided (which answer the original question), but would breaks if an array containing non unique values is passed. So for completeness, I would just point out the small error in each and explain how to fix them.

For example trying to sort the following array [12,4,5,6,7,3,1,15,1] (Note that 1 appears twice) with Brionius algorithm .. at some point will end up with the less array empty and the equal array with a pair of values (1,1) that can not be separated in the next iteration and the len() > 1...hence you'll end up with an infinite loop

You can fix it by either returning array if less is empty or better by not calling sort in your equal array, as in zangw answer

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)
            elif x == pivot:
                equal.append(x)
            else: # if 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 hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

The fancier solution also breaks, but for a different cause, it is missing the return clause in the recursion line, which will cause at some point to return None and try to append it to a list ....

To fix it just add a return to that line

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

Endogenous

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. – Endogenous

Answer 12

Partition - Split an array by a pivot that smaller elements move to the left and greater elemets move to the right or vice versa. A pivot can be an random element from an array. To make this algorith we need to know what is begin and end index of an array and where is a pivot. Then set two auxiliary pointers L, R.

So we have an array user[...,begin,...,end,...]

The start position of L and R pointers
[...,begin,next,...,end,...]
     R       L

while L < end
  1. If a user[pivot] > user[L] then move R by one and swap user[R] with user[L]
  2. move L by one

After while swap user[R] with user[pivot]

Quick sort - Use the partition algorithm until every next part of the split by a pivot will have begin index greater or equals than end index.

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)

Prog

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

Answer 13

Or if you prefer a one-liner that also illustrates the Python equivalent of C/C++ varags, lambda expressions, and if expressions:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

Trillbee

Answer 14

A "true" in-place implementation [Algorithms 8.9, 8.11 from the Algorithm Design and Applications Book by Michael T. Goodrich and Roberto Tamassia]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()

Waterbuck

Answer 15

def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)

Halloo

Answer 16

I know many people have answered this question correctly and I enjoyed reading them. My answer is almost the same as zangw but I think the previous contributors did not do a good job of explaining visually how things actually work...so here is my attempt to help others that might visit this question/answers in the future about a simple solution for quicksort implementation.

How does it work ?

1. We basically select the first item as our pivot from our list and then we create two sub lists.
2. Our first sublist contains the items that are less than pivot
3. Our second sublist contains our items that are great than or equal to pivot
4. We then quick sort each of those and we combine them the first group + pivot + the second group to get the final result.

Here is an example along with visual to go with it ... (pivot)9,11,2,0

average: n log of n

worse case: n^2

The code:

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

items=[9,11,2,0] print(quicksort(items))

Heddy

Answer 17

The algorithm contains two boundaries, one having elements less than the pivot (tracked by index "j") and the other having elements greater than the pivot (tracked by index "i").

In each iteration, a new element is processed by incrementing j.

Invariant:-

1. all elements between pivot and i are less than the pivot, and
2. all elements between i and j are greater than the pivot.

If the invariant is violated, ith and jth elements are swapped, and i is incremented.

After all elements have been processed, and everything after the pivot has been partitioned, the pivot element is swapped with the last element smaller than it.

The pivot element will now be in its correct place in the sequence. The elements before it will be less than it and the ones after it will be greater than it, and they will be unsorted.

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Selecting a pivot

A "good" pivot will result in two sub-sequences of roughly the same size. Deterministically, a pivot element can either be selected in a naive manner or by computing the median of the sequence.

A naive implementation of selecting a pivot will be the first or last element. The worst-case runtime in this case will be when the input sequence is already sorted or reverse sorted, as one of the subsequences will be empty which will cause only one element to be removed per recursive call.

A perfectly balanced split is achieved when the pivot is the median element of the sequence. There are an equal number of elements greater than it and less than it. This approach guarantees a better overall running time, but is much more time-consuming.

A non-deterministic/random way of selecting the pivot would be to pick an element uniformly at random. This is a simple and lightweight approach that will minimize worst-case scenario and also lead to a roughly balanced split. This will also provide a balance between the naive approach and the median approach of selecting the pivot.

Alright

Answer 18

def quicksort(array):
 if len(array) < 2:
  return array
 else:
  pivot = array[0]

 less = [i for i in array[1:] if i <= pivot]
 greater = [i for i in array[1:] if i > pivot]
 return quicksort(less) + [pivot] + quicksort(greater)

Albano

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. – Bryner

Answer 19

def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []

Sim

Answer 20

def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A

Valdivia

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. – Her

Answer 21

The algorithm has 4 simple steps:

1. Divide the array into 3 different parts: left, pivot and right, where pivot will have only one element. Let us choose this pivot element as the first element of array
2. Append elements to the respective part by comparing them to pivot element. (explanation in comments)
3. Recurse this algorithm till all elements in the array have been sorted
4. Finally, join left+pivot+right parts

Code for the algorithm in python:

def my_sort(A):

      p=A[0]                                       #determine pivot element. 
      left=[]                                      #create left array
      right=[]                                     #create right array
      for i in range(1,len(A)):
        #if cur elem is less than pivot, add elem in left array
        if A[i]< p:
          left.append(A[i])         
          #the recurssion will occur only if the left array is atleast half the size of original array
          if len(left)>1 and len(left)>=len(A)//2:          
              left=my_sort(left)                            #recursive call
        elif A[i]>p: 
          right.append(A[i])                                #if elem is greater than pivot, append it to right array
          if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
              right=my_sort(right)
     A=left+[p]+right                                        #append all three part of the array into one and return it
     return A

my_sort([12,4,5,6,7,3,1,15])

Carry on with this algorithm recursively with the left and right parts.

Nucleolated

Answer 22

Full example with printed variables at partition step:

def partition(data, p, right):
    print("\n==> Enter partition: p={}, right={}".format(p, right))
    pivot = data[right]
    print("pivot = data[{}] = {}".format(right, pivot))

    i = p - 1  # this is a dangerous line

    for j in range(p, right):
        print("j: {}".format(j))
        if data[j] <= pivot:
            i = i + 1
            print("new i: {}".format(i))
            print("swap: {} <-> {}".format(data[i], data[j]))
            data[i], data[j] = data[j], data[i]

    print("swap2: {} <-> {}".format(data[i + 1], data[right]))
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1


def quick_sort(data, left, right):
    if left < right:
        pivot = partition(data, left, right)
        quick_sort(data, left, pivot - 1)
        quick_sort(data, pivot + 1, right)

data = [2, 8, 7, 1, 3, 5, 6, 4]

print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))

Quintic

Answer 23

Another quicksort implementation:

# A = Array 
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index

def swap(A,i1,i2):
  A[i1], A[i2] = A[i2], A[i1]

def partition(A,g,p):
    # O(n) - just one for loop that visits each element once
    for j in range(g,p):
      if A[j] <= A[p]:
        swap(A,j,g)
        g += 1

    swap(A,p,g)
    return g

def _quicksort(A,s,e):
    # Base case - we are sorting an array of size 1
    if s >= e:
      return

    # Partition current array
    p = partition(A,s,e)
    _quicksort(A,s,p-1) # Left side of pivot
    _quicksort(A,p+1,e) # Right side of pivot

# Wrapper function for the recursive one
def quicksort(A):
    _quicksort(A,0,len(A)-1)

A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]

print(A)
quicksort(A)
print(A)

Deaton

Answer 24

For Version Python 3.x: a functional-style using operator module, primarily to improve readability.

from operator import ge as greater, lt as lesser

def qsort(L): 
    if len(L) <= 1: return L
    pivot   = L[0]
    sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

    return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

and is tested as

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

Actualize

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. – Niko

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

(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).) – Niko

Answer 25

Here's an easy implementation:-

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

Orphanage

Answer 26

My answer is very similar to the great one from @alisianoi . However, I believe there is a slight inefficiency in his code (see my comment), which I removed. Moreover, I added more explanation and was a bit more specific about the problem of duplicate (pivot) values.

def quicksort(nums, begin=0, end=None):
    # Only at the beginning end=None. In this case set to len(nums)-1
    if end is None: end = len(nums) - 1

    # If list part is invalid or has only 1 element, do nothing
    if begin>=end: return

    # Pick random pivot
    pivot = nums[random.randint(begin, end)]

    # Initialize left and right pointers
    left, right = begin, end
    while left < right:
        # Find first "wrong" value from left hand side, i.e. first value >= pivot
        # Find first "wrong" value from right hand side, i.e. first value <= pivot
        # Note: In the LAST while loop, both left and right will point to pivot!
        while nums[left] < pivot: left += 1
        while nums[right] > pivot: right -= 1

        # Swap the "wrong" values
        if left != right:
            nums[left], nums[right] = nums[right], nums[left]
            # Problem:  loop can get stuck if pivot value exists more than once. Simply solve with...
            if nums[left] == nums[right]:
                assert nums[left]==pivot
                left += 1

    # Now, left and right both point to a pivot value.
    # All values to its left are smaller (or equal in case of duplicate pivot values)
    # All values to its right are larger.
    assert left == right and nums[left] == pivot
    quicksort(nums, begin, left - 1)
    quicksort(nums, left + 1, end)
    return

Without recursion:

def quicksort(nums, ranges=None):
    if ranges is None:
        ranges = [[0, len(nums) - 1]]
    while ranges != []:
        [start, end] = ranges[0]
        ranges = ranges[1:]
        if start >= end:
            continue
        pivot = nums[randint(start, end)]
        left = start
        right = end
        while left < right:
            while nums[left] < pivot:
                left += 1
            while nums[right] > pivot:
                right -= 1
            if left != right:
                nums[left], nums[right] = nums[right], nums[left]
                if nums[left] == nums[right]:
                    left += 1
        ranges = [[start, left - 1], [left + 1, end]] + ranges

Sheliasheline

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. – Catarina

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

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

Answer 27

1. First we declare the first value in the array to be the pivot_value and we also set the left and right marks
2. We create the first while loop, this while loop is there to tell the partition process to run again if it doesn't satisfy the necessary condition
3. then we apply the partition process
4. after both partition processes have ran, we check to see if it satisfies the proper condition. If it does, we mark it as done, if not we switch the left and right values and apply it again
5. Once its done switch the left and right values and return the split_point

I am attaching the code below! This quicksort is a great learning tool because of the Location of the pivot value. Since it is in a constant place, you can walk through it multiple times and really get a hang of how it all works. In practice it is best to randomize the pivot to avoid O(N^2) runtime.

def quicksort10(alist):
    quicksort_helper10(alist, 0, len(alist)-1)

def quicksort_helper10(alist, first, last):
    """  """
    if first < last:
        split_point = partition10(alist, first, last)
        quicksort_helper10(alist, first, split_point - 1)
        quicksort_helper10(alist, split_point + 1, last)

def partition10(alist, first, last):
    done = False
    pivot_value = alist[first]
    leftmark = first + 1
    rightmark = last
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivot_value:
            rightmark = rightmark - 1

        if leftmark > rightmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark

Leadwort

Answer 28

def quick_sort(l):
    if len(l) == 0:
        return l
    pivot = l[0]
    pivots = [x for x in l if x == pivot]
    smaller = quick_sort([x for x in l if x < pivot])
    larger = quick_sort([x for x in l if x > pivot])
    return smaller + pivots + larger

Bromberg

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? – Rimrock

Answer 29

def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don`t have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()

Stephine

please provide some explanation – Aggi

Answer 30

This algorithm doesn't use recursive functions.

Let N be any list of numbers with len(N) > 0. Set K = [N] and execute the following program.

Note: This is a stable sorting algorithm.

def BinaryRip2Singletons(K, S):
    K_L = []
    K_P = [ [K[0][0]] ] 
    K_R = []
    for i in range(1, len(K[0])):
        if   K[0][i] < K[0][0]:
            K_L.append(K[0][i])
        elif K[0][i] > K[0][0]:
            K_R.append(K[0][i])
        else:
            K_P.append( [K[0][i]] )
    K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
    while len(K_new) > 0:
        if len(K_new[0]) == 1:
            S.append(K_new[0][0])
            K_new = K_new[1:]
        else: 
            break
    return K_new, S

N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []

print('K =', K, 'S =', S)
while len(K) > 0:
    K, S = BinaryRip2Singletons(K, S)
    print('K =', K, 'S =', S)

PROGRAM OUTPUT:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]

Perplexed

Answer 31

Probably just a preference thing, but I like to add validation to the top of my functions.

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  left  = []
  right = []
  equal = []
  pivot = arr[-1]
  for num in arr:
    if num < pivot:
      left.append(num)
    elif num == pivot:
      equal.append(num)
    else:
      right.append(num)

  return quicksort(left) + equal + quicksort(right)

Tarnopol

Answer 32

I Find these solutions unnecessarily difficult to read, and most don't seem to account for duplicate elements in the array.

Here is my Quick Sort algorithm:

def qs(lst):
  if len(lst) <= 1:
    return lst

  pivot = lst[len(lst)//2]
  sml = [x for x in lst if x < pivot]
  mid = [x for x in lst if x == pivot]
  big = [x for x in lst if x > pivot]

  return qs(sml) + mid + qs(big)

Here is an example of input and output with this algorithm:

lst = [1, 9, 8, 4, 5, 3, 5, 7]
qs(lst)
>>> [1, 3, 4, 5, 5, 7, 8, 9]

Duodenal

Answer 33

Instead of taking three different arrays for less equal greater and then concatenating all try the traditional concept(partitioning method):

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

this is without using any inbuilt function.

partitioning function -

def partitn(alist, left, right):  
 i=left  
 j=right  
 mid=(left+right)/2   

pivot=alist[mid]  
while i <= j:  
    while alist[i] < pivot:  
        i=i+1   

    while alist[j] > pivot:  
        j=j-1   

    if i <= j:  
        temp = alist[i]  
        alist[i] = alist[j]  
        alist[j] = temp  
        i = i + 1   
        j = j - 1   

Intercontinental

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

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] – Gentleness

Answer 34

I will do quicksort using numpy library. I think it is really usefull library. They already implemented the quick sort method but you can implment also your custom method.

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort

indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)

temp_array = []

for index in index_list:
    temp_array.append( array[index])

array = temp_array

print array #it will show sorted array

Cobaltite

Answer 35

def quick_sort(list):
    if len(list) ==0:
        return []

    return  quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ]  +  quick_sort( filter( lambda item: item > list[0], list))

Kirkpatrick

Answer 36

inlace sort

def qsort(a, b=0, e=None):
    # partitioning
    def part(a, start, end):
        p = start
        for i in xrange(start+1, end):
            if a[i] < a[p]:
                a[i], a[p+1] = a[p+1], a[i]
                a[p+1], a[p] = a[p], a[p+1]
                p += 1
        return p

    if e is None:
        e = len(a)
    if e-b <= 1: return

    p = part(a, b, e)
    qsort(a, b, p)
    qsort(a, p+1, e)

without recursion:

deq = collections.deque()
deq.append((b, e))
while len(deq):
    el = deq.pop()
    if el[1] - el[0] > 1:
        p = part(a, el[0], el[1])
        deq.append((el[0], p))
        deq.append((p+1, el[1]))

Ferromagnesian

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

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. – Ferromagnesian

Answer 37

def quicksort(items):
    if not len(items) > 1:
        return items
    items, pivot = partition(items)
    return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])


def partition(items):
    i = 1
    pivot = 0
    for j in range(1, len(items)):
        if items[j] <= items[pivot]:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i - 1], items[pivot] = items[pivot], items[i - 1]
    return items, i - 1

Queenhood

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. – Ankylostomiasis