Randomized Quicksort, Randomized Select, Skip Lists
Randomized quicksort uses a random pivot selection to achieve expected O(n log n) time complexity, avoiding worst-case O(n²) performance on sorted inputs.
Watch how random pivot selection affects sorting:
#include
#include
#include
#include
class RandomizedQuickSort {
private:
static std::mt19937 rng;
public:
static void sort(std::vector& arr) {
quicksort(arr, 0, arr.size() - 1);
}
private:
static void quicksort(std::vector& arr, int low, int high) {
if (low < high) {
int pivotIndex = randomizedPartition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
static int randomizedPartition(std::vector& arr, int low, int high) {
// Generate random index between low and high
std::uniform_int_distribution dist(low, high);
int randomIndex = dist(rng);
// Swap random element with last element
std::swap(arr[randomIndex], arr[high]);
// Perform standard partition with last element as pivot
return partition(arr, low, high);
}
static int partition(std::vector& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
public:
// Three-way partition for handling duplicates efficiently
static void dutchFlagSort(std::vector& arr, int low, int high) {
if (low >= high) return;
auto [lt, gt] = threeWayPartition(arr, low, high);
dutchFlagSort(arr, low, lt - 1);
dutchFlagSort(arr, gt + 1, high);
}
private:
static std::pair threeWayPartition(std::vector& arr, int low, int high) {
std::uniform_int_distribution dist(low, high);
int randomIndex = dist(rng);
std::swap(arr[randomIndex], arr[low]);
int pivot = arr[low];
int lt = low; // arr[low..lt-1] < pivot
int i = low + 1; // arr[lt..i-1] == pivot
int gt = high + 1; // arr[gt..high] > pivot
while (i < gt) {
if (arr[i] < pivot) {
std::swap(arr[lt++], arr[i++]);
} else if (arr[i] > pivot) {
std::swap(arr[i], arr[--gt]);
} else {
i++;
}
}
return {lt, gt};
}
public:
// Performance analysis
static void benchmark(std::vector arr, const std::string& description) {
auto start = std::chrono::high_resolution_clock::now();
sort(arr);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast(end - start);
std::cout << description << ": " << duration.count() << " microseconds" << std::endl;
}
};
// Initialize random number generator
std::mt19937 RandomizedQuickSort::rng(std::chrono::steady_clock::now().time_since_epoch().count()); Randomized selection finds the k-th smallest element in expected O(n) time using random pivot selection.
Find the k-th smallest element using randomized selection:
#include
#include
#include
#include
class RandomizedSelect {
private:
static std::mt19937 rng;
public:
// Find k-th smallest element (1-indexed)
static int select(std::vector& arr, int k) {
if (k < 1 || k > arr.size()) {
throw std::invalid_argument("k out of range");
}
return quickSelect(arr, 0, arr.size() - 1, k - 1); // Convert to 0-indexed
}
private:
static int quickSelect(std::vector& arr, int low, int high, int k) {
if (low == high) {
return arr[low];
}
int pivotIndex = randomizedPartition(arr, low, high);
if (k == pivotIndex) {
return arr[k];
} else if (k < pivotIndex) {
return quickSelect(arr, low, pivotIndex - 1, k);
} else {
return quickSelect(arr, pivotIndex + 1, high, k);
}
}
static int randomizedPartition(std::vector& arr, int low, int high) {
std::uniform_int_distribution dist(low, high);
int randomIndex = dist(rng);
std::swap(arr[randomIndex], arr[high]);
return partition(arr, low, high);
}
static int partition(std::vector& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
public:
// Find k smallest elements
static std::vector selectMultiple(std::vector arr, int k) {
if (k <= 0 || k > arr.size()) {
return {};
}
// Use quickselect to partition around k-th element
int kthElement = select(arr, k);
// Collect all elements <= k-th element
std::vector result;
int count = 0;
for (int x : arr) {
if (x < kthElement || (x == kthElement && count < k)) {
result.push_back(x);
if (x == kthElement) count++;
}
}
return result;
}
// Find median using randomized select
static double findMedian(std::vector arr) {
int n = arr.size();
if (n % 2 == 1) {
return select(arr, (n + 1) / 2);
} else {
int lower = select(arr, n / 2);
int upper = select(arr, n / 2 + 1);
return (lower + upper) / 2.0;
}
}
// Iterative version to avoid stack overflow
static int selectIterative(std::vector& arr, int k) {
if (k < 1 || k > arr.size()) {
throw std::invalid_argument("k out of range");
}
int low = 0, high = arr.size() - 1;
k--; // Convert to 0-indexed
while (low < high) {
int pivotIndex = randomizedPartition(arr, low, high);
if (k == pivotIndex) {
return arr[k];
} else if (k < pivotIndex) {
high = pivotIndex - 1;
} else {
low = pivotIndex + 1;
}
}
return arr[low];
}
};
std::mt19937 RandomizedSelect::rng(std::chrono::steady_clock::now().time_since_epoch().count()); Skip lists are probabilistic data structures that provide O(log n) expected time for search, insertion, and deletion operations.
Build and search a skip list structure:
#include
#include
#include
#include
class SkipListNode {
public:
int value;
std::vector forward;
SkipListNode(int val, int level) : value(val), forward(level + 1, nullptr) {}
};
class SkipList {
private:
static const int MAX_LEVEL = 16;
static const double P = 0.5; // Probability for coin flip
SkipListNode* header;
int level;
std::mt19937 rng;
std::uniform_real_distribution dist;
public:
SkipList() : level(0), rng(std::random_device{}()), dist(0.0, 1.0) {
header = new SkipListNode(INT_MIN, MAX_LEVEL);
}
~SkipList() {
SkipListNode* current = header;
while (current) {
SkipListNode* next = current->forward[0];
delete current;
current = next;
}
}
private:
int randomLevel() {
int lvl = 0;
while (dist(rng) < P && lvl < MAX_LEVEL) {
lvl++;
}
return lvl;
}
public:
void insert(int value) {
std::vector update(MAX_LEVEL + 1);
SkipListNode* current = header;
// Search for insertion point
for (int i = level; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0];
// If value doesn't exist, insert it
if (!current || current->value != value) {
int newLevel = randomLevel();
// If new level is greater than current level
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = header;
}
level = newLevel;
}
// Create new node
SkipListNode* newNode = new SkipListNode(value, newLevel);
// Update forward pointers
for (int i = 0; i <= newLevel; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
}
bool search(int value) {
SkipListNode* current = header;
// Start from highest level
for (int i = level; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
}
current = current->forward[0];
return current && current->value == value;
}
bool remove(int value) {
std::vector update(MAX_LEVEL + 1);
SkipListNode* current = header;
// Search for node to delete
for (int i = level; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0];
// If found, delete it
if (current && current->value == value) {
// Update forward pointers
for (int i = 0; i <= level; i++) {
if (update[i]->forward[i] != current) {
break;
}
update[i]->forward[i] = current->forward[i];
}
delete current;
// Update level
while (level > 0 && !header->forward[level]) {
level--;
}
return true;
}
return false;
}
void display() {
std::cout << "Skip List:" << std::endl;
for (int i = level; i >= 0; i--) {
std::cout << "Level " << i << ": ";
SkipListNode* current = header->forward[i];
while (current) {
std::cout << current->value << " ";
current = current->forward[i];
}
std::cout << std::endl;
}
}
// Get all values in sorted order
std::vector getValues() {
std::vector values;
SkipListNode* current = header->forward[0];
while (current) {
values.push_back(current->value);
current = current->forward[0];
}
return values;
}
// Range query: find all values in [low, high]
std::vector rangeQuery(int low, int high) {
std::vector result;
SkipListNode* current = header;
// Find starting position
for (int i = level; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < low) {
current = current->forward[i];
}
}
current = current->forward[0];
// Collect values in range
while (current && current->value <= high) {
result.push_back(current->value);
current = current->forward[0];
}
return result;
}
}; Visualize probability distributions:
#include
#include
#include
#include
class AdvancedRandomization {
public:
// Reservoir sampling: randomly sample k items from stream
static std::vector reservoirSample(const std::vector& stream, int k) {
if (k <= 0 || stream.empty()) return {};
std::vector reservoir;
std::mt19937 rng(std::random_device{}());
// Fill reservoir with first k elements
for (int i = 0; i < std::min(k, (int)stream.size()); i++) {
reservoir.push_back(stream[i]);
}
// Process remaining elements
for (int i = k; i < stream.size(); i++) {
std::uniform_int_distribution dist(0, i);
int j = dist(rng);
if (j < k) {
reservoir[j] = stream[i];
}
}
return reservoir;
}
// Fisher-Yates shuffle
static void fisherYatesShuffle(std::vector& arr) {
std::mt19937 rng(std::random_device{}());
for (int i = arr.size() - 1; i > 0; i--) {
std::uniform_int_distribution dist(0, i);
int j = dist(rng);
std::swap(arr[i], arr[j]);
}
}
// Generate random permutation
static std::vector randomPermutation(int n) {
std::vector perm(n);
std::iota(perm.begin(), perm.end(), 0);
fisherYatesShuffle(perm);
return perm;
}
// Monte Carlo algorithm: estimate π
static double estimatePi(int numSamples) {
std::mt19937 rng(std::random_device{}());
std::uniform_real_distribution dist(-1.0, 1.0);
int insideCircle = 0;
for (int i = 0; i < numSamples; i++) {
double x = dist(rng);
double y = dist(rng);
if (x * x + y * y <= 1.0) {
insideCircle++;
}
}
return 4.0 * insideCircle / numSamples;
}
// Las Vegas algorithm: randomized primality test
static bool millerRabinPrimality(long long n, int k = 5) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
// Write n-1 as d * 2^r
long long d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
r++;
}
std::mt19937 rng(std::random_device{}());
for (int i = 0; i < k; i++) {
std::uniform_int_distribution dist(2, n - 2);
long long a = dist(rng);
long long x = modPow(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int j = 0; j < r - 1; j++) {
x = (x * x) % n;
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
private:
static long long modPow(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
}; | Algorithm | Worst Case | Expected Case | Advantage |
|---|---|---|---|
| Deterministic Quicksort | O(n²) | O(n log n) | Simple, cache-friendly |
| Randomized Quicksort | O(n²) | O(n log n) | No adversarial input |
| Median-of-medians Select | O(n) | O(n) | Guaranteed linear |
| Randomized Select | O(n²) | O(n) | Simple, fast in practice |
| Balanced BST | O(log n) | O(log n) | Guaranteed performance |
| Skip List | O(n) | O(log n) | Simple implementation |
#include
int main() {
std::cout << "=== Unit 6: Randomization Demo ===" << std::endl;
// Randomized Quicksort Demo
std::cout << "\n--- Randomized Quicksort ---" << std::endl;
std::vector arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
std::cout << "Original array: ";
for (int x : arr) std::cout << x << " ";
std::cout << std::endl;
RandomizedQuickSort::sort(arr);
std::cout << "Sorted array: ";
for (int x : arr) std::cout << x << " ";
std::cout << std::endl;
// Randomized Selection Demo
std::cout << "\n--- Randomized Selection ---" << std::endl;
std::vector selectArr = {3, 6, 8, 10, 1, 2, 1};
std::cout << "Array: ";
for (int x : selectArr) std::cout << x << " ";
std::cout << std::endl;
int k = 3;
int kthSmallest = RandomizedSelect::select(selectArr, k);
std::cout << k << "-th smallest element: " << kthSmallest << std::endl;
double median = RandomizedSelect::findMedian(selectArr);
std::cout << "Median: " << median << std::endl;
// Skip List Demo
std::cout << "\n--- Skip List ---" << std::endl;
SkipList skipList;
std::vector values = {3, 6, 7, 9, 12, 19, 17, 26, 21, 25};
for (int val : values) {
skipList.insert(val);
std::cout << "Inserted " << val << std::endl;
}
skipList.display();
std::cout << "Search 17: " << (skipList.search(17) ? "Found" : "Not found") << std::endl;
std::cout << "Search 20: " << (skipList.search(20) ? "Found" : "Not found") << std::endl;
std::vector range = skipList.rangeQuery(10, 20);
std::cout << "Range query [10, 20]: ";
for (int x : range) std::cout << x << " ";
std::cout << std::endl;
// Advanced Randomization Demo
std::cout << "\n--- Advanced Randomization ---" << std::endl;
// Estimate π
double piEstimate = AdvancedRandomization::estimatePi(100000);
std::cout << "Estimated π: " << piEstimate << std::endl;
// Reservoir sampling
std::vector stream = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector sample = AdvancedRandomization::reservoirSample(stream, 3);
std::cout << "Reservoir sample (k=3): ";
for (int x : sample) std::cout << x << " ";
std::cout << std::endl;
return 0;
}