Created
April 14, 2013 07:17
-
-
Save MercuryRising/5381772 to your computer and use it in GitHub Desktop.
quick sort in place
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def quick_sort_partition(sequence, left, right): | |
''' | |
In place sorts the subsequence of sequence[left:right] | |
''' | |
pivot_value = random.choice(sequence[left:right]) | |
pivot_index = sequence.index(pivot_value) | |
sequence[pivot_index], sequence[right] = sequence[right], sequence[pivot_index] | |
for index in range(left, right): | |
if sequence[index] <= pivot_value: | |
sequence[index], sequence[left] = sequence[left], sequence[index] | |
left += 1 | |
sequence[right], sequence[left] = sequence[left], sequence[right] | |
return left | |
def quick_sort_inplace(sequence, left=None, right=None): | |
''' | |
Quicksort randomly chooses a pivot value to populate a greater than or less than list. | |
Recursively calls quick_sort to create smaller and smaller sorted lists, until lists of length 1 or 0 remain. | |
''' | |
if left < right: | |
new_pivot = quick_sort_partition(sequence, left, right) | |
quick_sort_inplace(sequence, left, new_pivot-1) | |
quick_sort_inplace(sequence, new_pivot+1, right) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment