Quick Sort Algorithm
QuickSort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Core Concept
Quick Sort divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays. The steps are:
Pick an element from the array. This element is called the pivot.
Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
Visual Representation
Implementation
def partition(array, low, high):
# Choose the rightmost element as pivot
pivot = array[high]
# Pointer for greater element
i = low - 1
# Traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
def quick_sort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quick_sort(array, low, pi - 1)
# Recursive call on the right of pivot
quick_sort(array, pi + 1, high)
# Driver code
data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)
size = len(data)
quick_sort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)