Quick Sort

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 sub lists are recursively called to sort the elements in list. The selection of pivot can decide the efficiency of the quick sort.

Illustration:

Qsort.gif

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(n2)
  • Average Case: O(nlogn)
  • Best Case: O(nlogn) Space Complexity: O(logn)

    Program for Quick Sort:

def partition(data,low,high): 
    i = ( low-1 )         # Index of smaller element 
    pivot = data[high]     # Pivot Value

    for j in range(low , high): 

        if   data[j] < pivot:         # If current element is smaller than the pivot 

            i = i+1             # Increment index of smaller element 
            data[i],data[j] = data[j],data[i]   
    data[i+1],data[high] = data[high],data[i+1] 
    return ( i+1 ) 


def quickSort(data, low, high):
    if low < high:

        # Select pivot position and put all the elements smaller than pivot on left and greater than pivot on right
        pi = partition(data, low, high)

        # Sort the elements on the left of pivot
        quickSort(data, low, pi - 1)

        # Sort the elements on the right of pivot
        quickSort(data, pi + 1, high)

inp=input("Enter the data: ").split()
data=[]
for i in inp:
    data.append(int(i))
quickSort(data, 0, len(data) - 1)
print('Sorted list in Ascending Order:')
print(data)

Output

quicksort.png

Explanation

quicksortillust.png