Algoritmos de Ordenação

Algoritmo de Ordenação

É um tipo de algoritmo utilizado para resolver problemas como pesquisa (lista telefônica), agrupamento de elementos repetidos; ordenando seus elementos.

Alguns tipos de algoritmos de ordenação que serão explicados:

• Insertion Sort
• Bubble Sort
• Quick Sort

Insertion sort

Insertion sort, ou ordenação por inserção, é um algoritmo de ordenação que é eficiente quando aplicado a um pequeno número de elementos. Sua complexidade é de O(n²) e é estável.

Ele percorre um vetor de elementos da esquerda para direita e à medida que se avança vai deixando os elementos mais à esquerda ordenados.

A imagem abaixo dá uma noção do que o Insertion Sort faz:





Uma implementação em Java seria feito da seguinte forma:

public static void insertionSort(int[] array){

                for (int i = 1; i < array.length; i++){

                        int a = array[i];

                        int j;

                        for (j = i - 1; j >= 0 && array[j] > a; j--){

                                array[j + 1] = array[j];

                                array[j] = a;

                        }

                }              

Bubble Sort

• É um algoritmo de classificação simples e bem conhecida.
• É uma ordenação O (n 2), o que torna bastante ineficiente para triagem de grandes volumes de dados.
• É estável e adaptável.
• Estratégia: "Comparação e troca."

Como funciona: Faz comparação do primeiro elemento com o segundo, do segundo com o terceiro, assim sucessivamente tendo n-1 comparado com n. Se não ordenar na primeira verificação, verifica-se novamente da mesma maneira, do primeira ao n elemento.

Acompanhe na figura abaixo a ordenação do vetor, cujos valores são [5,1,12,-5,16].

Legenda: Unsort= desordenado; Swap= troca; Ok=troca efetuada.




Implementação em Java

public class Ordenacao {

         /**

          * toShow - Mostrar o vetor

          */

         public static void toShow(long[] arr) {

                 for (int i = 0; i < arr.length; i++) {

                          System.out.print( " |" + arr[i] + "| " );

                 }

                 System.out.println( "" );

                 System.out.println( "" );

         }

         /**

          * BubbleSort

          *

          * @param arr

          */

         public static void bubbleSort(long[] arr) {

                 boolean trocado = true;

                 int j = 0;

                 long tmp;

                 while (trocado) {

                          trocado = false;

                          j++;

                          for (int i = 0; i < arr.length - j; i++) {

                                   if (arr[i] > arr[i + 1]) {

                                            tmp = arr[i];

                                            arr[i] = arr[i + 1];

                                            arr[i + 1] = tmp;

                                            trocado = true;

                                            toShow( arr );

                                   }

                          }

                 }

         }

}

Quick Sort

• É um algoritmo de ordenação rápida, que é usado não apenas para fins educacionais, mas amplamente aplicado.
• Em média, tem complexidade O (n log n), tornando-o adequado para classificar grandes volumes de dados.
• A ideia do algoritmo é razoavelmente simples e uma vez que você compreenda, você pode escrevê-lo tão rápido como bubblesort.
• Estratégia: Dividir pra conquistar

Como funciona:

1. Escolha um valor de pivô. Tomamos o valor do elemento do meio como valor pivô, mas pode ser qualquer valor. (O pivô não é necessariamente o elemento do meio, pode ser da direita ou esquerda também, dependerá dos elementos a serem ordenados).
2. Partição. Reorganizar elementos de maneira que todos os elementos que são menores que o pivô escolhido vão para a parte esquerda do vetor e todos os elementos maiores que o pivô, vão para a parte direita. Valores iguais ao pivô podem ficar em qualquer parte do array. Não é necessário dividir o vetor em partes iguais.
3. Ordenar ambas as partes. Aplicar algoritmo quicksort recursivamente para a esquerda e para a direita. Ou seja, em cada lado do vetor inicial dividí-lo novamente e fazer o mesmo até estar completamente ordenado.

EXEMPLO Ordenar {1, 12, 5, 26, 7, 14, 3, 7, 2}





Implementação em Java

int partition(int arr[], int left, int right)

{

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

      return i;

}

void quickSort(int arr[], int left, int right) {

      int index = partition(arr, left, right);

      if (left < index - 1)

            quickSort(arr, left, index - 1);

      if (index < right)

            quickSort(arr, index, right);