Algoritmo de ordenação Quick Sort

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

[ Hits: 9.572 ]

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

Jogo Windows Invaders (com gráficos)

Biblioteca de tipos abstratos

Informação do sistema

Vetor de lista

Jogo da Velha com IA invencivel


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts