Especificações do Ambiente: Características do Hardware e Software

PROJETO E ANÁLISE DE ALGORITMOS

Descrição dos Testes e Análises

Especificações do Ambiente: Características do Hardware e Software
Descreva outras especificações se for o caso.

Descrição dos Algoritmos
Quick Sort
Quem criou estratégia, melhor caso, pior caso, caso médio, etc.
Quem criou
Proposto por Hoare em 1960 quando visitou a universidade de Moscovo e publicado em 1962. Naquela época, Hoare trabalhou em um projeto de tradução de maquina para o Natioal Physical Laboratory. Ele criou o quick sort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente.
Quick Sort é o algoritmo de ordenação interna mais rápido que se conhece para uma ampla variedade de situações. Provavelmente é o mais utilizado.

Melhor caso
Acontece quando as partições têm sempre o mesmo tamanho (partições balanceadas)
C (n) = nlg n = O (n lg n)
Exemplo:

Caso médio
Partições podem ser feitas em qualquer posição no vetor.
C (n) = 1,39n lg n = O (n lg )
Exemplo:

Pior caso
Acontece quando o pivô é sempre o maior ou menor elemento (partições de tamanho desequilibrado).
C (n) = n (n+1)/2 = O (n²)
Exemplo:

Implementação do Algoritmo
#include
#include // Define uma constante
// Define a constant
#define MAX 3 // Protótipo da função de ordenação
// Ordination function prototype void quick_sort(int *a, int left, int right); // Função main
// Main Function int main(int argc, char** argv)
{
int i, vet[MAX]; // Lê MAX ou 10 valores // Read MAX or 10 values for(i = 0; i < MAX; i++) { printf("Digite um valor: "); scanf("%d", &vet[i]); } // Ordena os valores // Order values quick_sort(vet, 0, MAX - 1); // Imprime os valores ordenados // Print values in order ascendant printf("\n\nValores ordenados\n"); for(i = 0; i < MAX; i++) { printf("%d\n", vet[i]); }