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)

Answer 1

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

# this comment is just to improve readability due to horizontal scroll!!!

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

Answer 2

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.

Answer 3

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]

Answer 4

# 编程珠玑实现
# 双向排序: 提高非随机输入的性能
# 不需要额外的空间,在待排序数组本身内部进行排序
# 基准值通过random随机选取
# 入参: 待排序数组, 数组开始索引 0, 数组结束索引 len(array)-1
import random

def swap(arr, l, u):
    arr[l],arr[u] = arr[u],arr[l]
    return arr

def QuickSort_Perl(arr, l, u):
    # 小数组排序i可以用插入或选择排序 
    # if u-l < 50 : return arr
    # 基线条件: low index = upper index; 也就是只有一个值的区间
    if l >= u:
        return arr
    # 随机选取基准值, 并将基准值替换到数组第一个元素        
    swap(arr, l, int(random.uniform(l, u)))
    temp = arr[l]
    # 缓存边界值, 从上下边界同时排序
    i, j = l, u
    while True:
        # 第一个元素是基准值,所以要跳过
        i+=1
        # 在小区间中, 进行排序
        # 从下边界开始寻找大于基准值的索引
        while i <= u and arr[i] <= temp:
            i += 1
        # 从上边界开始寻找小于基准值的索引
        # 因为j肯定大于i, 所以索引值肯定在小区间中
        while arr[j] > temp:
            j -= 1
        # 如果小索引仍小于大索引, 调换二者位置
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    # 将基准值的索引从下边界调换到索引分割点
    swap(arr, l, j)
    QuickSort_Perl(arr, l, j-1)
    QuickSort_Perl(arr, j+1, u)
    return arr

print('QuickSort_Perl([-22, -21, 0, 1, 2, 22])',
    QuickSort_Perl([-22, -21, 0, 1, 2, 22], 0, 5))

Answer 5

Quick sort without additional memory (in place)

Usage:

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

def partition(array, begin, end):
    pivot = begin
    for i in xrange(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)

Answer 6

If I search "python quicksort implementation" in Google, this question is the first result to pop up. I understand that the initial question was to "help correct the code" but there already are many answers that disregard that request: the currently second most voted one, the horrendous one-liner with the hilarious "You are fired" comment and, in general, many implementations that are not in-place (i.e. use extra memory proportional to input list size). This answer provides an in-place solution but it is for python 2.x. So, below follows my interpretation of the in-place solution from Rosetta Code which will work just fine for python 3 too:

import random

def qsort(l, fst, lst):
    if fst >= lst: return

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

    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j - 1
    qsort(l, fst, j)
    qsort(l, 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(l):
    if not l: return l # empty sequence case
    pivot = l[random.choice(range(0, len(l)))]

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