Python Quick Sort Tutorial
last modified March 8, 2025
In this article, we explain the Quick Sort algorithm and demonstrate its use in Python.
An algorithm is a step-by-step procedure for solving a problem or performing a computation. Algorithms are fundamental to computer science and programming.
Sorting is the process of arranging data in a specific order, such as ascending or descending. Sorting is a common operation in programming.
Common Sorting Algorithms
Some common sorting algorithms include:
- Quick Sort
- Merge Sort
- Bubble Sort
- Insertion Sort
- Selection Sort
Quick Sort Algorithm
Quick Sort is a divide-and-conquer algorithm. 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.
Quick Sort Example
The following is a Python implementation of the Quick Sort algorithm.
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)
# Example usage
numbers = [3, 6, 8, 10, 1, 2, 1]
sorted_numbers = quick_sort(numbers)
print("Sorted numbers:", sorted_numbers)
words = ["banana", "apple", "cherry", "date"]
sorted_words = quick_sort(words)
print("Sorted words:", sorted_words)
The quick_sort function sorts a list of numbers or words in ascending order.
$ ./quick_sort.py Sorted numbers: [1, 1, 2, 3, 6, 8, 10] Sorted words: ['apple', 'banana', 'cherry', 'date']
Sorting in Descending Order
To sort in descending order, we can modify the Quick Sort function.
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)
# Example usage
numbers = [3, 6, 8, 10, 1, 2, 1]
sorted_numbers_desc = quick_sort_desc(numbers)
print("Sorted numbers (descending):", sorted_numbers_desc)
words = ["banana", "apple", "cherry", "date"]
sorted_words_desc = quick_sort_desc(words)
print("Sorted words (descending):", sorted_words_desc)
The quick_sort_desc function sorts a list in descending order.
$ ./quick_sort_desc.py Sorted numbers (descending): [10, 8, 6, 3, 2, 1, 1] Sorted words (descending): ['date', 'cherry', 'banana', 'apple']
Comparing Quick Sort with Insertion Sort
Quick Sort is generally faster than Insertion Sort for large datasets. Let's compare their performance using a benchmark.
import time
import random
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)
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Generate a large list of random numbers
data = [random.randint(0, 1000) for _ in range(10000)]
# Benchmark Quick Sort
start_time = time.time()
quick_sort(data.copy())
quick_sort_time = time.time() - start_time
# Benchmark Insertion Sort
start_time = time.time()
insertion_sort(data.copy())
insertion_sort_time = time.time() - start_time
print(f"Quick Sort time: {quick_sort_time:.6f} seconds")
print(f"Insertion Sort time: {insertion_sort_time:.6f} seconds")
The benchmark compares the time taken by Quick Sort and Insertion Sort to sort a list of 10,000 random numbers.
Source
In this article, we have explained the Quick Sort algorithm and demonstrated its use in Python.
Author
List all Python tutorials.