Quick Sort

Quick Sort is an algorithm for sorting which is based on divide and conquer approach. An element is chosen as pivot and partitions the given list. The elements are swapped, based on comparison with pivot value, in order to obtain a sorted list. The partitioned sublists are recursively called to sort the elements in list. The selection of pivot can decide the efficiency of the quick sort.

Illustration:

Algorithm:

partition(list,lowestIndex,highestIndex)

    pointerI=lowestIndex-1

    pivot=Element at highestIndex

    for pointerJ from lowestIndex to HighestIndex

        if ElementAtpointerJ < pivot

            pointerI=pointerI+1

            swap ElementAtpointerI with ElementAtpointerJ

    swap Element at pointerI+1 with pivot

    return i+1

quickSort(list,lowestIndex,highestIndex)

    if lowestIndex < highestIndex

        pivotIndex=partition(list,lowestIndex,highestIndex)    

        recursiveCall on left part, quickSort(list,lowestIndex,pivotIndex-1)

        recursiveCall on right part, quickSort(list,pivotIndex+1,highestIndex)

Time Complexity:

• Worst Case: O(n²)
• Average Case: O(nlogn)
• Best Case: O(nlogn)

Space Complexity: O(logn)

Program for Quick Sort:

Output:

Explanation: