# 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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

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 &lt; len ; j++){
if(Array[j]&lt;pivot){
swap(&amp;Array[j],&amp;Array[i]);
i++;
}
}

swap(&amp;Array[0],&amp;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&gt;order){
// Order statistic index is in the left part
leftHalve = (int *)calloc(i-1+1,sizeof(int));
for(k=0;k&lt;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&lt;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).