Quick Sort is a sorting algorithm, that uses divide and conquer to solve it. The steps are simple in Quick Sort.

1. We first need to find the pivot index. From there, we split the array into two parts, one part where the numbers are lower than the pivot and one part where the numbers are bigger than the pivot.
2. We do this until the arrays are split up into size one.
3. From there, we build the array back up, but instead of sorting each time like mergesort, we already know the places of the indexes.

Here is a sample code in Python: (From GeeksforGeeks)

def partition(start, end, array):
     
    pivot_index = start
    pivot = array[pivot_index]
     
    while start < end:
         
        while start < len(array) and array[start] <= pivot:
            start += 1
             
        while array[end] > pivot:
            end -= 1

        if(start < end):
            array[start], array[end] = array[end], array[start]

    array[end], array[pivot_index] = array[pivot_index], array[end]
    return end
     
def quick_sort(start, end, array):
     
    if (start < end):
         
        p = partition(start, end, array)
        quick_sort(start, p - 1, array)
        quick_sort(p + 1, end, array)

array = [ 10, 7, 8, 9, 1, 5 ]
quick_sort(0, len(array) - 1, array)
 
print("Sorted Array: {}".format(array))

Now you may be wondering, why use Quick Sort? Quick Sort’s best case runs in O(Nlog(N)), the fastest operation of sorting.

Quicksort and Mergesort are quite similar, leading us to think which one we should use. Generally, Quicksort is faster O(Nlog(N)) than Merge Sort, so it should be used for smaller data sets, while mergesort should be used for larger data sets.

That’s it for Today’s Lesson. For more information, go to

https://www.geeksforgeeks.org/quick-sort/

Thank you!