Yet another post for the crawlers to better index my site for algorithms and as a repository for Python code. The quick sort algorithm is well explained in the topmost Google search result for ‘Quick Sort Python Code’, but the code is unnecessarily convoluted. Instead, go with the code below.
In it, I assume the pivot to be the first element. You can easily add a function to randomize selection of the pivot. Choosing a random pivot minimizes the chance that you will encounter worst-case O(n2) performance. Always choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data.
| def quicksort(x): | |
| if len(x) == 1 or len(x) == 0: | |
| return x | |
| else: | |
| pivot = x[0] | |
| i = 0 | |
| for j in range(len(x)-1): | |
| if x[j+1] < pivot: | |
| x[j+1],x[i+1] = x[i+1], x[j+1] | |
| i += 1 | |
| x[0],x[i] = x[i],x[0] | |
| first_part = quicksort(x[:i]) | |
| second_part = quicksort(x[i+1:]) | |
| first_part.append(x[i]) | |
| return first_part + second_part | |
| alist = [54,26,93,17,77,31,44,55,20] | |
| quicksort(alist) | |
| print(alist) |
Also read:
Computing Work Done (Total Pivot Comparisons) by Quick Sort
Karatsuba Multiplication Algorithm – Python Code
Merge Sort
Discovering Python & R 
Hi, there is a bug in your code. When I use list = [18, 16, 17] to test you code, it returns [17, 16, 18].
LikeLike
Very very useful
Code is very easy to understand
Thank you
LikeLike
[…] Quick Sort Python Code Computing Work Done (Total Pivot Comparisons) by Quick […]
LikeLike
it doesn’t actually fully sort the list. output is:
[20, 26, 17, 31, 44, 54, 77, 55, 93]
LikeLike
Replace the ending with below to have it print correctly.:
alist = [54,26,93,17,77,31,44,55,20]
alist = quickSort(alist)
print alist
LikeLike
still did not work for me.
23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19 returns
‘ 1’, ‘ 11’, ‘ 14’, ‘ 15’, ‘ 17’, ‘ 19’, ‘ 27’, ‘ 29’, ‘ 31’, ‘ 37’, ‘ 4’, ‘ 43’, ‘ 49’, ‘ 56’, ‘ 64’, ‘ 78’, ‘ 91’, ‘ 99′, ’23’
LikeLike