QuickSort Algorithm (Python)

Question

This is my implementation of Quick Sort Algorithm :

def quick_sort(sequence):
 if len(sequence)<= 1:
 return sequence
 else:
 pivot = sequence.pop() # To take the last item of "sequence" list
 
 greater =[] 
 lower = []
 
 for n in sequence:
 if n > pivot : 
 greater.append(n)
 else:
 lower.append(n)
""" return the quiqk sorted "lower" and "greater" lists ,and pivot as a list in between """
 return quick_sort[lower] + [pivot] + quick_sort[greater]

How can I improve it ?

Answer 1

The main single advantage of quicksort is that it sorts in-place. Your implementation does not. It requires an additional memory for left and right lists, linear in terms of the initial array length.

Returning the concatenation of the three lists also doesn't help performance.

An obvious improvement is to reimplement it in-place.

Answer 2

1. In-place quicksort:
   You can make your quicksort inplace, so that it only uses O(log(N)) memory or O(1) memory. Memory is how much computer data your function uses (different from speed).

2. Choosing a better pivot:
   Choosing the last element as your pivot will make quicksort converge to O(N2) for sorted lists, which is quite common in real world scenarios. O(N2) is very, very slow so you definitely do not want to choose the last element as your pivot. Here are some pivots that you can consider:

   • The middle element of your list. If you choose this, you will not get O(N2) time for nearly sorted lists, but it's still very easy to make a list that makes your program go to O(N2) time complexity. I wouldn't recommend this, although it's still better than the one you have currently.

   • The Mo3 approach. This is where your pivot is the median of the first, middle and last element of your list. Although still possible, it's unlikely that it will approach O(N2) time complexity. Since the median of 3 is still relatively easy to compute, you should definitely consider this.

   • A random element from your list. You can choose a random element from your list by

     import random
     random.choice(sequence)
     

     Choosing a random variable will make going to O(N^2) time nearly impossible. However, finding a random variable is slightly time costly (Mo3 is faster to find, but there's a very slight chance it might become incredibly slow).

3. Insertion Sorting. For lists of size 10 or less, sort the rest of the list using insertion sort instead. Insertion sort, although an O(N2) time complexity, is faster than quicksort for lists of size 10 or less. You can implement it into your code like this:

   def quick_sort(sequence):
    if len(sequence) <= 10:
    insertionsort(sequence)
    return sequence
   

   Keep in mind that you will have to implement insertion sort. I would recommend https://www.geeksforgeeks.org/insertion-sort/ if you do not already know what insertion sort is.