Essays.club - TCC, Modelos de monografias, Trabalhos de universidades, Ensaios, Bibliografias
Pesquisar

Os Algoritmos de Ordenação e Recursividade

Por:   •  21/8/2018  •  3.067 Palavras (13 Páginas)  •  332 Visualizações

Página 1 de 13

...

if (vetor[j] > vetor[j + 1]) {

aux = vetor[j];

vetor[j] = vetor[j + 1];

vetor[j + 1] = aux;

}

}

}

}

void bubble_sort_2 (int vetor[], int n) {

int k, j, aux;

for (k = 1; k

for (j = 0; j

if (vetor[j] > vetor[j + 1]) {

aux = vetor[j];

vetor[j] = vetor[j + 1];

vetor[j + 1] = aux;

}

}

}

}

void bubble_sort_4 (int vetor[], int n) {

int k, j, aux;

for (k = n - 1; k > 0; k--) {

for (j = 0; j

if (vetor[j] > vetor[j + 1]) {

aux = vetor[j];

vetor[j] = vetor[j + 1];

vetor[j + 1] = aux;

}

}

}

}

- Insertion Sort

2.1 Definição

O método de ordenação por Inserção Direta é o mais rápido entre os outros métodos considerados básicos, Bubblesort e Seleção Direta. A principal característica deste método consiste em ordenarmos o arranjo utilizando um sub-arranjo ordenado localizado em seu inicio, e a cada novo passo, acrescentamos a este sub-arranjo mais um elemento, até que atingimos o último elemento do arranjo fazendo assim com que ele se torne ordenado.

2.2 Funcionamento

Usaremos como exemplo uma sequência:

5 - 3 - 1 - 4 – 2

Inicialmente considera-se o primeiro elemento do arranjo como se ele estivesse ordenado; ele será considerado o sub-arranjo ordenado inicial.

Agora o elemento imediatamente superior ao o sub-arranjo ordenado, no o exemplo o número 3, deve se copiado para uma variável auxiliar qualquer. Após copiá-lo, devemos percorrer o sub-arranjo a partir do último elemento para o primeiro. Assim poderemos encontrar a posição correta da nossa variável auxiliar dentro do sub-arranjo. No caso verificamos que a variável auxiliar é menor que o último elemento do o sub-arranjo ordenado (o subarranjo só possui por enquanto um elemento, o número 5 ). O número 5 deve então ser copiado uma posição para a direita para que a variável auxiliar com o número 3, seja colocada em sua posição correta.

3-5-1-4-2

Verifique que o sub-arranjo ordenado possui agora dois elementos. Vamos repetir o processo anterior para que se continue a ordenação. Copiamos então mais uma vez o elemento imediatamente superior ao o sub-arranjo ordenado para uma variável auxiliar. Logo em seguida vamos comparando nossa variável auxiliar com os elementos do subarranjo, sempre a partir do último elemento para o primeiro Neste caso verificamos que a nossa variável auxiliar é menor que o último elemento do sub-arranjo. Assim, copiamos este elemento para a direita e continuamos com nossas comparações (5 permanece como cópia no lugar do 1). Aqui, mais uma vez a nossa variável auxiliar é menor que o elemento do sub-arranjo que estamos comparando. Por isso ele deve ser copiado para a direita, abrindo espaço para que a variável auxiliar seja colocada em sua posição correta.

1-3-5-4-2

Aplicando o algoritmo até que se chegue ao fim da sequência, poderá resultara a seguinte sequência:

1-3-4-5-2

1-2-3-4-5

2.2 Exemplo de código

void insertionSort(int vetorDesordenado[], int tamanhoVetor ){

int i, j, valorAtual;

for( j=1; j

valorAtual = vetorDesordenado[j];

i = j-1;

while(i >= 0 && vetorDesordenado[i] > valorAtual) {

vetorDesordenado[i+1] = vetorDesordenado[i]; i--;

}

vetorDesordenado[i+1] = valorAtual;

}

}

- Quick Sort

3.1 Definição

O problema da ordenação consiste em rearranjar um vetor v[0..n-1] em ordem crescente, ou seja, permutar os elementos do vetor de modo que tenhamos v[0] ≤ v[1] ≤ . . . ≤ v[n-1]. O algoritmo Quicksort, inventado por C.A.R. Hoare em 1962, resolve o problema.

Em algumas raras instâncias, o Quicksort pode ser tão lento quanto os algoritmos elementares; mas em geral é muito mais rápido. Mais precisamente, o algoritmo consome tempo proporcional a n log n em média e proporcional a n2 no pior caso.

Usaremos duas abreviaturas ao discutir o algoritmo. A expressão v[i..k] ≤ x será usada como abreviatura de v[j] ≤ x para todo j no conjunto de índices i..k. Analogamente, a expressão v[i..k] ≤ v[p..r] será interpretada como v[j] ≤ v[q] para todo j no conjunto i..k e todo q no conjunto p..r.

3.2 Funcionamento

O núcleo do algoritmo Quicksort é o seguinte problema da separação (= partition subproblem), que formularemos de maneira propositalmente vaga, rearranjar um vetor v[p..r] de modo que todos os elementos pequenos fiquem na parte esquerda do vetor e todos os elementos grandesfiquem na parte direita.

O

...

Baixar como  txt (19.8 Kb)   pdf (74 Kb)   docx (25 Kb)  
Continuar por mais 12 páginas »
Disponível apenas no Essays.club