QuickSort on Python

import random
UnorderedList =[random.randint(1,10000) for i in range(100000)]
OrderedList= ['' for i in range(len(UnorderedList))]


def QuickSort( lists, OrderedLists,index):
    if len(lists)==0:
        return OrderedLists
    UList = []; LList =[]
    pivot = random.choice(lists)
    lists.remove(pivot)
    for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)
    OrderedLists[index+len(LList)]= pivot
    QuickSort(UList, OrderedLists, index+len(LList)+1)
    QuickSort(LList,OrderedLists,index)
    return OrderedLists


ans = QuickSort(UnorderedList, OrderedList,0)
print(ans)

Yesterday in school, we were going over sorting methods and I got introduced to quick sort which is known(ofc by the name) for being a very fast sorting method. My computing teacher also said the algorithm had recursion and generally was ‘involved’. He also said he didn’t expect any of our class to be able to program it which I took as a challenge to program it. So an hour into my Saturday and here is my solution.

Prerequisites:

This program does involve a few complex concepts which means I don’t believe it’s an appropriate program to be attempting to understand if you’re still a beginner to programming. So check yourself with these bullet points and if you meet them, then I think you could understand the code!:

• Recursion
• List Comprehension
• Functions and Parameters
• Knowledge of the other sorting methods such as Bubble, Insertion and Merge
• List Indexing

What is Quicksort?

From what I learnt yesterday, quick sort involves a randomly assigned pivot being chosen in a list and then the values of the list being arranged so that all greater values are to the right of the pivot while the smaller values are to the left of the list. This, as a result, means that our pivot will be in the correct position of the ordered list. We repeat this will the numbers above the pivot and also the numbers smaller than the pivot on the left of the list.

The circled numbers are the pivots and as you can see they are ordered using quicksort. When repeated, this will mean eventually all the numbers will be a pivot and therefore be placed in the correct position.

This method makes use of divide and conquer since we are immediately arranging the values into set halves(higher than the pivot and below the pivot) which in turn means this is applicable for very large lists. So for example when using the time module, it sorted an 100 element list ranging from integers 1–10,000 in 0.001232 seconds. Since it is divide and conquer, this means it O notation would be 0(n x log n) therefore 1000 elements took 0.2994 seconds and finally 100,000 elements in 0.543 seconds which is very fast. It does unfortunately get slower towards the bigger numbers with 1,000,000 elements taking 11.18 seconds but I will suggest a method at the end of the article which is a way of speeding up the program which will be your challenge if you want to adapt this code.

Since I have only learnt this yesterday, I’m not going to eliminate the chance that I’ve misunderstood the concept so please do tell me if I’ve made a mistake. I am going to note that normally you would work out a pivot but that is optional and so I didn’t include it since I believe it would actually slow down my program for lower n.

QuickSort - GeeksforGeeks

Code:

import random
UnorderedList =[random.randint(1,10000) for i in range(100000)]
OrderedList= ['' for i in range(len(UnorderedList))]

Initially, we import the random library in so we can use it to both make the unordered list and also to randomly choose a pivot. We then use a list comprehension using the random.randint method which chooses a random number between 1 and 10,000, this happens 100,000 times which means at the end of this, we have a list of 100,000 random elements which are unordered. I then create an ordered list which is going to be empty for now but it will slowly be filled with all the correctly ordered elements. For that reason, it is filled with ‘’s.

We make use of list comprehension twice so here is the syntax for list comprehension if you have forgotten

ans = QuickSort(UnorderedList, OrderedList,0)
print(ans)

Before going to the main function, I will explain these last 2 lines. This calls the function QuickSort and passes all the appropriate arguments and the returned value will be saved to the variable ans. We can then print that final result. I set it up as a variable first because in a real world application, you would want the sorted list for more processing realistically.

def QuickSort( lists, OrderedLists,index):
    if len(lists)==0:
        return OrderedLists
    UList = []; LList =[]
    pivot = random.choice(lists)
    lists.remove(pivot)
    for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)
    OrderedLists[index+len(LList)]= pivot
    QuickSort(UList, OrderedLists, index+len(LList)+1)
    QuickSort(LList,OrderedLists,index)
    return OrderedLists

This final part of the code is the actual function. Firstly, I will explain the parameters:

• Lists: This is the Unordered list which (since I want to reduce redundancy) I’m going to use as a way of checking whether everything has been sorted and therefore we can return the branch of the quick sort which would have been sorted
• OrderedList: This is the ordered list which we want to morph so that it is the ordered list of the elements in the unordered list
• Index: Since we want to append to the ordered list, we need to come up with a method to keep track of the index of specific parts branches of the code so when we append to the OrderedList, that we append into the correct index.

Using this diagram as an example, if we were using the sub-branch of 8,7,9 when we use the index() on that list although we are being returned 1for the number 7, in relation to the ordered list, we need to include all the other numbers is the lower number list to get the correct value of the index position to add to. So in this case we need to add 4 since we have the lower branch 1,3,2,5.

if len(lists)==0:
        return OrderedLists

This is the terminating condition of the program. Since the program is recursive we need a condition will stop the function from iterating. Since we want to finish once the unordered list is empty, I do this by saying once the length of the unordered list is 0 so empty. To make the unordered list needs to get to 0, we need to remove values from the unordered list once we add them to the ordered list.

UList = []; LList =[]
pivot = random.choice(lists)
lists.remove(pivot)

We create 2 new lists which are going to be the values in the list greater than the pivot and the values smaller than the pivot and separate them into 2 separate lists. We choose the pivot by randomly choosing an element from the unordered list, and and then since this value is now going to be in the correct position, we can remove this from the unordered list.

for i in lists:
        if i>pivot:
            UList.append(i)
        else:
            LList.append(i)

We now need to sort the Unordered list into the UList and LLower lists. To do this, we need to iterate through the unordered list and run a comparison to the values of the list to the pivot and depending on whether the statement is true or not, we append it to either of the 2 lists.

OrderedLists[index+len(LList)]= pivot
QuickSort(UList, OrderedLists, index+len(LList)+1)
QuickSort(LList,OrderedLists,index)

We then need to add this value into the ordered list(the pivot) since now it is going to be in the correct position once the lists have been arranged- it would simply be the index of the starting point of the list added to the length of the lower list. So we set this the index of the ordered list to the value of the pivot. Since we need to order the upper and lower lists now, we need to run the functions again on them new lists repeatedly to order out the lists which is where the recursion comes from running these lists into the function again. These will repeat the steps until the main list empties and then everything i returned back and then we have our ordered array. Since the lower list will start at the same position as the function iteration we are currently running, we pass just index into the function. Logically, we are just working from the same origin point but just using a smaller list. With the upper list its a bit more complicated since we need to have the start index be at the index above the position of the pivot and so we need to first add the index(the origin in case it isn't 0) then the length of the small list which will get us to the centre of the list and then add 1 more so we are on the area governed by the upper list.

Run this recursively and it will order the list in very quick time. There you go! You’ve completed a program for quick sort on python!

Challenge: As you saw, for 1,000,000 elements, it took the program 11 seconds to sort and this is too much. Your job is to add to the code in the function so that if any list passed into the function is only 3 elements long, then they simply add set those values into the ordered list. This is because when sorting into the Upperlist and LowerList, they will automatically mean the 3 values are sorted.