#include "quicksort.h"



void particao(int esq, int dir, int *i, int *j, int a[])

{

    int pivo, temp;



    *i = esq;

    *j = dir;

    pivo = a[*i];



    do {

        while (pivo > a[*i])

            (*i)++;



        while (pivo < a[*j])

            (*j)--;



        if (*i <= *j) {

            temp = a[*i];

            a[*i] = a[*j];

            a[*j] = temp;



            (*i)++;

            (*j)--;

        }

    } while (*i <= *j);

}



void ordena(int esq, int dir, int a[])

{

    int i, j;



    particao(esq, dir, &i, &j, a);



    if (esq < j)

        ordena(esq, j, a);



    if (i < dir)

        ordena(i, dir, a);

}



void quickSort(int a[], int *n)

{

    ordena(0, (*n)-1, a);

}



void particaoLista(int esq, Ponteiro *esquerda, Ponteiro *esquerdaOriginal, int dir, Ponteiro *direita, Ponteiro *direitaOriginal, int *i, int *j, Lista *a)

{

    int pivo;

    Ponteiro x, w;



    *i = esq;

    *j = dir;

    pivo = retornaChave(*esquerda);



    do {

        while (pivo > retornaChave(*esquerda)) {

            *esquerda = retornaProx(*esquerda);

            (*i)++;

        }



        while (pivo < retornaChave(*direita)) {

            *direita = retornaAnt(*direita);

            (*j)--;

        }





        if (*i <= *j) {



            if((*esquerdaOriginal == *esquerda) && (*esquerdaOriginal != *direita)){

                *esquerdaOriginal = *direita;

            }



            if((*direitaOriginal == *direita) && (*direitaOriginal != *esquerda)){

                *direitaOriginal = *esquerda;

            }



            if(retornaProx(*esquerda) != *direita){

                x = retornaProx(*esquerda); w = retornaAnt(*direita);

            }else{

                x = (*esquerda); w = (*direita);

            }



            trocaPosicao(*esquerda, *direita, a);

/*

            Ponteiro aux = *esquerda;

            *esquerda = *direita;

            *direita = aux;

*/

            *esquerda = x; (*i)++;

            *direita = w; (*j)--;

        }

    } while (*i <= *j);

}



void ordenaLista(int esq, Ponteiro esquerda, int dir, Ponteiro direita, Lista *a)

{

    int i, j;

    Ponteiro iCel = esquerda;

    Ponteiro jCel = direita;



    particaoLista(esq, &iCel, &esquerda, dir, &jCel, &direita, &i, &j, a);



    if (esq < j)

        ordenaLista(esq, esquerda, j, jCel, a);



    if (i < dir)

        ordenaLista(i, iCel, dir, direita, a);

}



void quickSortLista(Lista *a)

{

    Ponteiro esquerda = a->primeiro->prox;

    Ponteiro direita = a->ultimo;



    ordenaLista(0, esquerda, a->numElementos-1, direita, a);

}



void particaoRegistro(int esq, int dir, int *i, int *j, Registro r[])

{

    int pivo;

    Registro temp;



    *i = esq;

    *j = dir;

    pivo = retornaChaveReg(&r[*i]);



    do {

        while (pivo > retornaChaveReg(&r[*i]))

            (*i)++;



        while (pivo < retornaChaveReg(&r[*j]))

            (*j)--;



        if (*i <= *j) {

            temp = r[*i];

            r[*i] = r[*j];

            r[*j] = temp;



            (*i)++;

            (*j)--;

        }

    } while (*i <= *j);

}



void ordenaRegistro(int esq, int dir, Registro r[])

{

    int i, j;



    particaoRegistro(esq, dir, &i, &j, r);



    if (esq < j)

        ordenaRegistro(esq, j, r);



    if (i < dir)

        ordenaRegistro(i, dir, r);

}



void quickSortRegistro(Registro r[], int *n)

{

    ordenaRegistro(0, (*n)-1, r);

}