magnum est imperium romanum

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define SIZE 10

int main()
{
    printf("Hello world!\n");

    time_t t;
    //srand((unsigned) time(&t));
    srand(0);

    while(1){
        int arr[SIZE];
        napln_pole(arr,SIZE);
        /*arr[0] = 8;
        arr[1] = 7;
        arr[2] = 1;
        arr[3] = 2;
        arr[4] = 9;*/
        int copy[SIZE];
        copyArray(arr,copy,SIZE);


        printf("Orig\n");
        printArr(arr,SIZE);

        /*printf("Bubble\n");
        bubbleSort(arr,SIZE);
        printArr(arr,SIZE);

        printf("Shaker\n");
        printArr(copy,SIZE);
        shakerSort(copy,SIZE);
        printArr(copy,SIZE);
        printf("-------------------------\n");
*/
        printf("RadixSort\n");
        //heapSort(arr,SIZE);
        //int out[SIZE];
        //countingSort(arr,out,SIZE,100);
        //printArr(out,SIZE);
        /*int n = 8192;
        int d = getDigit(n,4);
        printf("%d %d \n",n, d);*/

        radixSort(copy,SIZE,4);
        printArr(copy,SIZE);


        /*printf("-------------------------\n");


        printf("Fib for %d = %d \n", arr[0], fib(arr[0]));*/

        char c;
        scanf("%c",&c);

    }
    return 0;
}

void napln_pole(int pole[], int velikost){
    for (int i = 0; i < velikost; i++){
      pole[i] = rand() % 1001;  //% 100 zajistuje rozsah 0-99. pro rozsah 0-1000 pouzijte % 1001
    }
}



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


void selectionSort(int arr[], int length){
    int i;
    for(i = 0; i < length; i++){

        int min = i;

        int j;
        for(j = i+1; j < length; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }

        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

void bubbleSort(int arr[], int length){
    int s = 0;

    int i;
    int lastSwapL = 0;

    for(i = 0; i < length-2; i++){
        int endL = lastSwapL;
        int j;
        for(j = length-1; j > endL; j--){
            int a = arr[j];
            int b = arr[j-1];
            if(a < b){
                arr[j] = b;
                arr[j-1] = a;
                lastSwapL = j;
                s++;
            }
        }
        printf("i %d\n",i);
    }
    printf("%d\n",s);

}

void shakerSort(int arr[], int length){
    int s = 0;

    int i;
    int lastSwapL = 0;
    int lastSwapR = length-2;

    for(i = 0; i < length-2; i++){
        int dirty = 0;
        int endL = lastSwapL;
        int j;
        for(j = length-1; j > endL; j--){
            int a = arr[j];
            int b = arr[j-1];

            if(a < b){
                arr[j] = b;
                arr[j-1] = a;
                lastSwapL = j;
                s++;
                dirty = 1;
            }
        }

        if(dirty == 0) break;
        dirty = 0;

        int endR = lastSwapR;
        for(j = i; j < endR; j++){
            int a = arr[j];
            int b = arr[j+1];

            if(a > b){
                arr[j] = b;
                arr[j+1] = a;
                lastSwapR = j;
                s++;
                dirty = 1;
            }
        }
        printf("i %d\n",i);
        if(dirty == 0) break;
    }
    printf("%d\n",s);

}

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 i = start-1;
    int j;
    for(j = start; j < end; j++){
        if(arr[j] <= pivot){
            swap(arr,++i,j);
        }
    }
    swap(arr,++i,end);
    return i;
}

void mergeSort(int arr[], int start, int end){
    if(start < end){
        int mid = start+(end-start)/2; //We can not just do (start+end)/2 as we would risk overflow
        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 lengthL = mid-start+1;
    int lengthR = end-mid;

    int left[lengthL];
    int right[lengthR];

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

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

    left[lengthL] = INT_MAX; //Requires limits.h
    right[lengthR] = INT_MAX;

    int iL = 0;
    int iR = 0;

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


void swap(int arr[], int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

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

void copyArray(int src[], int dst[], int length){
    for(int i = 0; i < length; i++){
            dst[i] = src[i];
    }
}

int fib(int n){
    if(n < 0) return -1;
    if(n == 0 || n== 1) return 1;
    return fib(n-1)+fib(n-2);
}

int getParent(int i){
    return (i-1)/2;
}

int getLeft(int i){
    return 2*i+1;
}

int getRight(int i){
    return 2*i+2;
}

void heapify(int arr[], int size, int i){
    int left = getLeft(i);
    int right = getRight(i);
    int largest = i;

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

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

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

}

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

void heapSort(int arr[], int size){
    buildMaxHeap(arr,size);

    for(int i = size-1; i > 0; i--){
        swap(arr,0,i);
        heapify(arr,i,0);
    }
}


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

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

    for(int i = 0; i < size; 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 = size-1; i >= 0; i--){
        //printf("%d \n",sizeof(counts)/sizeof(int));
        out[counts[in[i]] - 1] = in[i];
        counts[in[i]] = counts[in[i]] - 1;
    }
}

void radixSort(int arr[], int size, int d){
    for(int i = 0; i < d; i++){
        insertSortRadix(arr,size,i);
    }
}

int getDigit(int n, int digit){
    return n%power(10,digit)/(power(10,digit-1));
}

int power(int base, int n){
    int out = 1;
    for(int i = 0; i < n; i++){
        out*=base;
    }
    return out;
}

void insertSortRadix(int arr[], int length, int d){
    int i;
    for(i = 1; i < length; i++){
        int temp = arr[i];

        //printf("%d %d \n",d,i);
        int j = i -1;
        while(j >= 0 && getDigit(temp,d+1) < getDigit(arr[j],d+1)){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}