Estrutura de Dados - Ordenação Parte 2 - Selection, Insertion e Shell sort

Selection sort.

O algoritmo consiste em selecionar o menor (ou maior) elemento fora de ordem colocá-lo em sua posição correta. Para fazer isso, primeiro os elementos devem ser divididos em duas partes: os elementos já ordenados e os elementos que ainda não foram ordenados.

Inicialmente a parte ordenada estará vazia, enquanto a parte não ordenada possuirá todos os elementos.

Após a divisão, o algoritmo irá encontrar o menor elemento do lado não ordenado e colocá-lo no lado ordenado. Esse passo irá se repetir até que o lado não ordenado fique vazio.

Este algoritmo possui duas grandes vantagens, primeiro, é um algoritmo simples de ser implementado e segundo, não há consumo de memória além daquele já alocado para os elementos originais, uma vez que a divisão de lado ordenado e lado não ordenado é feita no próprio vetor que queremos ordenar.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande.

public class SelectionSort {

 public static void ordenar(int arr[]) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
   int min = i;
   for (int j = i + 1; j < n; j++)
    if (arr[j] < arr[min])
     min = j;

   int temp = arr[min];
   arr[min] = arr[i];
   arr[i] = temp;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 64, 25, 12, 22, 11 };

  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}

Insertion sort

O algoritmos consiste inicialmente em selecionar um pivô e comparar os elementos seguintes, um a um. Se o elemento seguinte for maior que o pivô, esse elemento agora passará a ser o novo pivô. Se o elemento for menor que o pivô, os elementos anteriores ao pivô serão percorridos até ser encontrado o elemento maior que o elemento encontrado anteriormente colocando-o logo antes do elemento maior.

Este algoritmo possui uma vantagem: não há consumo de memória além daquele já alocado para os elementos originais, uma que toda a ordenação ocorre dentro dos próprios elementos.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande, assim como o selection sort.

public class InsertionSort {

 public static void sort(int arr[]) {
  int n = arr.length;
  for (int i = 1; i < n; ++i) {
   int k = arr[i];
   int j = i - 1;

   while (j >= 0 && arr[j] > k) {
    arr[j + 1] = arr[j];
    j = j - 1;
   }
   arr[j + 1] = k;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 12, 11, 13, 5, 6 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  sort(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");

  System.out.println();
 }

}

Shell sort

Este algoritmo consiste em realizar trocas entre os elementos que estão posicionados a uma distância determinada. A distância inicial pode ser definida por d = n /  2 e a cada iteração diminuímos a essa distância, por exemplo, se você tem 10 elementos

iteração 1) d = 10 / 2 = 5;
iteração 2) d =  5 / 2 = 3;
iteração 3) d =  3 / 2 = 2
iteração 4) d =  2 / 2 = 1

Os elementos estarão ordenados quando a distância for menor ou igual a zero.

public class ShellSort {

 public static int ordenar(int arr[]) {
  int n = arr.length;

  for (int gap = n / 2; gap > 0; gap /= 2) {
   for (int i = gap; i < n; i += 1) {
    int temp = arr[i];

    int j;
    for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
     arr[j] = arr[j - gap];

    arr[j] = temp;
   }
  }
  return 0;
 }

 public static void main(String args[]) {
  int arr[] = { 12, 34, 54, 2, 3 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }
}