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)