• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Quick Sort

← Previous Next →

Quick sort is one of the most powerful and widely used sorting algorithms. It is much faster than basic methods like selection sort or insertion sort, especially when dealing with large datasets. Quick sort works by choosing a pivot and arranging values so that smaller elements move to one side and larger ones move to the other. This process continues on each side until the entire list is sorted.

In this tutorial, you’ll learn how quick sort works, what pivot selection means, why the divide-and-conquer technique makes it so fast, how to implement the algorithm in Python, and when quick sort performs well. By the end of this lesson, you’ll understand why quick sort is a favorite in real applications.

What Is Quick Sort?

Quick sort is a divide-and-conquer sorting algorithm. It picks a pivot value and rearranges the list so that all values smaller than the pivot move to the left side and all values greater than the pivot move to the right side. Once this partition step is completed, quick sort repeats the same logic on each side.

Quick sort breaks the problem into smaller pieces and sorts them independently, which makes the algorithm fast and efficient.

How Quick Sort Works Step by Step

Let’s take this list:

[8, 3, 1, 7, 0, 10, 2]

Step 1: Choose a pivot

Let’s pick the last element 2 as the pivot.

Step 2: Partition the list

Rearrange values:

  • Elements less than pivot → move to left

  • Elements greater than pivot → move to right

After partitioning around 2, the list becomes:

[1, 0, 2, 7, 3, 10, 8]

(Exact rearrangement may differ depending on the partition logic.)

Step 3: Apply quick sort on the left side

Left list:

[1, 0]

Pivot = 0
After partition → [0, 1]

Step 4: Apply quick sort on the right side

Right list:

[7, 3, 10, 8]

Pick pivot = 8
Rearrange around 8 → [7, 3, 8, 10]

Split again and keep sorting until all parts are finished.

Quick sort keeps breaking down the list until sorting becomes trivial.

Why Use Quick Sort?

Quick sort is preferred because it is extremely fast in practical situations. Some key advantages include:

  • Handles large datasets smoothly

  • Very efficient in average and best cases

  • Uses divide-and-conquer for faster execution

  • Requires minimal memory

  • Commonly chosen in system-level and application-level sorting

Quick sort is often faster than merge sort and heap sort in everyday programs.

Quick Sort Using Recursion

Here’s the classic Python implementation:

def quick_sort(data):
    if len(data) <= 1:
        return data

    pivot = data[-1]
    left = [x for x in data[:-1] if x <= pivot]
    right = [x for x in data[:-1] if x > pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)

This version:

  • Picks the last value as the pivot

  • Creates two lists around the pivot

  • Recursively sorts both sides

Example Usage

numbers = [9, 4, 7, 2, 1]
print(quick_sort(numbers))

Output:

[1, 2, 4, 7, 9]

Time Complexity of Quick Sort

Quick sort performance depends on how balanced the partitions are.

  • Best case: O(n log n)

  • Average case: O(n log n)

  • Worst case: O(n²)

Worst case happens when the pivot is repeatedly the smallest or largest element. However, with proper pivot choices, quick sort performs very well.

Pivot Selection Methods

Quick sort’s efficiency depends a lot on how the pivot is chosen. Common methods include:

First element as pivot

Simple, but may cause worst-case behavior for sorted lists.

Last element as pivot

Very common, easy to implement.

Middle element as pivot

Reduces the chance of poor splits.

Random pivot

Often the best way to avoid worst-case scenarios.

Random selection usually improves performance on unpredictable datasets.

When Quick Sort Works Best

Use quick sort when:

  • The dataset is large

  • Speed is important

  • Average-case performance matters

  • You want a simple and fast recursive method

  • Memory usage should stay low

Quick sort is popular in database systems, searching engines, and general-purpose sort routines.

When Quick Sort Is Not Suitable

Avoid quick sort when:

  • Data is extremely skewed

  • Worst-case performance must be avoided at all costs

  • You are working with data that needs stable sorting

  • Recursion depth could become too high

In such cases, merge sort or heap sort may be better choices.

Real-Life Uses of Quick Sort

Quick sort appears in many real-world scenarios:

Sorting records in databases

Efficiently arranges rows when speed matters.

System-level sorting routines

Quick sort is used in C, Java, Python (internal variations), and more.

Search engines

Helps in organizing index data.

E-commerce platforms

Sorts product lists, prices, and ranking data.

Competitive programming

Quick sort is preferred due to fast execution and easy coding.

Step-by-Step Example

List:

[5, 2, 9, 1, 5, 6]

Pivot = 6
Left side = [5, 2, 1, 5]
Right side = [9]

Sort left side again:
Pivot = 5
Left = [2, 1]
Right = [5]

Sort [2, 1]
Pivot = 1
Left = []
Right = [2]

Final sorted output becomes:

[1, 2, 5, 5, 6, 9]

Quick sort breaks the list into smaller parts and sorts them one by one.

Practical Examples

Example 1: Sort numbers

print(quick_sort([4, 1, 6, 3]))

Example 2: Sort words alphabetically

words = ["kiwi", "apple", "mango"]
print(quick_sort(words))

Example 3: Sort floating values

values = [3.5, 1.2, 4.8, 2.0]
print(quick_sort(values))

Example 4: Sort names

names = ["Anita", "Riya", "Tara"]
print(quick_sort(names))

Example 5: Sort scores

scores = [78, 45, 90, 32]
print(quick_sort(scores))

Example 6: Sort characters

chars = ['d', 'a', 'c', 'b']
print(quick_sort(chars))

Example 7: Sort dates

dates = ["2024-01-10", "2024-01-01", "2024-01-05"]
print(quick_sort(dates))

Example 8: Sort dictionary keys

keys = ["id3", "id1", "id2"]
print(quick_sort(keys))

Example 9: Sort user ratings

ratings = [4.2, 3.9, 5.0, 2.8]
print(quick_sort(ratings))

Example 10: Sort product codes

codes = ["A10", "A2", "A7"]
print(quick_sort(codes))

Summary of the Tutorial

Quick sort is a fast, efficient sorting algorithm that uses a pivot to divide the list into smaller parts and sorts each part individually. You learned how partitioning works, how to choose pivots, and how to implement quick sort in Python. Despite its rare worst-case behavior, quick sort remains one of the most practical and widely used algorithms for sorting large datasets.

Practice Questions

Q1. Write a Python program to sort the list [3, 7, 2, 9, 1] using quick sort.

Q2. Write a Python program to modify quick sort to use the middle element as the pivot.

Q3. Write a Python program to sort a list of strings alphabetically using quick sort.

Q4. Write a Python program to track and print the number of recursive calls made during quick sort.

Q5. Write a Python program to sort a list that contains duplicate values using quick sort.

Q6. Write a Python program to accept a list of numbers from user input and sort it using quick sort.

Q7. Write a Python program to print the array after each partition step in quick sort.

Q8. Write a Python program to implement in-place quick sort (without creating new sublists).

Q9. Write a Python program to count and display the total number of comparisons made during quick sort.

Q10. Write a Python program to compare the execution time of quick sort and merge sort on a list of 1,000 random numbers.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top