Quick Sort Algorithm and Finding the Median in Arrays

Posted on Dec 11, 2024 in Computers

Quick Sort Algorithm Explained

Key Concepts in Quick Sort:

  • Pivot Element: The pivot divides the array into two partitions.
  • The choice of pivot affects the performance:
    • A good pivot leads to balanced partitions.
    • A poor pivot can lead to highly unbalanced partitions.
  • Partitioning: The partitioning process ensures that:
    • Elements less than the pivot are on one side.
    • Elements greater than the pivot are on the other side.
  • Recursion: Quick Sort is recursively applied to the left and right partitions.

Best Case

  • At each step, the array is divided into two halves.
  • Total depth of recursion: log⁡n.
  • Work done at each level: n.
  • Total complexity: O(nlog⁡n).

Worst Case

  • Occurs when the pivot is always the smallest or largest element.
  • Recursion depth: n.
  • Work done at each level: n.
  • Total complexity: O(n2).

Average Case

  • On average, the pivot divides the array into partitions with a ratio of approximately 1:1.
  • Similar to the best case: O(nlog⁡n).

Advantages of Quick Sort

  • Efficient: Performs well for large datasets.
  • In-Place: Requires O(log⁡n) additional memory for recursion.
  • Versatile: Works well for arrays and linked lists.

What is Randomized Quick Sort?

Randomized Quick Sort is a variation of the Quick Sort algorithm where the pivot is chosen randomly instead of using a fixed position (e.g., first, last, or middle element). Randomization ensures that the algorithm’s performance is less affected by the input order and minimizes the chances of encountering the worst-case scenario.

In standard Quick Sort, if the input is already sorted or nearly sorted, choosing the pivot deterministically (e.g., always the first or last element) can lead to unbalanced partitions and worst-case time complexity O(n2). Randomized Quick Sort mitigates this by:

  • Ensuring Balanced Partitions: By randomly selecting the pivot, it is statistically more likely to divide the array into balanced partitions.
  • Making the Algorithm Input-Independent: Randomized Quick Sort is less sensitive to the initial order of the input.
  • Improving Expected Performance: The expected time complexity remains O(nlog⁡n) for any input.

Example: Sort [10, 80, 30, 90, 40, 50, 70]

  • Initial Array: [10, 80, 30, 90, 40, 50, 70].
  • Random Pivot Selection: Suppose the randomly chosen pivot is 40 (index 4).
  • Swap 40 with the last element: Array becomes [10, 80, 30, 90, 70, 50, 40].
  • Partition Around Pivot 40: After partitioning: Array becomes [10, 30, 40, 90, 70, 50, 80].
  • Recursive Calls:
    • Apply Randomized Quick Sort to left partition [10, 30].
    • Apply Randomized Quick Sort to right partition [90, 70, 50, 80].
  • Repeat Until Sorted: Final sorted array: [10, 30, 40, 50, 70, 80, 90].

Time Complexity

  • Best Case: Balanced partitions at each step. O(nlogn)
  • Average Case: Random pivot leads to reasonably balanced partitions. O(nlogn)
  • Worst Case: All partitions are highly unbalanced (very rare). O(n2)

Inversions in an Array

An inversion in an array is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. For example, in the array [2, 4, 1, 3, 5], the inversions are (2, 1) and (4, 1), making the total count 3.

Algorithm to Count Inversions Using Merge Sort

Merge Sort can count inversions efficiently by combining sorting and counting during the merge step.

Steps:

  • Divide: Recursively divide the array into two halves.
  • Count: Count inversions in the left half, right half, and across the two halves.
  • Merge: While merging, count how many elements from the right half are smaller than the current element in the left half (these contribute to inversions).

Time Complexity

  • Divide: O(log⁡n) levels of recursion.
  • Merge and Count: O(n) work per level.
  • Total: O(nlog⁡n).
  • Efficient compared to the brute-force O(n2) approach.

Finding the Median of an Unsorted Array

To find the median of an unsorted array efficiently, we can use the Median of Medians Algorithm, which is a variation of the QuickSelect Algorithm. This algorithm finds the k-th smallest element in an unsorted array in O(n) time on average.

Time Complexity

  • Average Case: O(n). Each partition reduces the problem size by approximately half.
  • Worst Case: O(n2). Occurs when the pivot is consistently the smallest or largest element.
  • Optimized Case: The Median of Medians algorithm guarantees O(n) even in the worst case.

Code Example (Python)


import random
def quick_select(arr, low, high, k):
    if low <= high:
        pivot = random.randint(low, high)
        arr[pivot], arr[high] = arr[high], arr[pivot]
        partition_index = partition(arr, low, high)
        if partition_index == k:
            return arr[partition_index]
        elif partition_index > k:
            return quick_select(arr, low, partition_index - 1, k)
        else:
            return quick_select(arr, partition_index + 1, high, k)
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 find_median(arr):
    n = len(arr)
    if n % 2 == 1:
        return quick_select(arr, 0, n - 1, n // 2)
    else:
        left = quick_select(arr, 0, n - 1, n // 2 - 1)
        right = quick_select(arr, 0, n - 1, n // 2)
        return (left + right) / 2