Quick Sort
An efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order using a pivot.
Visualization
Details
Analogy
Imagine a teacher sorting exam papers by score. They pick one paper (the 'pivot'), say with a score of 85. They then create two piles: papers with scores lower than 85 and papers with scores higher than 85. They repeat this process on the two smaller piles until all the papers are sorted.
Purpose
To sort an array by picking an element as a pivot and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
Use Cases
One of the most widely used sorting algorithms. It's the default in many programming language libraries due to its good average-case performance.
Algorithm Steps
function quickSort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
quickSort(arr, low, pivot-1)
quickSort(arr, pivot+1, high)
function partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j = low to high-1:
if arr[j] < pivot:
i++
swap arr[i] with arr[j]
swap arr[i+1] with arr[high]
return i+1
Explanation
What's Happening?
Initial array. Let's partition the whole array. Pivot is 70 (last element).
Code Implementation
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1