Update the QuickSort Algorithm to minimise chance of O(n^2)

[faiqali1]

According to this question on StackOverflow it is better to use the median or a random value as a pivot.

Currently the implementation uses the last element as the pivot.

def quick_sort(collection: list) -> list:
    if len(collection) < 2:
        return collection
    pivot = collection.pop()  # <-- Use the last element as the first pivot
    greater: list[int] = []  
    lesser: list[int] = []  
    for element in collection:
        (greater if element > pivot else lesser).append(element)
    return quick_sort(lesser) + [pivot] + quick_sort(greater)

[lt77777]

I can fix this

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[mahi072]

Hi @faiqali1, I would like to contribute in this issue. Is it still open? Please guide me through this.

[Ashutosh2613]

I would like to work on this issue.

[faiqali1]

Hi @mahi072 And @Ashutosh2613,

Yeah, the issue is still open. Apologies for the late reply.

The current issue, as stated in the title is that, it is better to choose the pivot at a random point then choosing the last element every time.

So using the Random module, choose a Random point between 0 & the length of the array and use that as a pivot.

[Kate-Way]

HI @faiqali1! I'm new to contribution process. I can't find how fork this question, but here is the code:

import random

def quick_sort(collection: list) -> list:
    if len(collection) < 2:
        return collection
    pivot = random.choice(collection)  
    greater: list[int] = []
    lesser: list[int] = []
    for element in collection:
        (greater if element > pivot else lesser).append(element)
    return quick_sort(lesser) + quick_sort(greater)

[Ashutosh2613]

@faiqali1 Changes are made, please do review the changes!

[ruchikayadav1408]

@faiqali1 heyyy shall i work on this?