Os Algoritmos de Ordenação e Recursividade
Por: Victoria Circhia • 4/5/2017 • Trabalho acadêmico • 4.314 Palavras (18 Páginas) • 234 Visualizações
[pic 1] Universidade Tecnológica Federal do Paraná[pic 2]
Guilherme Sant’Anna Stresser
Engenharia Elétrica
Computação 2
Trabalho apresentado
ao Professor Leonardo
Gomes Guidolin
Algoritmos de ordenação e Recursividade
Medianeira - PR
ALGORITMOS DE ORDENAÇÃO
- Bubble Sort
1.1 Definição
Em diversas aplicações, tanto cientificas como comerciais, vamos encontrar problemas de ordenação, como por exemplo, ordenar números em ordem crescente ou decrescente, nomes em ordem alfabética, etc. Para ordenar os elementos de uma maneira eficaz é necessário o uso de um algoritmo de ordenação. Existem diversos algoritmos de ordenação, o conhecimento deles e suas aplicações é algo muito importante para um programador; conhecendo esses algoritmos, o programador poderá escolher o melhor de acordo com a necessidade, melhorando o desempenho da aplicação.
1.2 Funcionamento
O algoritmo Bubble Sort percorre todo o vetor diversas vezes, por isso, não é recomendado o uso dele para aplicações que requerem velocidade ou trabalhem com uma grande quantidade de dados. Como exemplo, vamos ordenar um vetor em ordem crescente composto pelos elementos {8, 9, 3, 5, 1}.
O algoritmo inicia comparando a primeira posição do vetor, que tem o elemento 8, com a segunda posição do vetor que tem o elemento 9.
Como o elemento 8 é menor que o elemento 9, não há troca de posição {8, 9, 3, 5, 1}.
Na próxima iteração, compara-se a segunda posição do vetor, que tem o elemento 9, comparando-o com a terceira posição do vetor, que tem o elemento 3 {8, 9, 3, 5, 1}.
Como elemento 9 é maior que o elemento 3 é feito a troca de posição e reordena-se o vetor.
Compara-se com a terceira posição do vetor, que agora tem o elemento 9, com a quarta posição do vetor que tem o elemento 5 {8, 3, 9, 5, 1}.
Como o elemento 9 é maior que o elemento 5, é feito a troca de posição e reordena-se o vetor.
Compara-se a quarta posição do vetor, que tem o elemento 9, com a quinta posição do vetor, que tem o elemento 1 {8, 3, 5, 9, 1}.
Como elemento 9 é maior que o elemento 1 é feito a troca de posição. Reordenando o vetor: {8, 3, 5, 1, 9}.
Dessa forma é feita a primeira iteração por completo. Com podemos verificar, o elemento com maior valor (9) foi ficou na última posição do vetor, esse processo vai se repetir até que o vetor esteja ordenado. Na próxima iteração, o segundo maior valor será ordenado para penúltima posição do vetor. Essa ordenação lembra como as bolhas num tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo, Bubble Sort (literalmente "flutuação por Bolha"). Na próxima iteração, todo esse processo vai se repetir, vejamos:
{8, 3, 5, 1, 9}: 8 > 3 = Sim, realizar troca. Reordenando o vetor:
{3, 8, 5, 1, 9}: 8 > 5 = Sim, realizar troca. Reordenando o vetor:
{3, 5, 8, 1, 9}: 8 > 1 = Sim, realiza troca. Reordenando o vetor:
{3, 5, 1, 8, 9}: 8 > 9 = Não, vetor permanece como está.
Com isso é feito uma segunda iteração por completo. Novamente o processo vai se repetir.
{3, 5, 1, 8, 9}: 3 > 5 = Não, vetor permanece como está.
{3, 5, 1, 8, 9}: 5 > 1 = Sim, realiza troca. Reordenando o vetor:
{3, 1, 5, 8, 9}: 5 >8 = Não, vetor permanece como está.
{3, 1, 5, 8, 9}: 8 > 9 = Não, vetor permanece como está.
Terceira iteração realizada por completo. O processo se repete novamente:
{3, 1, 5, 8, 9}: 3 > 1 = Sim, realiza troca. Reordenando o vetor:
{1, 3, 5, 8, 9}: 3 > 5 = Não, vetor permanece como está.
{1, 3, 5, 8, 9}: 5 > 8 = Não, vetor permanece como está.
{1, 3, 5, 8, 9}: 8 > 9 = Não, vetor permanece como está.
1.3 Exemplos de códigos
void bubble_sort_1 (int vetor[], int n) {
int k, j, aux;
for (k = 1; k < n; k++) {
for (j = 0; j < n - 1; j++) {
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 < n; k++) {
for (j = 0; j < n - k; 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 < k; 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.
...