• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Quick Sort

← Previous Next →

Quick Sort is a highly efficient divide-and-conquer sorting algorithm.
It works by selecting a pivot element and partitioning the array around it — smaller values to the left, larger to the right.

🔹 How Quick Sort Works

  1. Pick a pivot element

  2. Partition the array:

    • Elements less than pivot → left side

    • Elements greater than pivot → right side

  3. Recursively apply the above steps on left and right subarrays

🔹 Quick Sort in Python

def quick_sort(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(left) + [pivot] + quick_sort(right)
Example
numbers = [10, 7, 8, 9, 1, 5]

sorted_list = quick_sort(numbers)
print("Sorted array:", sorted_list)

✅ Output:

Sorted array: [1, 5, 7, 8, 9, 10]

🔹 In-Place Quick Sort 

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)

🔹 Time Complexity

Case Time
Best Case O(n log n)
Average O(n log n)
Worst Case O(n²)
Space O(log n)

Worst-case occurs when the smallest or largest element is always chosen as pivot.

🔹 Use Cases of Quick Sort

  • Large datasets

  • When average performance is more important than worst-case

  • Faster than Merge/Insertion in most real-world scenarios

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 →

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