sort.c

gistfile1.txt

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

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void insert(int *arr, int n) {
      int x = arr[n];
      --n;
      
      while (n >= 0 && arr[n] > x)
      {
          arr[n+1] = arr[n];
          --n;
      }
      arr[n+1] = x;
}

void insertsort(int *arr, int n) {
    int i = 1;
    
    while (i < n)
    {
      insert(arr, i);
      ++i;
    }
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int *arr, int n) {
    int pivot = arr[0];
    int i=1, j;
    
    for (j=1; j<n; j++)
    {
        if (arr[j] < pivot)
        {
            swap(arr+i, arr+j);
            ++i;
        }
    }
    swap(arr+i-1, arr);
    return i-1;
}

void quicksort(int *arr, int n) {
    if (n > 0)
    {
        int p = partition(arr, n);
        quicksort(arr, p);
        quicksort(arr + p + 1, n - p - 1);
    }
}

void merge(int *arr, int m, int n) {
    int *x = malloc(n*sizeof(int));
    int j=0, k=m;
    
    for (int i=0; i<n; ++i) {
        if (j==m)                           x[i] = arr[k++];
        else if (k==n)                      x[i] = arr[j++];
        else if (arr[j] < arr[k])           x[i] = arr[j++];
        else                                x[i] = arr[k++];
    }
    for (int i=0; i<n; i++) arr[i]=x[i];
    free(x);
}

void mergesort(int *arr, int n) {
    if (n > 1)
    {
        int middle = n/2;
        mergesort(arr, middle);
        mergesort(arr + middle, n - middle);
        merge(arr, middle, n);
    }
}


int aplica_ordena(int *arr, int n, int algo) {
    switch(algo) {
        case 0: qsort(arr, n, sizeof(int), cmpfunc);
                break;
        case 1: insertsort(arr, n);
                break;
        case 2: quicksort(arr, n);
                break;
        case 3: mergesort(arr, n);
                break;
    }
}

int main(int argv, char *argc[]) {
    if (argv < 3) {
        printf("Uso: ./sort n algoritmo\n");
        return -1;
    }

    int x, i, n, cnt = 0;
    int *arr;
    n = atoi(argc[1]);
    int algo = atoi(argc[2]);
    time_t t0, t1;

    arr = (int *) malloc(sizeof(int)*n);

    for (i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("START!\n");
    t0 = time(NULL);
    aplica_ordena(arr, n, algo);
    t1 = time(NULL);
    printf("tempo total: %ld segundos\n", t1-t0);

    free(arr);

    return 0;

}