CodeGym /Courses /Python SELF EN /Quick Sort

Quick Sort

Python SELF EN

Level 58 , Lesson 4

Available

9.1 Understanding Quick Sort

Quick Sort is an efficient sorting algorithm that uses the divide-and-conquer approach. It works by selecting a pivot element, partitioning the array into two sub-arrays — elements less than the pivot and elements greater than the pivot, and then recursively applying the same process to each sub-array.

Quick Sort was developed as an attempt to solve the problem of "how to quickly move smaller elements to the left and larger ones to the right". Suppose the smallest element is at the far right, can we quickly move it, if not to its final position, then close to it? This would greatly reduce unnecessary comparisons.

How it works:

1. Choosing a pivot:

Select an element from the array as the pivot. This can be the first element, the last element, the middle element, or a random one. Sometimes it's the average of three random elements.

2. Partitioning:

Move all elements less than the pivot to the left part of the array, and all elements greater than the pivot to the right part. As a result, the pivot is at its final position in the sorted array.

3. Recursive application:

Recursively apply the process to the left and right sub-arrays, excluding the pivot.

Step-by-step process

Select a pivot element.
Move elements less than the pivot to the left, and elements greater to the right.
Recursively apply the process to the sub-arrays.

Time and space complexity of Quick Sort

Time Complexity:

Worst Case: O(n^2) — happens when each time the worst pivot is chosen (e.g., when the array is already sorted).
Average Case: O(n log n) — for randomly distributed data.
Best Case: O(n log n) — when the array is split into equal parts each time.

Space Complexity:

O(log n) — required for storing the recursion call stack, if tail recursion is used and the pivots are chosen well.

9.2 Implementing Quick Sort Algorithm

Python implementation:


def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Base case: array with 0 or 1 element is already sorted
    
    pivot = arr[len(arr) // 2]  # Choose the pivot
    left = [x for x in arr if x < pivot]  # Elements less than the pivot
    middle = [x for x in arr if x == pivot]  # Elements equal to the pivot
    right = [x for x in arr if x > pivot]  # Elements greater than the pivot
    
    return quick_sort(left) + middle + quick_sort(right)

# Example usage:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
# Output: Sorted array: [1, 1, 2, 3, 6, 8, 10]

Example of the algorithm in action

Let's take an example array: [3, 6, 8, 10, 1, 2, 1]

First Pass:

Pivot: 8
Left elements: [3, 6, 1, 2, 1]
Middle elements: [8]
Right elements: [10]

Recursive sort of the left part [3, 6, 1, 2, 1]:

Pivot: 1
Left elements: []
Middle elements: [1, 1]
Right elements: [3, 6, 2]

Recursive sort of the right part [3, 6, 2]:

Pivot: 6
Left elements: [3, 2]
Middle elements: [6]
Right elements: []

Recursive sort of the left part [3, 2]:

Pivot: 2
Left elements: []
Middle elements: [2]
Right elements: [3]

Merging result: [1, 1, 2, 3, 6] for the left part, [10] for the right part, and [8] for the middle.