DEV Community

Cover image for Quick sort algorithm
Aya Bouchiha
Aya Bouchiha

Posted on • Edited on

2 1

Quick sort algorithm

Definition of quicksort

Quicksort is a type of Divide and Conquer algorithm like merge sort, it works by choosing an element as a pivot from the giving array, and appending the greater elements to the selected pivot, and shifting the smaller elements before it.

Time and Space complexity

The space complexity of quicksort is O(log n)

best-case average case worst-case
O(n log n) O(n log n) O(n^2) when the list is already sorted, or the pivot is min or max value of the giving list

Implementation of quick sort using python

def QuickSortAlgorithm(arr: list) -> list:
    """
        [ name ] => Quick Sort
        [ type ] => Sorting algorithms
        [ time complexity ] => (
            1. best case:  O(n log n)
            2. average case: O(n log n)
            3. worst case: O(n^2) { when the pivot is the (min or max) value of the giving list, or the list is already sorted }
        )
        [ space complexity ] => O(log n)
        [params] => (
            arr {list} list to sort
        )
        [return] => {list} sorted list 
    """
    # size of array
    n = len(arr)
    if n <= 1:
        return arr
    # pivote = arr[mid] 
    pivot = arr[n // 2]
    smallerThanPivot = []
    greaterThanPivot = []
    for i in range(len(arr)):
        # do not append pivot to (greaterThanPivot) => continue
        if arr[i] == pivot:
            continue
        # if the element is greater than or equal pivot
        if arr[i] >= pivot:
            # append the element that is greater than pivot to greaterThanPivot array
            greaterThanPivot.append(arr[i])
        else:
            # if the element is smaller than pivot append it to smallerThanPivot
            smallerThanPivot.append(arr[i])

    return QuickSortAlgorithm(smallerThanPivot) + [pivot] + QuickSortAlgorithm(greaterThanPivot)
Enter fullscreen mode Exit fullscreen mode

References and useful resources

#day_12

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️