Python Program to Implement Quick Sort
By Coder Scratchpad on in Python
Sorting is an essential part of programming, and learning how to sort efficiently can make your Python programs much faster and smarter. One of the most widely used and efficient sorting algorithms is Quick Sort. Unlike simpler methods like Bubble Sort or Insertion Sort, Quick Sort uses a clever divide-and-conquer strategy to organize data quickly. It’s an important algorithm for beginners to understand because it introduces concepts like partitioning, recursion, and efficient problem-solving.
Quick Sort is commonly used in real-world applications where speed matters, such as databases, search algorithms, and large-scale data analysis. The idea is simple: pick a pivot element, partition the list into smaller and larger elements, and recursively sort each part. While it may sound complex at first, step-by-step practice makes it accessible and highly rewarding for beginners learning Python.
Table of Contents
Toggle- Program 1: Quick Sort Using Recursion
- Program 2: Quick Sort Using In-Place Partitioning
- Program 3: Quick Sort in Descending Order
- Program 4: Quick Sort with First Element as Pivot
- Program 5: Quick Sort Using Middle Element as Pivot
- Program 6: Quick Sort for Generic Python Lists
- Frequently Asked Questions (FAQ)
- Conclusion
Program 1: Quick Sort Using Recursion
This program implements the standard recursive approach to Quick Sort. It selects a pivot, divides the list around the pivot, and sorts each part recursively.
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)
numbers = [10, 7, 8, 9, 1, 5]
sorted_numbers = quick_sort(numbers)
print("Sorted list:", sorted_numbers)
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)
numbers = [10, 7, 8, 9, 1, 5]
sorted_numbers = quick_sort(numbers)
print("Sorted list:", sorted_numbers)
In this program, the list is divided into three parts: elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. The function then recursively sorts the left and right parts and combines them with the middle part. Beginners will find this approach easy to understand because it clearly shows how dividing the problem into smaller pieces simplifies sorting.
Program 2: Quick Sort Using In-Place Partitioning
For larger lists, Quick Sort can be implemented more efficiently using in-place partitioning. This method avoids creating extra lists and reduces memory usage.
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
def quick_sort_inplace(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
return arr
numbers = [12, 4, 5, 6, 7, 3, 1, 15]
sorted_numbers = quick_sort_inplace(numbers, 0, len(numbers) - 1)
print("Sorted list using in-place Quick Sort:", sorted_numbers)
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
def quick_sort_inplace(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
return arr
numbers = [12, 4, 5, 6, 7, 3, 1, 15]
sorted_numbers = quick_sort_inplace(numbers, 0, len(numbers) - 1)
print("Sorted list using in-place Quick Sort:", sorted_numbers)
This program uses a pivot to partition the list within the same array, swapping elements to place smaller ones on the left and larger ones on the right. Then it recursively sorts each partition. Beginners will learn how in-place sorting saves memory and improves performance, while still reinforcing the concepts of recursion and partitioning.
Program 3: Quick Sort in Descending Order
Quick Sort can be adapted to sort a list from largest to smallest by changing the comparison during partitioning. This version ensures that higher values come first.
def quick_sort_desc(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_desc(left) + middle + quick_sort_desc(right)
numbers = [8, 4, 23, 42, 16, 15]
sorted_numbers = quick_sort_desc(numbers)
print("Sorted list in descending order:", sorted_numbers)
def quick_sort_desc(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_desc(left) + middle + quick_sort_desc(right)
numbers = [8, 4, 23, 42, 16, 15]
sorted_numbers = quick_sort_desc(numbers)
print("Sorted list in descending order:", sorted_numbers)
This program works similarly to the standard Quick Sort but reverses the comparison to sort in descending order. Beginners can see how a small change in logic affects the sorting order without changing the overall structure of the algorithm.
Program 4: Quick Sort with First Element as Pivot
This version of Quick Sort selects the first element as the pivot. It shows how the choice of pivot can slightly affect the algorithm’s performance while achieving the same final sorted list.
def quick_sort_first_pivot(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort_first_pivot(left) + [pivot] + quick_sort_first_pivot(right)
numbers = [4, 2, 6, 9, 3]
print("Original List:", numbers)
sorted_numbers = quick_sort_first_pivot(numbers)
print("Sorted List:", sorted_numbers)
def quick_sort_first_pivot(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort_first_pivot(left) + [pivot] + quick_sort_first_pivot(right)
numbers = [4, 2, 6, 9, 3]
print("Original List:", numbers)
sorted_numbers = quick_sort_first_pivot(numbers)
print("Sorted List:", sorted_numbers)
Using the first element as pivot introduces beginners to the idea that pivot selection can influence the efficiency of Quick Sort. It is useful for understanding the flexibility of the algorithm.
Program 5: Quick Sort Using Middle Element as Pivot
Choosing the middle element as a pivot helps balance partitions and can prevent worst-case performance when the list is already nearly sorted. This program shows how to implement Quick Sort using the middle element.
def quick_sort_middle_pivot(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
pivot = arr[mid]
left = [x for i, x in enumerate(arr) if x <= pivot and i != mid]
right = [x for i, x in enumerate(arr) if x > pivot and i != mid]
return quick_sort_middle_pivot(left) + [pivot] + quick_sort_middle_pivot(right)
numbers = [9, 3, 7, 5, 6, 2]
print("Original List:", numbers)
sorted_numbers = quick_sort_middle_pivot(numbers)
print("Sorted List:", sorted_numbers)
def quick_sort_middle_pivot(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
pivot = arr[mid]
left = [x for i, x in enumerate(arr) if x <= pivot and i != mid]
right = [x for i, x in enumerate(arr) if x > pivot and i != mid]
return quick_sort_middle_pivot(left) + [pivot] + quick_sort_middle_pivot(right)
numbers = [9, 3, 7, 5, 6, 2]
print("Original List:", numbers)
sorted_numbers = quick_sort_middle_pivot(numbers)
print("Sorted List:", sorted_numbers)
Using the middle element as a pivot can improve the efficiency of Quick Sort in some cases. Beginners can understand how pivot selection affects performance and learn the importance of considering edge cases.
Program 6: Quick Sort for Generic Python Lists
Python’s dynamic typing allows Quick Sort to work on different data types, such as strings, in the same way it works on numbers. This program demonstrates a generic approach.
def quick_sort_generic(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quick_sort_generic(left) + [pivot] + quick_sort_generic(right)
words = ['banana', 'apple', 'cherry', 'date']
print("Original List:", words)
sorted_words = quick_sort_generic(words)
print("Sorted List:", sorted_words)
def quick_sort_generic(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x <= pivot]
right = [x for x in arr[:-1] if x > pivot]
return quick_sort_generic(left) + [pivot] + quick_sort_generic(right)
words = ['banana', 'apple', 'cherry', 'date']
print("Original List:", words)
sorted_words = quick_sort_generic(words)
print("Sorted List:", sorted_words)
This generic approach shows that Quick Sort can handle multiple data types in Python. Beginners can see how the same algorithm applies to numbers, strings, and other comparable elements, making it versatile for real-world applications.
Frequently Asked Questions (FAQ)
Quick Sort often raises questions for beginners. Here are some answers to make it easier to understand.
Q1: What is the time complexity of Quick Sort?
Quick Sort has an average time complexity of O(n log n), but in the worst case, it can degrade to O(n²). Proper pivot selection usually prevents the worst-case scenario.
Q2: Is Quick Sort stable?
No, Quick Sort is not stable by default. Equal elements may change their relative order during sorting.
Q3: Can Quick Sort be used on linked lists?
Yes, Quick Sort can be adapted for linked lists, but Merge Sort is often preferred because it handles linked structures more efficiently.
Q4: How does Quick Sort compare to Merge Sort?
Quick Sort is usually faster and uses less memory, but Merge Sort guarantees O(n log n) performance and is stable.
Q5: Can Quick Sort be implemented iteratively?
Yes, iterative Quick Sort is possible using a stack to simulate recursion, which is useful for very large lists.
Conclusion
Quick Sort is a foundational algorithm for Python programmers. It introduces recursion, partitioning logic, and efficient problem-solving strategies. In this article, we explored multiple implementations, including recursion, descending order, different pivot selections, and generic data types.
For beginners, practicing Quick Sort with different pivot choices and data types will strengthen algorithmic thinking and coding skills. Mastering Quick Sort provides a strong foundation for solving more complex programming challenges and optimizing data handling in Python.