Lines 49
##### Keywords
quicksort (5) sort (5)
##### Permissions
Owner: Stou S.
Viewable by Everyone
Editable by All Siafoo Users
Writing an article is easy - try our reStructured Text demo

# Simple quick sort implementation 0

 In Brief Can chose different pivot types by setting pivot_type
 Language Python
# 's
` 1''' Quicksort implementation 2Author: stou@icapsid.net  3License: Public Domain 4''' 5 6from random import randint, shuffle 7 8comparisons = 0 910pivot_type = 01112def pick_pivot(a):1314    if pivot_type == 0:15        return 016    elif pivot_type == 1:17        return len(a) - 118    elif pivot_type == 2:19        middle = len(a) / 2 - 1 if len(a) % 2 == 0 else len(a) / 22021        if a[-1] > a[0] and a[0] > a[middle]:22            return 023        elif a[0] > a[-1] and a[-1] > a[middle]:24            return -125        else:26            return middle27#    elif pivot_type == 3:28#        return randint(0, len(a)-1)2930def quick_sort(a):3132    global comparisons3334    if len(a) > 0:35        comparisons += (len(a) - 1)3637    if len(a) < 2:38        return a3940    pivot_ix = pick_pivot(a)4142    a[0], a[pivot_ix] = a[pivot_ix], a[0]4344    i = 145    46    for j in range(1, len(a)):4748        if a[j] < a[0]:49            a[j], a[i] = a[i], a[j]50            i += 15152    a[0], a[i - 1] = a[i - 1], a[0]5354    l_a = quick_sort(a[ : i - 1])55    r_a = quick_sort(a[ i : ])5657    l_a.extend(r_a)5859    return l_a6061def main():6263    target = range(10)64    shuffle(target)6566    target = [int(l) for l in open('QuickSort.txt').readlines()]6768    print quick_sort(target)6970    print comparisons7172if __name__ == '__main__':73    main()`

Can chose different pivot types by setting pivot_type