SHOW:
|
|
- or go back to the newest paste.
| 1 | def qsort2(array): | |
| 2 | - | array,pI = partition(array) |
| 2 | + | try: |
| 3 | - | return partition(array[:pI])[0]+[array[pI]]+partition(array[pI+1:])[0] |
| 3 | + | array,pI = partition(array) |
| 4 | return qsort2(array[:pI])+[array[pI]]+qsort2(array[pI+1:]) | |
| 5 | except: | |
| 6 | return array | |
| 7 | ||
| 8 | def partition(array): | |
| 9 | print("before: ",array)
| |
| 10 | if len(array) > 1: | |
| 11 | pivot = array[0] | |
| 12 | pivIndex = 0 | |
| 13 | i,j = 1,1 | |
| 14 | while j < len(array) - 1: | |
| 15 | if array[j] < pivot: | |
| 16 | temp = array[i] | |
| 17 | array[i] = array[j] | |
| 18 | array[j] = temp | |
| 19 | i += 1 | |
| 20 | j += 1 | |
| 21 | temp = array[i-1] | |
| 22 | array[i-1] = array[pivIndex] | |
| 23 | array[pivIndex] = temp | |
| 24 | pivIndex = i-1 | |
| 25 | print("after",array)
| |
| 26 | return array,pivIndex | |
| 27 | else: | |
| 28 | print("after",array)
| |
| 29 | return array | |
| 30 | ||
| 31 | print([3,8,2,5,1,4,7,6]) | |
| 32 | print(qsort2([3,8,2,5,1,4,7,6])) |
