-
-
Save vumaasha/1998240 to your computer and use it in GitHub Desktop.
Randomized Quick Sort in python
This file contains 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
| from random import randint | |
| def inPlaceQuickSort(A,start,end): | |
| if start<end: | |
| pivot=randint(start,end) | |
| temp=A[end] | |
| A[end]=A[pivot] | |
| A[pivot]=temp | |
| p=inPlacePartition(A,start,end) | |
| inPlaceQuickSort(A,start,p-1) | |
| inPlaceQuickSort(A,p+1,end) | |
| def inPlacePartition(A,start,end): | |
| pivot=randint(start,end) | |
| temp=A[end] | |
| A[end]=A[pivot] | |
| A[pivot]=temp | |
| newPivotIndex=start-1 | |
| for index in xrange(start,end): | |
| if A[index]<A[end]:#check if current val is less than pivot value | |
| newPivotIndex=newPivotIndex+1 | |
| temp=A[newPivotIndex] | |
| A[newPivotIndex]=A[index] | |
| A[index]=temp | |
| temp=A[newPivotIndex+1] | |
| A[newPivotIndex+1]=A[end] | |
| A[end]=temp | |
| return newPivotIndex+1 | |
| X=[4,5,7,4,3,6,0,4,22,45,82] | |
| inPlaceQuickSort(X,0,len(X)-1) | |
| #X=[0, 3, 4, 4, 4, 5, 6, 7, 22, 45, 82] |
when u swap the pivot and the last element, you do not need to create extra variable temp. you only need to do the following:
A[end], A[pivot] = A[pivot], A[end]
I guess second randint in not required
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Why you choose random pivot twice: before inPlacePartition call and after?