Explorando as Fundamentais Estruturas de Dados: Algoritmos de Ordenação

Introdução

Continuando essa série de publicações sobre estrutura de dados. Na publicação anterior falei que essa série de publicações faz parte das minhas anotações e estudos sobre o assunto dentro da disciplina do tecnólogo que faço. A disciplina é de Estrutura de Dados e vamos continuar aprofundando.

Neste próximo passo, vamos explorar sobre os algoritmos de ordenação. Vamos começar!

A importância da Ordenação

Antes de aprofundar especificamente em ordenação, gostaria de falar sobre o que é esse grupo de algoritmos. Na publicação anterior, comentei que:

Um conjunto de dados é um tipo abstrato de dados, estabelecendo uma relação, as funções e as operações que podem ser aplicados a estes dados.

Desta maneira, os algoritmos de ordenação são ferramentas onde os métodos de ordenação são funções e/ou operações a esse conjunto de dados que possuem técnicas diversas de ordenação para resolver uma mesma tarefa.

Podemos assumir então que ordenar os dados é uma operação essencial, pois se refere a organização de um conjunto de dados que pode facilitar a busca, a recuperação e a análise desses mesmos dados.

Explorando diferentes tipos de ordenação

Existem vários tipos de algoritmos de ordenação, cada um com suas próprias características e eficiência.

Não falarei de todos, falarei dos dois que seguem nessa tabela a seguir:

Algoritmo	Descrição	Complexidade Big O
Bubble Sort	Comparação e troca de elementos adjacentes.	O(n^2)
Quick Sort	Algoritmo de divisão e conquista com escolha de pivô	O(n log n)
	e particionamento recursivo da lista.

O motivo de não falar de outros como o Merge Sort, por exemplo, é devido ao texto ficar muito longo e quero dar mais o tom do texto que existe tanto quanto a técnica iterativa quanto recursiva.

Estas anotações não isentam o estudo de outros métodos de ordenação.

Bubble Sort

Os elementos vão se deslocando a cada iteração até a posição correta para ordenação da lista. É importante lembrar que como os elementos neste tipo de ordenação são constantemente trocados, há um alto custo com essa troca de elementos.

Um aspecto interessante do Bubble Sort é que sempre é necessário apenas uma iteração em toda a lista para que o maior item de uma lista seja deslocado para o final dela.

Pseudocódigo

Procedimento BubbleSort(lista)
    n <- tamanho da lista
    i, j, aux inteiro

    Para i de 0 até n-1
        trocou <- Falso

        Para j de 0 até n-i-1
            Se lista[j] > lista[j+1] Então
                // Troca os elementos de posição
                aux <- lista[j]
                lista[j] <- lista[j+1]
                lista[j+1] <- aux
                trocou <- Verdadeiro
            Fim Se

        Fim Para

        Se trocou = Falso Então
            // A lista está totalmente ordenada, podemos encerrar o loop
            Parar
        Fim Se

    Fim Para

Fim Procedimento

Java

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] lista = {26, 47, 38, 11, 95};
        bubbleSort(lista);
        System.out.println("Lista ordenada: " + Arrays.toString(lista));
    }

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

        for (int i = 0; i < n - 1; i++) {

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Troca os elementos de posição
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                }
            }
        }
    }
}

Typescript

