Ordenar vetor utilizando quicksort

Irei postando ao longo do tempo, alguns exercícios da faculdade que fiz recentemente.

Ordene um vetor gerado pelo método quicksort.

/*=============================================================================*
* includes                                                                     *
*=============================================================================*/

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

/*=============================================================================*
* typedef                                                                      *
*=============================================================================*/

struct lista {
       int iNum;
       struct lista *pLista;
};

typedef lista Lista;

/*=============================================================================*
* declaracoes                                                                  *
*==============================================================================*
/*-----------------------------------------------------------------------------*
* declaracoes - prototipos de funcoes                                          *
*-----------------------------------------------------------------------------*/

Lista* insereLista(Lista *, int);
int getTamanhoLista(Lista *);
void ordenaVetor(int *, int, int);
void criaVetor(Lista *, int *);


/*-----------------------------------------------------------------------------*
* funcao "main"                                                                *
*-----------------------------------------------------------------------------*/

int main(int argc, char *argv[]) {    
    Lista *pLista = NULL;
    int *pVet = NULL;
    
    for (int i = 0; i < 10; i++) {
        int iNum = (int) rand() % 10;
        pLista = insereLista(pLista, iNum);
    }
    
    criaVetor(pLista, pVet);
        
    system("pause");    
}

/*-----------------------------------------------------------------------------*
* corpo das funções - insereLista                                              *
*-----------------------------------------------------------------------------*/

Lista* insereLista(Lista *pLista, int iNum) {
       Lista *pAux = NULL;
       pAux = (Lista *) malloc(sizeof(Lista));
       pAux->iNum = iNum;
       pAux->pLista = pLista;
       return pAux;
}

/*-----------------------------------------------------------------------------*
* corpo das funções - getTamanhoLista                                          *
*-----------------------------------------------------------------------------*/

int getTamanhoLista(Lista *pLista) {
    int iTam = 0;
    Lista *pAux = pLista;
    while (pAux != NULL) {
          iTam++;
          pAux = pAux->pLista;
    }
    return iTam;
}

/*-----------------------------------------------------------------------------*
* corpo das funções - criaVetor                                                *
*-----------------------------------------------------------------------------*/

void criaVetor(Lista *pLista, int *pVet) {
     int iTamLista = 0;
     int i = 0;
     Lista *pAux = pLista;
     
     iTamLista = getTamanhoLista(pLista);
     pVet = (int *) malloc(sizeof(int) * iTamLista);
     
     
     while (pAux != NULL) {
           pVet[i] = pAux->iNum;
           pAux = pAux->pLista;
           i++;
     }
     
     ordenaVetor(pVet, 0, iTamLista - 1);
     
     printf("\n\n");
}

/*-----------------------------------------------------------------------------*
* corpo das funções - ordenaVetor                                              *
*-----------------------------------------------------------------------------*/

void ordenaVetor(int *pVet, int iPrim, int iUlt)
{
     int i, j, iMeio, iAux;
     i = iPrim;
     j = iUlt;
     iMeio = pVet[(i + j) / 2];
     do
     {
       while (pVet[i] < iMeio) i++;
       while (pVet[j] > iMeio) j--;
       if (i <= j) {
          iAux = pVet[i];
          pVet[i] = pVet[j];
          pVet[j] = iAux;
          i++;
          j--;
       }     
     } while (i <= j);

     if (iPrim < j) 
        ordenaVetor(pVet, iPrim, j);
     if (iUlt > i)
        ordenaVetor(pVet, i, iUlt);
}

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s