#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int cmpFunc (int *a, int *b){
    return *a < *b;
}

void bubbleSort (void *seq[], int len, int (*cmp)(void *, void *)){
    void *t;
    for (; len--;){
        int flag = 0;
        for (int i = 0; i < len; i++){
            if (!(*cmp)(seq[i], seq[i+1])){
                t = seq[i];
                seq[i] = seq[i+1];
                seq[i+1] = t;
                flag = 1;
            }
        }
        if (!flag){
            break;
        }
    }
}

void coctailSort (void *seq[], int len, int(*cmp)(void *, void *)){
    int left = 0;
    int right = len - 1;
    while (left <= right){
        int flag = 0;
        for (int i = left; i < right; i++){;
            if (!(*cmp)(seq[i], seq[i+1])){
                void *t = seq[i];
                seq[i] = seq[i+1];
                seq[i+1] = t;
                flag = 1;
            }
        }
        if (!flag){
            break;
        }
        right--;
        flag = 0;
        for (int i = right; i > left; i--){
            if ((*cmp)(seq[i], seq[i-1])){
                void *t = seq[i];
                seq[i] = seq[i-1];
                seq[i-1] = t;
                flag = 1;
            }
        }
        if (!flag){
            break;
        }
        left++;
    }
}

void mergeSort (void *seq[], int len, int (*cmp)(void *, void *)){
    if (len > 1){
        int len1 = len/2;
        int len2 = len - len1;
        void **seq1 = seq;
        void **seq2 = seq+len1;
        mergeSort(seq1, len1, cmp);
        mergeSort(seq2, len2, cmp);

        int i = 0;
        int j = 0;
        void* seqf[len];
        for (int k = 0; k < len; k++){
            if (i == len1){
                seqf[k] = seq2[j++];
            }
            else if (j == len2){
                seqf[k] = seq1[i++];
            }
            else if ((*cmp)(seq1[i], seq2[j])){
                seqf[k] = seq1[i++];
            }
            else{
                seqf[k] = seq2[j++];
            }
        }

        for (int n = 0; n < len; n++){
            seq[n] = seqf[n];
        }
    }
}

void radixSort (int seq[], int len, int elMaxLen, int range){
    int **tempTable = malloc(sizeof(*tempTable)*range);
    for (int i = 0; i < range; i++){
        tempTable[i] = malloc(sizeof(**tempTable)*(len+1));
        tempTable[i][0] = 0;
    }

    for (int i = 0; i < elMaxLen; i++){
        for (int n = 0; n < 8; n++){
            printf("%d%s", seq[n], n == 7 ? "\n" : " ");
        }
        for (int j = 0; j < len; j++){
            int key = seq[j]/((int)pow(10, i))%10;
            tempTable[key][++tempTable[key][0]] = seq[j];
        }
        int j = 0;
        for (int k = 0; k < range; k++){
            for (int l = 0; l < tempTable[k][0]; l++){
                seq[j++] = tempTable[k][l+1];
            }
            tempTable[k][0] = 0;
        }
    }

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

int main (int argc, char **argv){/*
    int a = 1;
    int b = 2;
    int c = 3;
    int d = 4;
    int e = 5;
    int f = 6;
    int g = 7;
    int h = 8;
    int *arr[8] = {&a, &f, &c, &e, &b, &g, &d, &h};
    mergeSort((void **)arr, 8, (int (*)(void *, void *))cmpFunc);
    for (int i = 0; i < 8; i++){
        printf("%d%s", *arr[i], i == 7 ? "\n" : " ");
    }*/
    int arr[] = {82, 12, 26, 76, 64, 34, 45, 58};
    radixSort(arr, 8, 2, 10);
    for (int i = 0; i < 8; i++){
        printf("%d%s", arr[i], i == 7 ? "\n" : " ");
    }
}