Algorithms Explained: Quicksort Today we’ll look at a very important sorting algorithm: . Quicksort is a sorting algorithm that employs a strategy. quicksort recursive divide-and-conquer I wont be explaining how recursion works as I’ve already wrote an article about that here. Since this is a divide-and-conquer algorithm we want to take a list of unsorted integers and split the problem down into two easier problems and then break each of those down…. and so on. To achieve this I’ll first cover quicksorts core operation: partitioning. It works as follows: >>> A = [6, 3, 17, 11, 4, 44, 76, 23, 12, 30]>>> partition(A, 0, len(A)-1)>>> print(A)[6, 3, 17, 11, 4, 23, 12, 30, 76, 44] So what happened here and how does it work? We need to pick some number as our . Our partition function takes 3 arguments, the , the in the list, and the . What we are trying to achieve here is that when we partition the list, everything to the left of the pivot is less than the and everything to the right is greater than the . For the first partition seen above, . After the partition we see some elements have changed position but everything to the left of 30 is less than it and everything to the right is greater than it. pivot list first element pivot pivot pivot 30 is our pivot So what does that mean for us? Well it means that 30 is now in its position in the list we now have two easier lists to sort. All of this is done so we are not creating new lists. correct AND in-place Lets look at the code: def partition(A, p, r): q = j = p while j < r:if A[j] <= A[r]:A[q], A[j] = A[j], A[q]q += 1 j += 1 A[q], A[r] = A[r], A[q] return q The at the end isn’t necessary for our partition but it is essential for sorting the entire list. The above code works its way across the list and maintains indices . return q A p, q, j, r is fixed and is the first element in the list. is the and is the last element in the list. Elements in the range are known to be less than or equal to the pivot and everything from are greater than the pivot. The only indices that change are and . At each step we compare with . If it is greater than the pivot it is in the correct position so we increment and move to the next element. If is less than we swap with After this swap, we increment , thus extending the range of elements known to be less than or equal to the pivot. We also increment to move to the next element to be processed. p r pivot A[p:q-1] A[q-1:r-1] q j A[j] A[r] j A[j] A[r] A[q] A[j]. q j Now onto the part. Remember it is a so it will continuously call on until there is nothing left to partition. quicksort recursive algorithm partition() Lets look at the code: def quicksort(A, p, r): if r <= p:return q = partition(A, p, r)quicksort(A, p, q-1)quicksort(A, q+1, r) return A Its that simple. All we do here is check if the index of the pivot, is less than or equal to the index of the start of our list we want to partition. If it is we return as whatever list was passed does not need to be partitioned any further. Otherwise, we partition the list , and call again on the two new . A quicksort sub lists Quicksort works best on large lists that are completely scrambled. It has really bad performance on lists that are almost sorted. Or in Big-O notation, the best case (scrambled) is O(n log(n)) and in the worst case, (almost or completely ordered list) is O( n^2). This topic is covered in further detail in our new book “Slither into Python” which you can now pre-order for just €5.99 — Our introduction to the Python programming language for beginners book, designed to take you from a complete beginner to a competent and skilled programmer in just 22 chapters, covering a whole range of topics. Check it out . HERE Slither into Python available to pre-order for 66% off.