function bubbleSort(arr: number[]): void {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Troca os elementos de posição
                const temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

const lista = [26, 47, 38, 11, 95];
bubbleSort(lista);
console.log("Lista ordenada:", lista);

Quick Sort

Este é um algoritmo de ordenação que utiliza a técnica de recursão para resolver problemas de ordenação. A ideia é baseada na ideia de Dividir e Conquistar:

• Dividir: Pega-se um problema M e divide-se em subproblemas menores de forma recursiva.
• Conquistar: Une as soluções dos subproblemas para obter a solução do problema maior P.

Pseudocódigo

Como visto no pseudocódigo abaixo, para desenvolver este algoritmo vamos precisar de duas funções:

• 1ª Função é a Partição: É quem vai produzir o pivô que vai deslocar os elementos que são menores para um lado, e maiores para o outro.
• 2ª Função é o Quick Sort: É quem vai empregar a técnica recursiva e fazer uso da ideia de Dividir e Conquistar falada acima.

quicksort(p inteiro, q inteiro, vetor[] inteiro)
    inicio_modulo
        Declarar
            x inteiro;

        se (p < q)
            então
                x <- particao(p, q, vetor);
                quicksort(p, x - 1, vetor);
                quicksort(x + 1, q, vetor);
        fimse;
    fimMódulo;

Java

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] lista = {26, 47, 38, 11, 95};
        quickSort(lista, 0, lista.length - 1);
        System.out.println("Lista ordenada: " + Arrays.toString(lista));
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }

        int idxPivo = partition(arr, low, high);

        quickSort(arr, low, idxPivo - 1);
        quickSort(arr, idxPivo + 1, high);
    }

    public static int partition(int[] arr, int low, int high) {
        int pivo = arr[high];
        int idx = low - 1;

        for (int i = low; i < high; ++i) {
            if (arr[i] <= pivo) {
                idx++;
                int temp = arr[i];
                arr[i] = arr[idx];
                arr[idx] = temp;
            }
        }

        idx++;
        arr[high] = arr[idx];
        arr[idx] = pivo;

        return idx;
    }
}

Typescript

function qs(arr: number[], low: number, high: number): void {
    if (low >= high) {
        return;
    }

    const idxPivo = partition(arr, low, high);

    qs(arr, low, idxPivo - 1);
    qs(arr, idxPivo + 1, high);
}

function partition(arr: number[], low: number, high: number): number {
    const pivo = arr[high];

    let idx = low -1;

    for(let i = low; i < high; ++i) {
        if(arr[i] <= pivo) {
            idx++;
            const temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }
    }

    idx++;
    arr[high] = arr[idx];
    arr[idx] = pivo;

    return idx;
}

function quickSort(arr: number[]): void {
    qs(arr, 0, arr.length - 1);
}

const lista = [26, 47, 38, 11, 95];
quickSort(lista);
console.log("Lista ordenada:", lista);

Praticando

Sempre após o estudo teórico de um assunto, a melhor maneira de concretizar o entendimento dos fundamentos é praticando com desafios de código. Retornando ao Codewars vamos buscar solucionar alguns desafios que tenham a ordenação como objetivo a ser alcançado.

7 kyu - Sort Numbers

Descrição do problema:

Complete a solução para que ela ordene a matriz de números passada como parâmetro. Se a função receber uma array vazia ou um valor nulo, ela deve retornar uma array vazia.

Por exemplo:

solution([1, 2, 10, 50, 5]); // should return [1, 2, 5, 10, 50]
solution([]); // should return []

Solução:

Aqui, optei pelo uso do Bubble Sort, é um algoritmo mais simples de escrever, o custo computacional não é uma questão aqui e serve exatamente para o que eu quero fazer.

export function solution(nums: number[]): number[] {
  //A condição de contorno caso a função receba um array vazio ou nulo
  if (nums.length === 0 || nums === null) return [];

  //Operação exata do algoritmo de Bubble Sort comentado anteriormente
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j+1]) {
        //Trocar os elementos de posição
        const temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
      }
    }
  }

  return nums;
}

Conclusão

Chegamos ao final desta segunda publicação desta série sobre Estrutura de Dados e Algoritmos. Lembrando que essa síntese de ideias fazem parte de anotações soltas e pessoais para o estudo da disciplina do tecnólogo, e aqui é uma forma de eu sintetizar essas ideias e poder compartilhar algo que estou aprendendo.

Se puder, vamos nos conectar no LinkedIn!

Até a próxima!