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);
}
}

C# events vs. delegates

Event invocation
Furthermore, an event can only be invoked from within the class that declared it, whereas a delegate field can be invoked by whoever has access to it. For example:

[sourcecode language="csharp"]
using System;
namespace EventAndDelegate
{
 delegate void MsgHandler(string s);

 class Class1
 {
 public static event MsgHandler msgNotifier;
 public static MsgHandler msgNotifier2;

 static void Main(string[] args)
 {
 new Class2().test();
 }
 }

 class Class2
 {
 public void test()
 {
 Class1.msgNotifier("test"); // error CS0070: The event 'EventAndDelegate.Class1.msgNotifier' can only appear on the left hand side of += or -= (except when used from within the type 'EventAndDelegate.Class1')
 Class1.msgNotifier2("test2"); // compiles fine
 }
 }
}
[/sourcecode]

This restriction on invocations is quite strong. Even derived classes from the class declaring the event aren’t allowed to fire the event. A way to deal with this is to have a protected virtual method to trigger the event.

 

Conclusion
We have seen that the event keyword is a modifier for a delegate declaration that allows it to be included in an interface, constraints it invocation from within the class that declares it, provides it with a pair of customizable accessors (addand remove) and forces the signature of the delegate (when used within the .NET framework).