• Hajipur, Bihar, 844101

☰
❮
❯

Python

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

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.

Python Quick Sort Quiz

Q1: What is the key concept of quick sort?

A. Bubble logic
B. Divide and conquer
C. Two-pointer method
D. Recursion only

Q2: What is a pivot in quick sort?

A. Middle element always
B. Element used for partitioning
C. Sorted value
D. Leftmost value only

Q3: Time complexity in best/average case?

A. O(n²)
B. O(n log n)
C. O(log n)
D. O(n)

Q4: Quick sort worst-case time?

A. O(n log n)
B. O(n)
C. O(n²)
D. O(1)

Q5: What happens during partition?

A. List is reversed
B. List is sorted
C. List is divided around pivot
D. List is merged

Q6: Is Quick Sort recursive?

A. No
B. Yes
C. Only with helper function
D. Only for small lists

Q7: Can Quick Sort be used to sort strings?

A. No
B. Yes
C. Only lowercase strings
D. Only numeric strings

Q8: What is the base condition in Quick Sort?

A. When list has only one element
B. When pivot is maximum
C. When list is reversed
D. When all elements are equal

Q9: Which version of Quick Sort is more memory efficient?

A. List-based
B. In-place
C. Recursive with extra list
D. Iterative quick sort

Q10: What kind of sorting algorithm is Quick Sort?

A. Stable
B. Unstable
C. Partially stable
D. Always stable in Python
← Previous Next →
Login
Go Back Top