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 SelectionSort(int[] vetor)
{
    int min, aux;
    for (int i = 0; i < vetor.Length - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < vetor.Length; j++)
            if (vetor[j] < vetor[min])
                min = j;
        if (min != i)
        {
             aux = vetor[min];
             vetor[min] = vetor[i];
             vetor[i] = 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)

---