Introduction to Quick Sort
Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer paradigm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Key Concepts
- Pivot Selection: The element around which the partitioning is done.
- Partitioning: Rearranging the elements in the array so that elements less than the pivot come before it and elements greater than the pivot come after it.
- Recursion: The process of repeating the quick sort on the sub-arrays.
Quick Sort Algorithm
Steps
- Choose a Pivot: Select an element from the array. Common strategies include picking the first element, the last element, the middle element, or a random element.
- Partitioning: Rearrange the array such that all elements less than the pivot are on the left, and all elements greater than the pivot are on the right.
- Recursively Apply: Apply the same process to the left and right sub-arrays.
Pseudocode
function quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
function partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j = low to high - 1:
if arr[j] < pivot:
i = i + 1
swap arr[i] with arr[j]
swap arr[i + 1] with arr[high]
return i + 1Example
Let's sort the array [10, 7, 8, 9, 1, 5] using Quick Sort.
- Initial Array:
[10, 7, 8, 9, 1, 5] - Choose Pivot: Let's choose the last element
5as the pivot. - Partitioning:
- Compare each element with
5and rearrange:10 > 5(no swap)7 > 5(no swap)8 > 5(no swap)9 > 5(no swap)1 < 5(swap1with10)
- After partitioning:
[1, 7, 8, 9, 10, 5] - Swap pivot
5with7:[1, 5, 8, 9, 10, 7]
- Compare each element with
- Recursively Apply:
- Left sub-array:
[1](already sorted) - Right sub-array:
[8, 9, 10, 7]- Choose pivot
7, partition and sort recursively.
- Choose pivot
- Left sub-array:
Python 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
# Example usage
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)Explanation
- quick_sort: This function takes the array, the starting index (
low), and the ending index (high). It recursively sorts the array by partitioning it around a pivot. - partition: This function rearranges the elements in the array such that elements less than the pivot are on the left and elements greater than the pivot are on the right. It returns the index of the pivot element after partitioning.
Practical Exercises
Exercise 1: Basic Quick Sort
Sort the following array using Quick Sort: [3, 6, 8, 10, 1, 2, 1].
Solution:
Exercise 2: Custom Pivot Selection
Modify the Quick Sort algorithm to always choose the middle element as the pivot.
Solution:
def partition(arr, low, high):
mid = (low + high) // 2
arr[mid], arr[high] = arr[high], arr[mid]
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
# Example usage
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)Common Mistakes and Tips
- Choosing a Bad Pivot: Always choosing the first or last element as the pivot can lead to poor performance on already sorted arrays. Consider using a random or median element.
- Handling Duplicate Elements: Ensure that your partitioning logic correctly handles arrays with duplicate elements.
- Recursive Depth: Be mindful of the recursion depth, especially for large arrays. Python has a recursion limit which can be adjusted if necessary.
Conclusion
Quick Sort is a powerful and efficient sorting algorithm that uses the divide-and-conquer strategy. By understanding the pivot selection and partitioning process, you can implement Quick Sort effectively. Practice with different pivot selection strategies and arrays to deepen your understanding.