|
| 1 | +from random import randint |
| 2 | +def qsort(a, start, end): |
| 3 | + """ quicksort in O(nlogn) and no extra |
| 4 | + memory. In place implementation |
| 5 | + >>> from random import sample |
| 6 | + >>> rand_list = [sample(range(100), 10) for j in range(10)] |
| 7 | + >>> sortedresult = [sorted(r) for r in rand_list] |
| 8 | + >>> for r in rand_list: qsort(r, 0, len(r)-1) |
| 9 | + >>> result = [sortedresult[i] == rand_list[i] for i in range(len(rand_list))] |
| 10 | + >>> print sum(result) |
| 11 | + 10 |
| 12 | + """ |
| 13 | + if start < end: |
| 14 | + p = choosepivot(start, end) |
| 15 | + if p != start: |
| 16 | + a[p], a[start] = a[start], a[p] |
| 17 | + equal = partition(a, start, end) |
| 18 | + qsort(a, start, equal-1) |
| 19 | + qsort(a, equal+1, end) |
| 20 | + |
| 21 | +def partition(a, l, r): |
| 22 | + """ partition array with pivot at a[0] |
| 23 | + in the array a[l...r] that returns the |
| 24 | + index of pivot element |
| 25 | + """ |
| 26 | + pivot, i = a[l], l+1 |
| 27 | + for j in range(l+1, r+1): |
| 28 | + if a[j] <= pivot: |
| 29 | + a[i],a[j] = a[j],a[i] |
| 30 | + i += 1 |
| 31 | + # swap pivot to its correct place |
| 32 | + a[l], a[i-1] = a[i-1], a[l] |
| 33 | + return i-1 |
| 34 | + |
| 35 | +def choosepivot(s, e): |
| 36 | + return randint(s,e) |
| 37 | + |
| 38 | +if __name__ == "__main__": |
| 39 | + import doctest |
| 40 | + doctest.testmod(verbose=True) |
0 commit comments