Quicksort is a popular and efficient sorting algorithm in computer science used for sorting large data sets. In this article, you will delve into understanding Quicksort in Python, covering its basics and applications. You will learn about the Quicksort algorithm workflow in Python and its step-by-step implementation through practical examples. Additionally, this article explores advanced Quicksort techniques, including an iterative implementation and useful optimisation strategies to improve the performance of the Quicksort algorithm. With this knowledge, you will be able to harness the power of Quicksort in Python and apply it effectively to your programming projects.
Basics of Quicksort Algorithm in Python
Quicksort is an efficient sorting algorithm developed by Tony Hoare in 1959. It is a comparison-sort algorithm that works based on the divide-and-conquer technique, which means that the algorithm divides the input into smaller pieces, sorts them individually, and combines the sorted pieces to build the final output.
The main concept of Quicksort is to choose a pivot element from the array and partition the other elements into two groups - one with the elements less than the pivot and the other with the elements greater than the pivot. This process is done recursively for the sub-arrays until the entire array is sorted.
The time complexity of Quicksort is as follows:
- Best case: \( O(n\log n) \)
- Average case: \( O(n\log n) \)
- Worst case: \( O(n^2) \)
However, in practice, Quicksort tends to perform much better than its worst-case complexity, making it one of the most popular
sorting algorithms.
Application of Quicksort in Python
To implement the Quicksort algorithm in
Python, it is essential to focus on the following aspects:
- The choice of pivot
- The partition function
- Recursive implementation
There are several techniques to choose the pivot, such as selecting the first, middle, or last element or using the median of three (first, middle, and last elements). The choice of pivot has a significant impact on the overall performance of the algorithm.
An example of implementing Quicksort in Python using the last element of the list as a pivot:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr.pop()
lesser = []
greater = []
for x in arr:
if x <= pivot:
lesser.append(x)
else:
greater.append(x)
return quicksort(lesser) + [pivot] + quicksort(greater)Python Quicksort Algorithm Workflow
The workflow of the Quicksort algorithm in Python can be broken down into the following main steps:
- Choose a pivot element from the list.
- Partition the list around the pivot, such that elements less than the pivot are placed before the pivot, and elements greater than the pivot are placed after the pivot.
- Recursively apply the Quicksort algorithm on the two sub-arrays (elements smaller than the pivot and elements bigger than the pivot) until all arrays are sorted.
Let us walk through an example to see how the Quicksort algorithm works in Python:
| Array: | 5, 3, 8, 4, 2 |
| Pivot: | 2 |
| Partitioned Array: | [2] | [5, 3, 8, 4] |
| Recursive call on left sub-array: | (Nothing to sort) |
| Recursive call on right sub-array: | Quicksort([5, 3, 8, 4]) |
Following the algorithm recursively, the array will be sorted as follows: Final Sorted Array: [2, 3, 4, 5, 8]
Quicksort is an in-place sorting algorithm, which means that it does not require additional memory for sorting. However, the recursive implementation shown above does not showcase an in-place version, as it creates new lists for partitioning. In practice, Quicksort can be implemented to sort the array in place without the need for additional memory.
Understanding the basics of the Quicksort algorithm and its implementation in Python is essential for any computer science student. It is a highly efficient sorting method, and the knowledge of its workings will come in handy in various programming scenarios and applications.
Quicksort Implementation in Python: Examples
In order to understand the Quicksort code in Python thoroughly, let's break down the implementation into a sequence of steps. Step 1: Choose a pivot element
- Selecting an appropriate pivot is crucial for the efficiency of the algorithm. Common strategies include selecting the first, middle, or last element, or using the median of three elements (first, middle, and last).
Step 2: Partition the array
- Next, rearrange the array such that elements smaller than the pivot are placed before it and elements greater than the pivot are placed after it. This step is commonly called 'partitioning'.
Step 3: Recursive Quicksort
- Finally, recursively apply the Quicksort algorithm on the two sub-arrays (elements less than the pivot and elements greater than the pivot) until the base case is reached (an empty array or an array of size 1).
Here is an example of Quicksort implementation in Python using the last element as the pivot:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr.pop()
lesser = []
greater = []
for x in arr:
if x <= pivot:
lesser.append(x)
else:
greater.append(x)
return quicksort(lesser) + [pivot] + quicksort(greater)In-Place Quicksort Python Implementation
The previously shown implementation, though valid, is not an in-place sorting algorithm, as it creates new lists during partitioning. The in-place variant of Quicksort does not require additional memory during the sorting process. This section will cover the in-place implementation of Quicksort in
Python: Step 1: Choose a pivot element
- Similar to the previous implementation, select an appropriate pivot.
Step 2: Define the partition function
- Create a partition function that takes the array, a starting index, and an ending index as input arguments. This function will rearrange the elements around the pivot and return the index of the new pivot location.
Step 3: Define the in-place Quicksort function
- Define the function that takes an array, a starting index, and an ending index as input arguments. This function will perform the in-place Quicksort by calling the partition function and then recursively sorting the sub-arrays.
Here is the complete code for the in-place Quicksort implementation in Python:
def partition(arr, low, high):
pivot_idx = (low + high) // 2
arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
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
def quicksort_inplace(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quicksort_inplace(arr, low, pivot_index - 1)
quicksort_inplace(arr, pivot_index + 1, high)To use the in-place Quicksort function, call it like this:
arr = [10, 3, 8, 4, 2]
quicksort_inplace(arr, 0, len(arr) - 1)
In summary, understanding the detailed implementation of the Quicksort algorithm in Python, particularly the in-place version, is important for computer science students and aspiring programmers who want to enhance their understanding of
sorting algorithms and efficient problem-solving techniques using Python.
Advanced Quicksort Techniques
While the traditional Quicksort algorithm relies on recursion, it is also possible to implement an iterative version using a stack. The iterative approach may be helpful when dealing with extremely large data sorting tasks, as it can avoid the risk of running into recursion depth limitations. This section will delve into the details and necessary steps to implement an iterative Quicksort algorithm in Python. To begin with, let's understand the main components of the iterative Quicksort algorithm:
- Create a stack to keep track of the indices of the elements to be sorted.
- While the stack is not empty, pop the top two elements (representing the lower and upper bounds of the sub-array) from the stack.
- Partition the sub-array and obtain the index of the new pivot location.
- Push the indices of the left and right sub-arrays onto the stack for further partitioning and sorting.
The following code demonstrates an iterative Quicksort implementation in Python:
def partition(arr, low, high):
pivot_idx = (low + high) // 2
arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
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
def quicksort_iterative(arr):
stack = [(0, len(arr) - 1)]
while stack:
low, high = stack.pop()
if low < high:
pivot_index = partition(arr, low, high)
stack.append((low, pivot_index - 1))
stack.append((pivot_index + 1, high))An essential aspect of transforming the Quicksort algorithm from recursive to iterative is to replace the recursive calls with stack operations, thus managing the sorting process using a stack while avoiding stack overflows that can occur during deep recursion.
Optimising the Python Quicksort Algorithm
There are several techniques that can be applied to optimise the performance of the Quicksort algorithm in
Python: 1. Choose an Effective Pivot-Selection Strategy:
- Randomised pivot: Select a random element from the list as the pivot. This introduces randomisation into the algorithm, which can help avoid worst-case scenarios.
- Median of three: Choose the median of the first, middle, and last elements of the list as the pivot. This approach tends to improve the partitioning efficiency, hence, speeding up the algorithm.
2. Limit Recursion Depth:
- Using a hybrid approach where you switch to a simpler sorting algorithm (e.g., Insertion Sort) for small sub-arrays can prevent excessive recursive calls and improve the overall performance.
3. Parallelise Quicksort:
- Another performance optimisation technique is to parallelise the algorithm by dividing the list into smaller parts and sorting each part concurrently using multiple processing units or threads.
4. Tail Call Elimination:
- By identifying the larger and smaller sub-array after partitioning, you can eliminate one of the recursive calls by sorting the smaller sub-array first. This reduces the number of function calls and the associated overhead.
Each of these optimisation techniques aims to enhance the efficiency and performance of the Quicksort algorithm in
Python. The choice of optimisation methods depends on the specific application requirements, available resources, and the nature of the input data being sorted. By leveraging advanced concepts like iterative implementations and algorithm optimisations, you can make Quicksort an even more powerful and efficient sorting tool for various programming scenarios.
Quicksort Python - Key takeaways
Quicksort Python: efficient sorting algorithm based on the divide-and-conquer technique; works by selecting a pivot element and partitioning other elements into groups based on their relation to the pivot
Time complexity: Best case and Average case: O(n log n); Worst case: O(n^2)
Quicksort implementation: Python code that sorts a given list by selecting a pivot, partitioning the list, then recursively applying Quicksort to sub-arrays
In-place Quicksort Python implementation: sorts the array without additional memory, using functions for partitioning and recursive sorting based on indices
Iterative Quicksort Python: alternative Quicksort approach using a stack to avoid recursion depth limitations, particularly useful for sorting large data sets
Explanations 
Textbooks 
Exams 
Magazine 
