Ordenação de Vetores: mudanças entre as edições

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
 
(18 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.


Os métodos mais conhecidos são:
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 '''''selection sort''''' é 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>.
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="csharp">
<source lang="c">
public void SelectionSort(int[] vetor)
void selection_sort(int num[], int tam)  
{
{  
    int min, aux;
  int i, j, min, aux;
    for (int i = 0; i < vetor.Length - 1; i++)
  for (i = 0; i < (tam-1); i++)  
    {
  {
        min = i;
    min = i;
        for (int j = i + 1; j < vetor.Length; j++)
    for (j = (i+1); j < tam; j++) {
            if (vetor[j] < vetor[min])
      if(num[j] < num[min]) {
                min = j;
        min = j;
        if (min != i)
      }
         {
    }
            aux = vetor[min];
    if (i != min) {
            vetor[min] = vetor[i];
      aux = num[i];
            vetor[i] = aux;
      num[i] = num[min];
      num[min] = aux;
    }
  }
}
</source>
 
==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 <ref name="InsertionSort">http://pt.wikipedia.org/wiki/Insertion_sort</ref>.
 
<source lang="c">
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;
  }
}
</source>
 
==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 <ref name="BubbleSort">http://pt.wikipedia.org/wiki/Bubble_sort</ref>.
 
<syntaxhighlight lang="c">
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;
            }
         }
         }
     }
     }
}
}
</source>
</syntaxhighlight >
 
==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==
==Referências==
Linha 37: Linha 81:
----
----


[[Cat
[[Categoria:Estruturas de Dados]]

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)

Ver também [1] [2].

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

  1. Analise o funcionamento de cada um dos algoritmos de ordenação a partir de testes de mesa.
  2. Implementar e testar os três algoritmos.
  3. 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

  1. ↑ http://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
  2. ↑ http://terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c
  3. ↑ http://pt.wikipedia.org/wiki/Selection_sort
  4. ↑ http://pt.wikipedia.org/wiki/Insertion_sort
  5. ↑ http://pt.wikipedia.org/wiki/Bubble_sort

--Evandro.cantu (discussão) 11h18min de 2 de setembro de 2014 (BRT)

Disponível em “http://wiki.foz.ifpr.edu.br/wiki/index.php?title=Ordenação_de_Vetores&oldid=4881”