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!
Top comments (0)