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

# Fees in RWTH Aachen University

Monthly Expenditure Minimum Costs per Month
Accommodation € 160
Food and general expenses € 350
Health insurance approx. € 80
University fees (social security contribution, semester ticket), approx. €200 per semester approx. € 38
Book and materials € 70 (may be significantly higher, according to subject studied)
Total approx. € 700 per month (€ 8,400 per year)