Algoritmo de ordenação Quick Sort

Publicado por João Cristiano Monteiro da Silva (última atualização em 30/11/2010)

[ Hits: 9.685 ]

Download 4845.main.cpp




Algoritmo que implementa a ordenação quick sort, aplicando o conceito de template (permite reutilização de código) e partição, conceito amplamente abordado para explicar esse tipo de ordenação.

  



Esconder código-fonte

#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename T>
void troca(T *a, T *b) {
    T aux = *a;
    *a = *b;
    *b = aux;
}

template <typename T>
void quicksort(T aux[], int inicio, int fim) {
    if (fim > inicio) {
        int retorno = particao(aux, inicio, fim);
        quicksort(aux, inicio, retorno - 1);
        quicksort(aux, retorno + 1, fim);
    }
}

template <typename T>
int particao(T aux[], int inicio, int fim) {
    int temp = inicio;
    while (true) {
        while (aux[inicio] <= aux[temp]) inicio++;
        while (aux[fim] > aux[temp]) fim--;
        if (fim < inicio) {
            troca(&aux[temp], &aux[fim]);
            return (fim);
        }
        troca(&aux[inicio], &aux[fim]);
    }
}

int main(int argc, char **argv) {
    //int vetor[8] = {25, 32, 12, -8, 9, 220, 5, 1};
    //double vetor[8] = {25.56, 32.12, 12.89, -8.54, 9.08, 220.54, 5.48, 1.56};
    char vetor[8] = {'h', 'a', 'd', 'e', 'f', 'g', 'b', 'c'};

    cout << "Vetor original: " << endl;
    for (int i = 0; i < 8; i++) {
        cout << "Posicao " << i << " = " << vetor[i] << endl;
    }
    cout << endl << endl;
    cout << "Vetor ordenado: " << endl;
    quicksort(vetor, 0, 7);
    for (int i = 0; i < 8; i++) {
        cout << "Posicao " << i << " = " << vetor[i] << endl;
    }
    return (EXIT_SUCCESS);
}

Scripts recomendados

Árvore binária AVL

signal.h - Um exemplo

Arvores Red Black

4 EP - Poli USP - LIG4 (LigK)

Gerador de number list v2


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts