TP2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAX_LENGTH_OPTIONS 3
#define MAX_OPTIONS 8
//Define the options of functions sorting
char optionSorting[MAX_OPTIONS][MAX_LENGTH_OPTIONS + 1] = {
    "Bub",
    "Sel",
    "Ins",
    "She",
    "Qui",
    "Hea",
    "Mer",
    "Rad"
};

void bubble_sort(int *vetor, int length) {

  int aux, y, x;

  for( x = 0; x < length; x++ )
  {
    for( y = x + 1; y < length; y++ )
    {
      if ( vetor[x] > vetor[y] )
      {
         aux = vetor[x];
         vetor[x] = vetor[y];
         vetor[y] = aux;
      }
    }
  }

}

void selection_sort(int *vetor,int length) {
  int i, j, min, aux;

  for (i = 0; i < (length - 1); i++) {
    min = i;
    for (j = i+1; j < length; j++) {
      if (vetor[j] < vetor[min]) {
   min = j;
      }
    }
    if (i != min) {
      aux = vetor[i];
      vetor[i] = vetor[min];
      vetor[min] = aux;
    }
  }
}

void insertion_sort(int *vetor, int length) {
   int i, j, nowvalueue;

   for( j=1; j < length; j++ )
   {
      nowvalueue = vetor[j];
      i = j-1;

      while(i >= 0 && vetor[i] > nowvalueue)
      {
        vetor[i+1] = vetor[i];
        i--;
      }
      vetor[i+1] = nowvalueue;
   }
}

void shell_sort(int *vetor, int length) {
   int i , j , valueue;
    int blank = 1;

    do {
        blank = 3*blank+1;
    } while(blank < length);

    do {
        blank /= 3;
        for(i = blank; i < length; i++) {
            valueue = vetor[i];
            j = i - blank;

            while (j >= 0 && valueue < vetor[j]) {
                vetor[j + blank] = vetor[j];
                j -= blank;
            }
            vetor[j + blank] = valueue;
        }
    } while(blank > 1);
}

void quick_sort(int *vetor, int start, int end) {

   int pivo, aux, i, j, medium;

   i = start;
   j = end;

   medium = (int) ((i + j) / 2);
   pivo = vetor[medium];

   do{
      while (vetor[i] < pivo) i = i + 1;
      while (vetor[j] > pivo) j = j - 1;

      if(i <= j){
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i = i + 1;
         j = j - 1;
      }
   } while(j > i);

   if(start < j) quick_sort(vetor, start, j);
   if(i < end) quick_sort(vetor, i, end);

}

void heap_start(int *vetor, int length)
{
    int i, value, aux, alt ;
    for ( i = 1 ; i < length ; i++ )
    {
        value = vetor[i] ;
        aux = i ;
        alt = ( aux - 1 ) / 2 ;
        while ( aux > 0 && vetor[alt] < value )
        {
            vetor[aux] = vetor[alt] ;
            aux = alt ;
            alt = ( aux - 1 ) / 2 ;
        }
        vetor[aux] = value ;
    }
}

void heap_sort(int *vetor, int length)
{
    int i, aux, alt, endvalue ;
    for ( i = length - 1 ; i > 0 ; i-- )
    {
        endvalue = vetor[i] ;
        vetor[i] = vetor[0] ;
        alt = 0 ;

        if ( i == 1 )
            aux = -1 ;
        else
            aux = 1 ;

        if ( i > 2 && vetor[2] > vetor[1] )
            aux = 2 ;

        while ( aux >= 0 && endvalue < vetor[aux] )
        {
            vetor[alt] = vetor[aux] ;
            alt = aux ;
            aux = 2 * alt + 1 ;

            if ( aux + 1 <= i - 1 && vetor[aux] < vetor[aux + 1] )
                aux++ ;
            if ( aux > i - 1 )
                aux = -1 ;
        }
        vetor[alt] = endvalue ;
    }
}

void merging(int *vetor, int *vetAux, int min, int middle, int high) {
   int varOne, varTwo, i;

   for(varOne = min, varTwo = middle + 1, i = min; varOne <= middle && varTwo <= high; i++) {
      if(vetor[varOne] <= vetor[varTwo])
         vetAux[i] = vetor[varOne++];
      else
         vetAux[i] = vetor[varTwo++];
   }

   while(varOne <= middle)
      vetAux[i++] = vetor[varOne++];

   while(varTwo <= high)
      vetAux[i++] = vetor[varTwo++];

   for(i = min; i <= high; i++)
      vetor[i] = vetAux[i];
}

