Trabalho De Estrutura De Dados Quicksort

Alunos: Armando Alan Ramalho de Almeida Matrícula: 13080004001 Carlos Eduardo Santos Santiago Matrícula: 13080003301

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; } public static void main(String[] args){ int i; int[] vet = new int[10]; Scanner entrada = new Scanner(System.in); for(i=0;i<=9;i++){