P6 Estructuras 1 (EJ 11 Y 12) (V2)

/** QUICKSORT
*
*   - NO ES ESTABLE
**/

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

#define S(a) (sizeof(a) / sizeof(a[0]))
#define max(a,b) (a<b) ? b : a
#define min(a,b) (a>b) ? b : a

typedef enum {ALEATORIO, ULTIMO, MEDIO, MEDIANA_PMU} pivotType;

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

int partition(int arr[], int l, int r, pivotType P){
    int piv_index;
    switch(P){
        case ALEATORIO:
            piv_index = rand()%(r-l+1) + l;
            break;
        case ULTIMO:
            piv_index = r;
            break;
        case MEDIO:
            piv_index = (l+r)/2;
            break;
        case MEDIANA_PMU:
            piv_index = arr[l] + arr[r] + arr[(l+r)/2] - max(arr[l], max(arr[r], arr[(l+r)/2])) - min(arr[l], min(arr[r], arr[(l+r)/2]));
            piv_index = (piv_index == arr[(l+r)/2]) ? (l+r)/2 : ((piv_index == arr[r]) ? r : l );
            break;
        default:
            piv_index = r;
            break;
    }

    swap(&arr[piv_index], &arr[r]);

    int i = l, j;
    int pivot = arr[r];

    for(j = l; j<=r-1; j++)
        if(arr[j] <= pivot)
            swap(&arr[i++], &arr[j]);
    swap(&arr[i], &arr[r]);

    return i;
}

int quicksort(int arr[], int l, int r, pivotType P){
    static int llamadas = 0;
    llamadas++;
    if(l<r){
        int p = partition(arr, l, r, P);
        quicksort(arr, l, p-1, P);
        quicksort(arr, p+1, r, P);
    }

    return llamadas;
}

int main()
{
    int k;
    srand(time(NULL));
    int a[] = {3,7,11,12,2,4,3,129,32,45,121,764,76,5,8};

    for(k=0; k<S(a); k++) printf("%d ", a[k]); puts("\n");

    int calls = quicksort(a, 0, S(a)-1, MEDIANA_PMU);

    printf("Llamadas; %d\n", calls);
    for(k=0; k<S(a); k++) printf("%d ", a[k]); puts("\n");

    return 0;
}