Randomized Selection

 

Concept:

  • Implement QuickSort to partition array into two parts
  • Choose “Randomized pivot" (This article use left as pivot for convenience)
  • Partition the array
  • Divide the elements in the left part which are smaller than the pivot
  • Divide the elements in the right part which are larger than the pivot
  • If the order statistic is larger than the index(i-1), than desired order statistic must lays in the right part
  • If the order statistic is smaller than the index(i-1), than desired order statistic must lays in the left part

Time Complexity

O(n)

Conclution

Randomized Selection provides a simple and a fast way to find the ith order statictic.
Otherwise, “Deterministic selection" is another solution.

Find i th statistic order element X_{i}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int *a,int *b){
int temp;
temp = *a ;
*a = *b;
*b = temp;
}
int RSelect(int Array[],int len,int order){
int i = 0,j = 0,k;
int pivot;
int* leftHalve;
int* rightHalve;

if(len==1) return Array[0];

// Partition
pivot = Array[0]; // Always Select left most element as pivot
i = 1 ;
for(j = 1 ; j < len ; j++){
if(Array[j]<pivot){
swap(&Array[j],&Array[i]);
i++;
}
}

swap(&Array[0],&Array[i-1]); // Swap the pivot with division index i-1

if(i-1==order) return Array[i-1]; // After swap, the order statistic is exactly i-1

// Divide
if(i-1>order){
// Order statistic index is in the left part
leftHalve = (int *)calloc(i-1+1,sizeof(int));
for(k=0;k<i-1+1;k++){
leftHalve[k] = Array[k];
}
RSelect(leftHalve,i-1+1,order);
}else{
// Order statistic index is in the right part
rightHalve = (int *)calloc(len-i,sizeof(int));
for(k=0;k<len-i;k++){
rightHalve[k] = Array[i+k];
}
RSelect(rightHalve,len-i,order-i);
}
}
廣告