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
Anirudh Jayaraman 
Leave a comment