void merge_sort(int *vetor, int *vetAux, int min, int high) {
   int middle;

   if(min < high) {
      middle = (min + high) / 2;
      merge_sort(vetor, vetAux, min, middle);
      merge_sort(vetor, vetAux, middle+1, high);
      merging(vetor, vetAux, min, middle, high);
   } else return ;
}

int searchBiggest(int * vetor, int length){

  int i;
  int bigNb = -1;

  for(i = 0; i < length; i++){
    if(vetor[i] > bigNb)
      bigNb = vetor[i];
  }

  return bigNb;
}

// Radix Sort
void radix_sort(int * vetor, int length){

  int i, percentedSort[length], sDigit = 1;
  int bigNb = searchBiggest(vetor, length);

  while (bigNb / sDigit > 0){

    int couple[10] = { 0 };

    for (i = 0; i < length; i++)
      couple[(vetor[i] / sDigit) % 10]++;

    for (i = 1; i < 10; i++)
      couple[i] += couple[i - 1];

    for (i = length - 1; i >= 0; i--)
      percentedSort[--couple[(vetor[i] / sDigit) % 10]] = vetor[i];


    for (i = 0; i < length; i++)
      vetor[i] = percentedSort[i];

    sDigit *= 10;
  }
}

void redefines_vet(int *vet, int length) {
    int i ;

    for(i = 0; i < length; i++)
        vet[i] = (rand() % length);
}

void printVet(int *vet, int length) {
    int i ;

    for(i = 0; i < length; i++)
        printf("vet[%d]: %d\n", i, vet[i]);
}

int main(int argc, char *argv[]) {

    int length, i, choise;
    int *vet ;
    int print = 0 ;
    clock_t start, finish ;

    if(argc != 3 && argc != 4 && argc != 5) {
      printf("\nPARAMETER NOT ENTERED CORRECTLY!\n");
      return 0 ;
    } else if(argc == 4)
        print = 1;

    //Catch length of vector
    length = atoi(argv[2]);

    //malloc memory for vector
    vet = (int *) malloc(sizeof(int) * length);

    //Insert in vector with round numbers
    redefines_vet(vet, length);

    //Start Time Sorting
    start = clock();

    printf("PARAM:%s as\n", argv[1]);

    //Select choise
    for(i = 0; i < MAX_OPTIONS; i++) {
        if(strcmp(optionSorting[i], argv[1]) == 0) {
            choise = ++i;
            break ;
        }
    }

    //Print or Not
    if(print) {
        printf("VECTOR NOT ORDENED");
        printVet(vet, length);
    }


    switch(choise) {

        case 1: {
            printf("\nBUBBLE SORT\n");
            bubble_sort(vet, length);
        } break ;

        case 2: {
            printf("\nSELECTION SORT\n");
            selection_sort(vet, length);
        } break ;

        case 3: {
            printf("\nINSERTION SORT\n");
            insertion_sort(vet, length);
        } break ;

        case 4: {
            printf("\nSHELL SORT\n");
            shell_sort(vet, length);
        } break ;

        case 5: {
            printf("\nQUICK SORT\n");
            quick_sort(vet, 0, length);
        } break ;

        case 6: {
            printf("\n\nHEAP SORT\n");
            heap_start(vet, length);
            heap_sort(vet, length);
        } break ;

        case 7: {
            printf("\n\nMERGE SORT\n");
            int *vetAux = (int *) malloc(sizeof(int) * length);
            merge_sort(vet, vetAux, 0, length);
        } break ;

        case 8: {
            printf("\n\nRADIX SORT\n");
            radix_sort(vet, length);
        } break ;

        default: {
            printf("\nPARAMETER NOT FOUND!\n");
        } break ;
    }

    finish = clock();
    printf("IT TOOK %lf SECONDS TO EXECUTE.\n", (((double)(finish - start)) / CLOCKS_PER_SEC));

    //Print or Not
    if(print) {
        printf("VECTOR ORDENED");
        printVet(vet, length);
    }

    return 0 ;
}