Ordenação de Vetores

Ordenação de Vetores

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:

• 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 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 .

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 insertion sort é um simples de algoritmo de ordenação, eficiente quando aplicado a um 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 .

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 bubble sort, ou ordenação por flutuação, é um algoritmo de ordenação dos mais simples. 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 em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo .

void bubble_sort(int vetor[], int tamanho) {
    int comparacoes = 0;
    int trocas = 0;

    for(int i=tamanho-1; i >= 1; i--) {
        for(int j=0; j < i ; j++) {
            comparacoes ++;
            if(vetor[j]>vetor[j+1]) {
                 aux = vetor[j];
                 vetor[j] = vetor[j+1];
                 vetor[j+1] = aux;
                 trocas++;
            }
        }
    }
}

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. Pesquise e compare a complexidade de cada algoritmo.
4. Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores. 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)

---