Explorando as Fundamentais Estruturas de Dados: Algoritmos de Ordenação
Tags: braziliandevs
Published: 2023-08-06 22:04:49

## 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

```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

```ts
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

```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

```ts
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](www.codewars.com) 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.

```ts
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](https://www.linkedin.com/in/eng-matheus-prado/) no LinkedIn!

Até a próxima!