/******************************************************************************
* FILE: rowColumnSort.c
* AUTHOR: Cristian Chilipirea
* Skeleton for shear sort
******************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define N 25
#define SQRTN 5 // has to be sqrt(N)

void displayMatrix(int m[][SQRTN]) {
    // DO NOT MODIFY
    int i,j;
    for(i = 0; i < SQRTN; i++) {
        for(j = 0; j < SQRTN; j++) {
            printf("%i ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void copyMatrixInVectorSnake(int *v, int m[][SQRTN]) {
    // DO NOT MODIFY
    int i, j;
    for(i=0;i<SQRTN;i++) {
        if(i%2 == 0) {
            for(j=0;j<SQRTN;j++) {
                v[i*SQRTN+j] = m[i][j];
            }
        } else {
            for(j=SQRTN;j>0;j--) {
                v[i*SQRTN+(SQRTN-j)] = m[i][j-1];
            }
        }
    }
}

void compareVectors(int * a, int * b) {
    // DO NOT MODIFY
    int i;
    for(i = 0; i < N; i++) {
        if(a[i]!=b[i]) {
            printf("Sorted incorrectly\n");
            return;
        }
    }
    printf("Sorted correctly\n");
}

void displayVector(int * v) {
    // DO NOT MODIFY
    int i;
    for(i = 0; i < N; i++) {
        printf("%i ", v[i]);
    }
    printf("\n");
}

int cmp(const void *a, const void *b) {
    // DO NOT MODIFY
    int A = *(int*)a;
    int B = *(int*)b;
    return A-B;
}

int cmp_neg(const void *a, const void *b) {
    // DO NOT MODIFY
    int A = *(int*)a;
    int B = *(int*)b;
    return B-A;
}

int main(int argc, char *argv[]) {
    srand(42);
    int m[SQRTN][SQRTN];
    int v[N];
    int vQSort[N];
    int i,j;
    int aux[SQRTN];
    // generate the vector v with random values
    // DO NOT MODIFY
    for(i = 0; i < SQRTN; i++)
        for(j = 0; j < SQRTN; j++)
            m[i][j] = rand()%10;

    // make copy to check it against qsort
    // DO NOT MODIFY
    copyMatrixInVectorSnake(vQSort, m);
    qsort(vQSort, N, sizeof(int), cmp);
    int steps;
    for (steps = 1; steps <= N; steps = steps * 2) {

        for (i = 0; i < SQRTN; i = i + 2) {

            qsort(m[i], SQRTN, sizeof(int), cmp);

        }
        for (i = 1; i < SQRTN; i = i + 2) {

            qsort(m[i], SQRTN, sizeof(int), cmp_neg);

        }
        for (i = 0; i < SQRTN; i++) {

            for (j = 0; j < SQRTN; j++)
                aux[j] = m[j][i];
            qsort(aux, SQRTN, sizeof(int), cmp);
            for (j = 0; j < SQRTN; j++)
                m[j][i] = aux[j];
        }
    }
    // sort the matrix m using ShearSort


    displayMatrix(m);
    copyMatrixInVectorSnake(v, m);
    displayVector(v);
    displayVector(vQSort);
    compareVectors(v,vQSort);

    return 0;
}