Ordenação de Vetores: mudanças entre as edições
De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
| (10 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
| Linha 2: | Linha 2: | ||
Os métodos de ordenação de vetores consistem em ordenar os vetores em ordem crescente (ou decrescente) de valores. | Os métodos de ordenação de vetores consistem em ordenar os vetores em ordem crescente (ou decrescente) de valores. | ||
Alguns métodos simples e bem conhecidos são: | |||
*Método de seleção (''selection sort'') | *Método de seleção (''selection sort'') | ||
*Método de inserção (''insertion sort'') | *Método de inserção (''insertion sort'') | ||
*Método da bolha (''bubble sort'') | *Método da bolha (''bubble sort'') | ||
Ver também <ref name="OrdenacaoVetores"> http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o</ref> <ref name="OrdenacaoVetoresC"> http://terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c</ref>. | |||
==Método de seleção (''selection sort'')== | ==Método de seleção (''selection sort'')== | ||
O ''' | O '''método de seleção''' é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos <ref name="SelectionSort">http://pt.wikipedia.org/wiki/Selection_sort</ref>. | ||
<source lang="c"> | <source lang="c"> | ||
| Linha 32: | Linha 34: | ||
==Método de inserção (''insertion sort'')== | ==Método de inserção (''insertion sort'')== | ||
O ''' | O '''método de inserção''' é um de algoritmo de ordenação simples, eficiente quando aplicado a um vetor com pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados <ref name="InsertionSort">http://pt.wikipedia.org/wiki/Insertion_sort</ref>. | ||
<source lang="c"> | <source lang="c"> | ||
| Linha 50: | Linha 52: | ||
==Método da bolha (''bubble sort'')== | ==Método da bolha (''bubble sort'')== | ||
O ''''' | O '''método da bolha''', ou '''ordenação por flutuação''', também é um algoritmo de ordenação. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas sobem em um tanque com água, daí o nome do algoritmo <ref name="BubbleSort">http://pt.wikipedia.org/wiki/Bubble_sort</ref>. | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
void bubble_sort(int vetor[], int tamanho) { | void bubble_sort(int vetor[], int tamanho) { | ||
int | int i, j, aux; | ||
for(i=tamanho-1; i >= 1; i--) { | |||
for(j=0; j < i ; j++) { | |||
for( | |||
for( | |||
if(vetor[j]>vetor[j+1]) { | if(vetor[j]>vetor[j+1]) { | ||
aux = vetor[j]; | aux = vetor[j]; | ||
vetor[j] = vetor[j+1]; | vetor[j] = vetor[j+1]; | ||
vetor[j+1] = aux; | vetor[j+1] = aux; | ||
} | } | ||
} | } | ||
| Linha 74: | Linha 72: | ||
#Analise o funcionamento de cada um dos '''algoritmos de ordenação''' a partir de '''testes de mesa'''. | #Analise o funcionamento de cada um dos '''algoritmos de ordenação''' a partir de '''testes de mesa'''. | ||
#'''Implementar''' e '''testar''' os três algoritmos. | #'''Implementar''' e '''testar''' os três algoritmos. | ||
#Construa um '''programa''' que recebe dados pelo teclado e os armazene na forma de '''vetores''' de 10 posições. Em seguida ordenar os dados com os '''algoritmos de ordenação'''. | #Construa um '''programa''' que recebe dados pelo teclado e os armazene na forma de '''vetores''' de 10 posições. Em seguida ordenar os dados com os '''algoritmos de ordenação'''. | ||
Edição atual tal como às 22h28min de 4 de outubro de 2014
Ordenação de Vetores
Os métodos de ordenação de vetores consistem em ordenar os vetores em ordem crescente (ou decrescente) de valores.
Alguns métodos simples e bem conhecidos são:
- Método de seleção (selection sort)
- Método de inserção (insertion sort)
- Método da bolha (bubble sort)
Método de seleção (selection sort)
O método de seleção é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição, depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos [3].
void selection_sort(int num[], int tam)
{
int i, j, min, aux;
for (i = 0; i < (tam-1); i++)
{
min = i;
for (j = (i+1); j < tam; j++) {
if(num[j] < num[min]) {
min = j;
}
}
if (i != min) {
aux = num[i];
num[i] = num[min];
num[min] = aux;
}
}
}
Método de inserção (insertion sort)
O método de inserção é um de algoritmo de ordenação simples, eficiente quando aplicado a um vetor com pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados [4].
void insertionSort(int numeros[], int tam) {
int i, j, eleito;
for (i = 1; i < tam; i++){
eleito = numeros[i];
j = i - 1;
while ((j>=0) && (eleito < numeros[j])) {
numeros[j+1] = numeros[j];
j--;
}
numeros[j+1] = eleito;
}
}
Método da bolha (bubble sort)
O método da bolha, ou ordenação por flutuação, também é um algoritmo de ordenação. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas sobem em um tanque com água, daí o nome do algoritmo [5].
void bubble_sort(int vetor[], int tamanho) {
int i, j, aux;
for(i=tamanho-1; i >= 1; i--) {
for(j=0; j < i ; j++) {
if(vetor[j]>vetor[j+1]) {
aux = vetor[j];
vetor[j] = vetor[j+1];
vetor[j+1] = aux;
}
}
}
}
Exercícios
- Analise o funcionamento de cada um dos algoritmos de ordenação a partir de testes de mesa.
- Implementar e testar os três algoritmos.
- Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores de 10 posições. Em seguida ordenar os dados com os algoritmos de ordenação.
Referências
--Evandro.cantu (discussão) 11h18min de 2 de setembro de 2014 (BRT)
