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.

• Download 4845.main.cpp
• Enviar nova versã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);
}

Google Code Jam 2010 - Africa Classification Round A

Arvore Binária

4 EP - Poli USP - LIG4 (LigK)

Script - Vetor

Gerador de number list v2

Nenhum comentário foi encontrado.