gg

#include <stdio.h>
#include <stdlib.h>
#define COUNT 10

int main()
{
    printf("Hello world!\n");
    srand(0);
    while(1)
    {

        int array[COUNT];
        populateArray(array,COUNT,0,100);
        printArray(array,COUNT);
        //mergeSort(array,0,COUNT-1);
        //heapSort(array,COUNT);
        //int out[COUNT];
        //countingSort(array,out,COUNT,101);

        printf("%d\n",nthOrderStatistics(array,0,COUNT-1,1));
        //printArray(out,COUNT);
        //printArray(array,COUNT);

        char c;
        scanf("%c",&c);
    }
    return 0;
}

void populateArray(int arr[], int length, int min, int max)
{
    for (int i = 0; i < length ; i++)
    {
        arr[i] = rand() % (max + 1 - min) + min;
    }
}

void printArray(int arr[], int length)
{
    printf("[");
    for (int i = 0; i < length ; i++)
    {
        printf("%d",arr[i]);
        if(i < length-1)
        {
            printf(", ");
        }
    }
    printf("]\n");
}

void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void insertSort(int arr[], int length){
    for(int i = 1; i < length; i++){
        int temp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > temp){
            arr[j+1] = arr[j];
            j--;
        }
        arr[++j] = temp;
    }
}

void selectSort(int arr[], int length){
    for(int i = 0; i < length; i++){
        int min = i;
        for(int j = i + 1; j < length; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        swap(arr,min,i);
    }
}

void bubbleSort(int arr[], int length){
    for(int i = 0; i < length -1 ; i++){
        int last = i;
        for(int j = length-1; j > 0; j--){
            if(arr[j] < arr[j-1]){
                swap(arr,j,j-1);
                last = j-1;
            }
        }
        i = last;
    }
}

void quickSort(int arr[], int start, int end){
    if(start < end){
        int part = partition(arr,start,end);
        quickSort(arr,start,part-1);
        quickSort(arr,part+1,end);
    }
}

int partition(int arr[], int start, int end){
    int pivot = arr[end];
    int pos = start - 1;

    for(int i = start; i < end; i++){
        if(arr[i] < pivot){
            swap(arr,++pos,i);
        }
    }
    swap(arr,++pos,end);

    return pos;
}

void mergeSort(int arr[], int start, int end){
    if(start < end){
        int mid = start + (end - start) / 2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
}

void merge(int arr[], int start, int mid, int end){
    int lengthLeft = mid-start+1;
    int lengthRight = end - mid;

    int left[lengthLeft];
    int right[lengthRight];

    for(int i = 0; i < lengthLeft; i++){
        left[i] = arr[start+i];
    }

    for(int i = 0; i < lengthRight; i++){
        right[i] = arr[i+mid+1];
    }

    left[lengthLeft] = 2147483647;
    right[lengthRight] = 2147483647;

    int posLeft = 0;
    int posRight = 0;

    for(int i = start; i <= end; i++){
        if(left[posLeft] <= right[posRight]){
            arr[i] = left[posLeft++];
        }
        else {
            arr[i] = right[posRight++];
        }
    }
}

void heapSort(int arr[], int length){
    buildMaxHeap(arr,length);
    for(int i = length -1 ; i > 0; i--){
        swap(arr,0,i);
        heapify(arr,0,i);
    }
}

void heapify(int arr[], int i, int length){
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if(left < length && arr[left] > arr[largest]){
        largest = left;
    }

    if(right < length && arr[right] > arr[largest]){
        largest = right;
    }

    if(largest != i){
        swap(arr,largest,i);
        heapify(arr,largest,length);
    }
}

void buildMaxHeap(int arr[], int length){
    for(int i = length / 2; i >= 0; i--){
        heapify(arr,i,length);
    }
}

void countingSort(int in[], int out[], int length, int range){
    int counts[range];

    for(int i = 0; i < range; i++){
        counts[i] = 0;
    }

    for(int i = 0; i < length; i++){
        counts[in[i]] = counts[in[i]] + 1;
    }

    for(int i = 1; i < range; i++){
        counts[i] = counts[i] + counts[i-1];
    }


    for(int i = 0; i < length; i++){
        out[counts[in[i]]-1] = in[i];
        counts[in[i]] = counts[in[i]] - 1;
    }
}

int nthOrderStatistics(int arr[], int start, int end, int n){
    if(start == end){
        return arr[start];
    }

    int pivot = randomizedPartition(arr,start,end);
    int pivotLocal = pivot - start + 1;

    if(pivotLocal == n){
        return arr[pivot];
    }

    if(n < pivotLocal){
        return nthOrderStatistics(arr,start,pivot-1,n);
    }

    return nthOrderStatistics(arr,pivot+1,end,n-pivotLocal);
}


int randomizedPartition(int arr[], int start, int end){

    int k = rand() % (end + 1 - start) + start;
    swap(arr,k,end);
    return partition(arr,start,end);
}