Estrutura de Dados - Ordenação Parte 1 - Bubble sort e Quick sort

Ordenação

Hoje em dia temos que lidar com um grande volume de informações e será mais fácil lidar com elas se estiverem ordenadas com base em algum critério.

Imagina uma agenda de contatos onde os nomes são colocados de maneira sequencial, sem nenhum critério de ordenação. Ao buscar um nome específico, será necessário percorrer essa lista inteira até encontrar. No melhor caso o será  o primeiro e o pior caso será o último. Esse processo pode ser demorado caso a quantidade de informações seja muito grande.

A escolha do algoritmo de ordenação ideal é deve levar em consideração uma  série de variáveis como volume de informação, estrutura de dados de armazenamento, etc.

Hoje vamos falar sobre ordenação por troca, isto é, os elementos serão comparados uns aos outros e trocados de acordo com o critério desejado.

Os dois algoritmos mais básicos desse tipo de ordenação são o Bubble Sort e o Quick Sort

Bubble Sort

O algoritmo mais simples e conhecido, de fácil compreensão e implementação. Neste algoritmo, cada elemento será comparado com seu sucessor e trocado caso esteja fora de ordem. Com isso podemos perceber que será necessário várias iterações até que os elementos estejam completamente ordenados.

Apesar de ser simples de implementar, esse algoritmo possui uma ordem de N AO QUADRADO. Isso significa que seu desempenho terá uma curva crescente em função da quantidade de elementos.

Esse algoritmo então, pode não ser a escolha ideal caso tenhamos muitos elementos para ordenar e sim em um conjunto finito e controlado.

public class BubbleSort {

 public static void ordenar(int[] arr) {
  int n = arr.length;
  int temp = 0;
  for (int i = 0; i < n; i++) {
   for (int j = 1; j < (n - i); j++) {
    if (arr[j - 1] > arr[j]) {
     temp = arr[j - 1];
     arr[j - 1] = arr[j];
     arr[j] = temp;
    }

   }
  }
 }

 public static void main(String[] args) {
  int arr[] = { 3, 60, 35, 2, 45, 320, 5 };

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

  ordenar(arr);

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

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

}

Quick Sort

Este algoritmos usa a estratégia "Dividir para conquistar". O primeiro passo é escolher um pivô, em seguida, todos os elementos a direita que forem "menores" serão passados para esquerda do pivô e os elementos da esquerda que forme "maiores" serão passados para direita do pivô. No final dessa iteração, o pivô estará exatamente na posição que deveria.
O próximo passo é repetir esse passo para as sublistas a direita e à esquerda do pivô.

public class QuickSort {
 
 public static void ordenar(int arr[], int inicio, int fim) {
  if (inicio < fim) {
         int particao = particionar(arr, inicio, fim);
  
         ordenar(arr, inicio, particao-1);
         ordenar(arr, particao+1, fim);
     }
 }
 
 private static int particionar(int arr[], int inicio, int fim) {
     int pivo = arr[fim];
     int i = (inicio-1);
  
     for (int j = inicio; j < fim; j++) {
         if (arr[j] <= pivo) {
             i++;
  
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     }
  
     int temp = arr[i+1];
     arr[i+1] = arr[fim];
     arr[fim] = temp;
  
     return i+1;
 }

 
 public static void main(String[] args) {
  int arr[] = { 3, 60, 35, 2, 45, 320, 5 };

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

  ordenar(arr,0,arr.length-1);

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

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

}