Randomized Quick Select 🎯

Welcome to our deep dive into the world of Randomized Quick Select Algorithm! This tutorial is designed for both beginners and intermediate learners who are eager to learn and master this powerful algorithm.

What is Quick Select Algorithm? 📝

Quick Select is a fast in-place algorithm for finding the kth smallest element in an unsorted list. It's an efficient alternative to sorting the entire list and then picking the kth element.

Why Quick Select? 💡

Quick Select is particularly useful when dealing with large datasets, as it has an average time complexity of O(n). This makes it a preferred choice for many real-world applications.

Introduction to Randomized Quick Select 🎯

In the original Quick Select algorithm, the pivot selection can sometimes lead to worst-case time complexity of O(n^2). To overcome this, we introduce the Randomized Quick Select algorithm, which randomly selects a pivot, ensuring a better average-case performance.

Pseudocode for Randomized Quick Select 📝

function randomized_quick_select(arr, low, high, k):
    pivot = random index in arr[low...high]
    arr[pivot], arr[high] = arr[high], arr[pivot]
    storeIndex = partition(arr, low, high)

    if storeIndex == k:
        return arr[k]
    elif storeIndex > k:
        return randomized_quick_select(arr, low, storeIndex - 1, k)
    else:
        return randomized_quick_select(arr, storeIndex + 1, high, k)

Pivot Selection 💡

In the Randomized Quick Select algorithm, we choose a random index for the pivot, ensuring that the algorithm works well even with skewed distributions.

Partitioning 📝

Partitioning rearranges the array such that all elements smaller than the pivot come before it, while all elements greater than the pivot come after it. The pivot's final position is the kth smallest element if k is less than or equal to the number of elements smaller than the pivot.

Implementation 🎯

Here are complete working examples for Python and Java:

Python

python

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

def randomized_quick_select(arr, low, high, k):
    if low < high:
        pivot = random.randint(low, high)
        arr[pivot], arr[high] = arr[high], arr[pivot]
        storeIndex = partition(arr, low, high)

        if storeIndex == k:
            return arr[k]
        elif storeIndex > k:
            return randomized_quick_select(arr, low, storeIndex - 1, k)
        else:
            return randomized_quick_select(arr, storeIndex + 1, high, k)

arr = [3, 7, 8, 5, 6, 4, 9, 1, 2]
print(randomized_quick_select(arr, 0, len(arr) - 1, 4))

Java

java

import java.util.Random;

public class RandomizedQuickSelect {
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, high);
        return i;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int randomized_quick_select(int[] arr, int low, int high, int k) {
        if (low < high) {
            int pivot = low + new Random().nextInt(high - low + 1);
            swap(arr, pivot, high);
            int storeIndex = partition(arr, low, high);

            if (storeIndex == k) {
                return arr[k];
            } else if (storeIndex > k) {
                return randomized_quick_select(arr, low, storeIndex - 1, k);
            } else {
                return randomized_quick_select(arr, storeIndex + 1, high, k);
            }
        }
        return arr[k];
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 8, 5, 6, 4, 9, 1, 2};
        System.out.println(randomized_quick_select(arr, 0, arr.length - 1, 4));
    }
}

Quiz 📝

That's it for our introductory lesson on Randomized Quick Select! As you practice and deepen your understanding of this algorithm, you'll find it incredibly useful in solving various real-world problems. Keep coding! 🚀