Quicksort is a fantastic, versatile sorting algorithm that, as the name suggests, tends to be quite fast. It was developed by Tony Hoare in 1959 and is one of the most efficient sorting algorithms to this date, using a divide-and-conquer approach. Let's delve into the basics of Quicksort and see a working example in Python.
### Background
Quicksort operates by first dividing a large array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays. A `pivot` is chosen from the array, and partitioning is done such that elements less than `pivot` are moved before it and elements greater than `pivot` come after it.
### Python Implementation
Let us walk through the Python code for a simple Quicksort implementation.
```python
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
#if current element is smaller than pivot
if arr[j] <= pivot:
i = i+1 #increase index of smaller element
arr[i], arr[j] = arr[j], arr[i] #swap
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quicksort(arr, low, high):
if low < high:
#index
pi = partition(arr, low, high)
quicksort(arr, low, pi-1)
quicksort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quicksort(arr, 0, n-1)
In the above code:
The partition() function takes last element as pivot, starts from the leftmost element, and makes all elements on the left lower than the pivot and all elements on the right higher than the pivot. It returns pivot's correct position in the sorted array.
The quicksort() function calls partition() to get the pivot position, then recursively calls itself for the two parts divided at the pivot position.
You can print the array after sorting with print("Sorted array is:", arr).
Quicksort is famed for its efficiency and speed, which is why it's widely used. The above Python implementation demonstrates its elegance, highlighting the beauty of the divide-and-conquer approach.
In future posts, I'll explore other sorting algorithms, how they compare, and where each is ideally used. Stay tuned!