Método de classificação rápido e eficiente

Alunos: Armando Alan Ramalho de Almeida

Carlos Eduardo Santos Santiago

QuickSort

O que é ?

Método de Ordenação rápido e Eficiente.

Desenvolvido por Sir Charles Antony Richard Hoare.

Desenvolvedor da lógica Hoare e a linguagem formal CSL (usado para especificar interações entre processos concorrentes).

Método criado ao tentar traduzir um dicionário de inglês para o russo.

Método Utilizado pelo Quick-Sort

Ordena uma sequência S usando uma sequência simples.

A ideia principal é aplicar a técnica de “DIVISÃO E CONQUISTA” dividindo S em subconjuntos menores e então usando o método recursivo para ordenar esses subconjuntos.

Representação

Eficiência do Algoritmo

Melhor Caso : O pivô é tal que divide a sequência ao meio.

Serão feitas  θ(n log2 n)comparações.

Pior Caso: O pivô é tal que cada partição produz uma parte com um elemento, e outra com n-1 elementos

A complexidade é quadrática – θ(n2)

Obs: Na prática os casos ruins são raros , e o QuickSort apresenta um excelente desempenho.

Código

import java.util.Scanner;

public class QuickSort {

public static void quick_sort(int []v,int ini, int fim) {

int meio;

if (ini < fim) {

meio = particao(v, ini, fim);

quick_sort(v, ini, meio);

quick_sort(v, meio + 1, fim);

}

}

public static int particao(int []v, int ini, int fim) {

int pivo, topo, i;

pivo = v[ini];

topo = ini;

for (i = ini + 1; i <= fim; i++) {

if (v[i] < pivo) {

v[topo] = v[i];

v[i] = v[topo + 1];

topo++;

}

}

v[topo] = pivo;

return topo;

}