Os Algoritmos de Ordenação e Recursividade
Por: Carolina234 • 21/8/2018 • 3.067 Palavras (13 Páginas) • 278 Visualizações
...
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
...