Quick Sort 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 the other array holds values greater than the pivot value.
Algorithm Steps
- Choose a Pivot: Choose an element from the array as the pivot. The choice of pivot can be random or fixed.
- Partition: Rearrange elements in the array so that all elements less than the pivot come before it, while all elements greater than the pivot come after it. After this step, the pivot is in its final sorted position.
- Recursively Apply: Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.
Example
Here's a simple implementation of Quick Sort in Python:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Test the function
example_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(example_array)
print(sorted_array)
Performance
Quick Sort is a divide-and-conquer algorithm. It has an average and worst-case complexity of O(n log n), making it very efficient for large datasets.
Resources
For more information on Quick Sort, you can read our detailed Quick Sort Guide.