|
Revision 35, 470 bytes
(checked in by simon, 5 years ago)
|
|
Functional language style Python implementation of Qsort.
|
-
Property svn:mime-type set to
text/python-source
-
Property svn:eol-style set to
native
|
| Line | |
|---|
| 1 | import random |
|---|
| 2 | |
|---|
| 3 | def qsort(a): |
|---|
| 4 | if not a: |
|---|
| 5 | return [] |
|---|
| 6 | |
|---|
| 7 | # choose median of three random values as pivot |
|---|
| 8 | if len(a) > 2: |
|---|
| 9 | i3 = [ (i, a[i]) for i in random.sample(xrange(len(a)),3) ] |
|---|
| 10 | i3.remove(max(i3, key = lambda x: x[1])) |
|---|
| 11 | i3.remove(min(i3, key = lambda x: x[1])) |
|---|
| 12 | i = i3[0][0] |
|---|
| 13 | else: |
|---|
| 14 | i = 0 |
|---|
| 15 | |
|---|
| 16 | pivot = a[i] |
|---|
| 17 | del a[i] |
|---|
| 18 | |
|---|
| 19 | return qsort([x for x in a if x <= pivot]) + [pivot] + qsort([x for x in a if x > pivot]) |
|---|
