PDF - VERSÃO DE IMPRESSÃO

Lição 8 - Métodos de Ordenação e Aplicações

objetivo

Na lição anterior, estudamos os fundamentos das estruturas de dados, como pilhas, filas e alocação dinâmica. Nesta lição, exploramos os métodos de ordenação sob a perspectiva da ciência de dados, um campo em que a organização eficiente de informações é essencial para a análise e a tomada de decisões.

Você será introduzido aos principais algoritmos de ordenação, compreendendo como eles funcionam, suas complexidades e os cenários mais adequados para sua aplicação. Ademais, destacarei o impacto desses métodos no processamento de grandes volumes de dados e na otimização de pipelines analíticos. Ao final desta lição, você será capaz de selecionar e aplicar técnicas de ordenação de maneira estratégica, contribuindo para soluções ágeis e precisas no tratamento e na visualização de dados.

Animado para prosseguir seus estudos sobre ciência de dados?

problematização

No dia a dia da ciência de dados, lidar com grandes volumes de informações desorganizadas é um desafio constante. Dados desordenados dificultam a análise, comprometem o desempenho de algoritmos e atrasam a geração de insights precisos.

Imagine, por exemplo, um cenário em que uma empresa precisa identificar rapidamente seus melhores clientes a partir de milhões de registros de compras. Sem um método eficiente para organizar os dados, essa tarefa se torna lenta e imprecisa. Nesse sentido, os métodos de ordenação surgem, então, como uma solução fundamental para estruturar esses dados de forma eficiente, facilitando buscas rápidas, comparações e classificações essenciais. Na ordenação de registros em um banco de dados, na preparação de dados para algoritmos de aprendizado de máquina ou no processamento de informações em tempo real, a aplicação de técnicas de ordenação permite transformar o caos dos dados brutos em uma base organizada e funcional.

A ordenação se torna, dessa forma, uma ferramenta indispensável para otimizar análises, garantir a integridade dos resultados e suportar decisões estratégicas em diversos contextos.

Vamos aprender mais sobre isso?

case

Vamos entender, agora, como os métodos de ordenação e suas aplicações funcionam na prática? Como exemplo, temos a DataVision Analytics, uma empresa fictícia especializada em soluções de inteligência de negócios. A empresa foi contratada por uma grande rede varejista para resolver um problema crítico: otimizar o processo de análise de vendas e identificar padrões de comportamento de compra em tempo hábil. O cliente enfrentava dificuldades para processar milhões de registros de transações diárias em seu banco de dados, resultando em análises lentas e informações desatualizadas que prejudicavam a tomada de decisões estratégicas, como o gerenciamento de estoques e as campanhas promocionais.

Os cientistas de dados, então, iniciaram o projeto estruturando os dados e aplicando métodos de ordenação avançados. Utilizando algoritmos, como Merge Sort e Quick Sort, para organizar os registros de vendas por data, valor e região, foi possível reduzir drasticamente o tempo necessário para processar e classificar os dados.

Ao final do projeto, o tempo de análise dos dados foi reduzido em 60%, permitindo que a rede varejista obtivesse relatórios diários precisos. Com isso, a empresa passou a prever demandas com maior assertividade, evitando rupturas de estoque e diminuindo perdas.

Dessa forma, o exemplo demonstra como técnicas de ordenação, combinadas com práticas eficientes de ciência de dados, transformam grandes volumes de informações em insights estratégicos, otimizando processos e promovendo resultados tangíveis para a empresa.

Vamos aprender mais sobre isso?

Conceitualização

A ordenação é um conceito fundamental em ciência de dados, sendo responsável por organizar os elementos de um conjunto de dados em uma determinada sequência, como ordem crescente ou decrescente. Ziviani (2006) afirma que a ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado. Borin (2020), por sua vez, reforça que é usual dispormos de dados armazenados em um sistema que necessitam de ordenação.

Certamente, em sua vida profissional, você precisará ordenar dados com características numéricas, em ordem crescente ou decrescente. Ademais, a organização dos dados torna as tarefas de busca, análise e manipulação muito mais eficientes.

Quando lidamos com grandes volumes de informações, a ordenação desempenha um papel essencial, facilitando a identificação de padrões, a criação de relatórios e a otimização de algoritmos. Por exemplo, métodos ordenados são usados em operações, como a busca binária, na qual a eficiência depende diretamente da ordenação prévia dos dados.

Classificação dos algoritmos de ordenação

Os algoritmos podem ser categorizados em ordenação interna e ordenação externa, dependendo do tamanho dos dados e da memória disponível. Na ordenação interna, os dados são processados diretamente na memória principal do computador, adequada para situações em que o conjunto de dados é suficientemente pequeno para caber na memória RAM. Ziviani (2006) explica que essa abordagem é utilizada quando o arquivo a ser ordenado cabe todo na memória principal. Algoritmos, como Bubble Sort, Insertion Sort e Quick Sort, são exemplos desse tipo de ordenação, pois operam com eficiência em cenários de menor volume de dados.

A ordenação externa, por sua vez, é utilizada quando o volume de dados é tão grande que não pode ser completamente carregado na memória principal. Ziviani (2006) destaca que isso ocorre quando o arquivo a ser ordenado não cabe na memória principal. Nesse caso, os dados são processados em partes, sendo armazenados temporariamente em disco durante a execução do algoritmo. Esse método é amplamente aplicado em sistemas que lidam com big data ou bancos de dados extensos. Algoritmos, como Merge Sort Externo, são projetados para otimizar esse tipo de processamento, garantindo que grandes volumes sejam ordenados de forma eficiente sem comprometer os recursos do sistema.

A escolha entre ordenação interna e externa depende diretamente do tamanho dos dados e da quantidade de memória disponível. Observe o exemplo ao organizar uma lista de contatos de um aplicativo de mensagens. Se o número de contatos do usuário for relativamente pequeno, algoritmos, como QuickSort ou Insertion Sort (ordenação interna), podem ser usados para ordenar os nomes diretamente na memória, resultando em uma ordenação rápida e sem necessidade de acesso ao disco. Já na ordenação externa pense na ordenação de registros de um grande banco de dados de transações financeiras. Se houver milhões de registros, a ordenação deverá ser feita em blocos menores que cabem na memória, combinando-os depois com um algoritmo, como o Merge Sort Externo, garantindo que o sistema consiga ordenar os dados de forma eficiente sem esgotar os recursos da máquina.

Entender essa diferenciação é fundamental para que você, futuro técnico em desenvolvimento de sistemas, possa escolher a abordagem mais adequada conforme as características do problema, garantindo a eficiência dos processos e o uso racional dos recursos computacionais.

Principais algoritmos de ordenação

Os principais algoritmos de ordenação permitem organizar informações de forma eficiente, facilitando buscas, análises e otimizações em grandes volumes de dados. A apresentação teórica e prática desses métodos destaca suas características, sua complexidade computacional e suas aplicações adequadas em diferentes cenários.

O Bubble Sort é um método simples e intuitivo que realiza a ordenação comparando pares de elementos adjacentes e trocando suas posições sempre que necessário. Segundo Groner (2019), ele compara a cada dois valores adjacentes e faz a sua troca se o primeiro valor for maior que o segundo. Sua execução segue o princípio de borbulhar os maiores valores para o final da lista. Embora fácil de implementar, apresenta uma complexidade quadrática O(n2), o que o torna ineficiente para grandes conjuntos de dados, sendo mais adequado a contextos educacionais ou listas pequenas. Confira um exemplo do método na Figura 1 a seguir:

Figura 1 - Bubble Sort em Python
Fonte: o autor.

#PraCegoVer: na Figura 1, temos na Linha 1: def bubble_sort(lista); na Linha 2: n = len(lista); na Linha 3: # Percorre toda a lista; na Linha 4: for i in range(n - 1):; na Linha 5: # Últimos elementos já estão ordenados, então não precisam ser verificados; na Linha 6: for j in range(n - 1 - i):; na Linha 7: if lista[j] > lista[j + 1]:; na Linha 8: # Troca os elementos se estiverem fora de ordem; na Linha 9: lista[j], lista[j + 1] = lista[j + 1], lista[j]; na Linha 11: # Aplicação; na Linha 12: numeros = [64, 34, 25, 12, 22, 11, 90]; na Linha 13: print("Lista original:", numeros); na Linha 15: bubble_sort(numeros); na Linha 17: print("Lista ordenada:", numeros). Nas Linhas 10, 14 e 16 não há conteúdo escrito. Fim da descrição.

O Insertion Sort organiza os dados inserindo elementos de maneira ordenada em uma parte da lista que já está ordenada. Groner (2019) explica que ele constroi o array ordenado final, um valor de cada vez. A cada iteração, um elemento é comparado com os anteriores e inserido em sua posição correta. Esse método possui desempenho linear O(n2) [1] em listas quase ordenadas, mas também complexidade O(n2) no pior caso. É ideal para conjuntos de dados pequenos ou situações em que a lista está quase organizada. Confira um exemplo do método na Figura 2 a seguir:

Figura 2 - Insertion Sort em Python
Fonte: o autor.

#PraCegoVer: na Figura 2, temos na Linha 1: def insertion_sort(lista):; na Linha 2: # Percorre a lista a partir do segundo elemento; na Linha 3: for i in range(1, len(lista)):; na Linha 4: chave = lista[i] # O elemento que será comparado; na Linha 5: j = i – 1; na Linha 6: # Move os elementos da lista que são maiores que a chave uma posição à frente; na Linha 7: while j >= 0 and lista[j] > chave:; na Linha 8: lista[j + 1] = lista[j]; na Linha 9: j -= 1; na Linha 10: # Coloca a chave na posição correta; na Linha 11: lista[j + 1] = chave; na Linha 13: # Aplicação; na Linha 14: numeros = [64, 34, 25, 12, 22, 11, 90]; na Linha 15: print("Lista original:", numeros); na Linha 17: insertion_sort(numeros); na Linha 19: print("Lista ordenada:", numeros). Nas Linhas 12, 16 e 18 não há conteúdo escrito. Fim da descrição.

O Quick Sort é um dos algoritmos mais eficientes para ordenação interna, utilizando o conceito de divisão e conquista. Groner (2019) explica que, devido à sua característica, ele é um pouco mais complexo que os outros algoritmos vistos até aqui. O algoritmo escolhe um pivô e divide a lista em duas partes: elementos menores e maiores que o pivô, ordenando-os recursivamente. Sua complexidade média é O(n log n). Confira um exemplo do método na Figura 3 a seguir:

Figura 3 - Quick Sort em Python
Fonte: o autor.

#PraCegoVer: na Figura 3, temos na Linha 1: def quick_sort(lista):; na Linha 2: # Caso base: listas com 0 ou 1 elemento já estão ordenadas; na Linha 3: if len(lista) <= 1:; na Linha 4: return lista; na Linha 6: # Escolha do pivô (neste caso, o último elemento); na Linha 7: pivo = lista[-1]; na Linha 8: menores = [x for x in lista[:-1] if x <= pivo] # Elementos menores ou iguais ao pivô; na Linha 9: maiores = [x for x in lista[:-1] if x > pivo] # Elementos maiores que o pivô; na Linha 11: # Ordena as sublistas menores e maiores, e junta com o pivô; na Linha 12: return quick_sort(menores) + [pivo] + quick_sort(maiores); na Linha 14: # Aplicação; na Linha 15: numeros = [64, 34, 25, 12, 22, 11, 90]; na Linha 16: print("Lista original:", numeros); na Linha 18: ordenada = quick_sort(numeros); na Linha 20: print("Lista ordenada:", ordenada). Nas Linhas 5, 10, 13, 17 e 19 não há conteúdo escrito. Fim da descrição.

Por fim, o Merge Sort também utiliza a abordagem de divisão e conquista, dividindo o conjunto em partes menores até que cada elemento esteja isolado. Em seguida, as sublistas são combinadas de forma ordenada. Diferentemente do Quick Sort, o Merge Sort garante desempenho consistente com complexidade O(n log n) mesmo nos piores casos. Sua aplicação é ideal para grandes volumes de dados e situações que envolvem ordenação externa, como arquivos armazenados em disco. Segundo Groner (2019), ele é o primeiro algoritmo de ordenação que pode ser usado em um cenário do mundo real, pois os outros não têm um bom desempenho. Confira um exemplo do método na Figura 4 a seguir:

Figura 4 - Merge Sort em Python
Fonte: o autor.

#PraCegoVer: na Figura 4, temos na Linha 1: def merge_sort(lista):; na Linha 2: # Caso base: listas com 1 ou nenhum elemento já estão ordenadas; na Linha 3: if len(lista) <= 1:; na Linha 4: return lista; na Linha 6: # Divide a lista no meio; na Linha 7: meio = len(lista) // 2; na Linha 8: esquerda = merge_sort(lista[:meio]) # Recursivamente ordena a metade esquerda; na Linha 9: direita = merge_sort(lista[meio:]) # Recursivamente ordena a metade direita; na Linha 11: # Combina as metades ordenadas; na Linha 12: return merge(esquerda, direita); na Linha 14: def merge(esquerda, direita):; na Linha 15: resultado = []; na Linha 16: i = j = 0; na Linha 18: # Compara os elementos das duas metades e adiciona ao resultado; na Linha 19: while i < len(esquerda) and j < len(direita):; na Linha 20: if esquerda[i] < direita[j]:; na Linha 21: resultado.append(esquerda[i]); na Linha 22 i += 1; na Linha 23: else:; na Linha 24: resultado.append(direita[j]); na Linha 25: j += 1; na Linha 27: # Adiciona os elementos restantes (se houver) de ambas as listas; na Linha 28: resultado.extend(esquerda[i:]); na Linha 29: resultado.extend(direita[j:]); na Linha 30: return resultado; na Linha 21: # Aplicação; na Linha 33: numeros = [64, 34, 25, 12, 22, 11, 90]; na Linha 34: print("Lista original:", numeros); na Linha 36: ordenada = merge_sort(numeros); na Linha 38: print("Lista ordenada:", ordenada). Nas Linhas 5, 10, 13, 17, 26, 31, 35 e 37 não há conteúdo escrito. Fim da descrição.

Compreender esses algoritmos e suas particularidades é fundamental para que você, futuro técnico em desenvolvimento de sistemas, possa tomar decisões assertivas na escolha da técnica mais adequada para cada cenário específico. Cada método de ordenação possui características únicas em termos de desempenho, complexidade computacional e comportamento em diferentes volumes de dados.

Portanto, ao analisar o contexto de aplicação, como o tamanho do conjunto de dados, a necessidade de escalabilidade e os recursos computacionais disponíveis, é possível selecionar algoritmos que garantam maior eficiência no processamento e melhor aproveitamento de memória e tempo de execução. Esse domínio técnico permite otimizar tarefas críticas em ciência de dados, como a preparação de dados, buscas em grandes bancos de informações, análise de desempenho de sistemas e execução de modelos preditivos, promovendo soluções mais robustas e alinhadas às demandas reais do problema.

Para ilustrar melhor os métodos de ordenação, indico que você assista a um vídeo do YouTube, que apresenta uma visualização de diversos algoritmos, incluindo alguns que vimos nesta lição. Vale a pena conferir!

Clique aqui para acessar o vídeo.

saiba aplicar

A compreensão dos métodos de ordenação é fundamental para você, pois permite a construção de soluções eficientes para organizar e processar dados em diferentes contextos. Em ciência de dados, em que grandes volumes de informações precisam ser analisados rapidamente, dominar algoritmos de ordenação contribui diretamente para a otimização de pipelines analíticos, redução de tempos de processamento e aumento da precisão na tomada de decisões. Essa habilidade lhe capacita enquanto profissional para resolver problemas complexos, possibilitando que você possa projetar sistemas mais robustos e escaláveis, alinhados às demandas do mercado tecnológico atual.

Chegou a sua vez! Neste passo a passo, você implementará os algoritmos de ordenação Bubble Sort, Insertion Sort, Quick Sort e Merge Sort (representados nas Figuras 1, 2, 3 e 4), utilizando o mesmo conjunto de dados. O objetivo é medir o tempo de execução de cada algoritmo e determinar qual é o mais rápido e o mais lento. Para isso, utilizaremos a ferramenta OnlineGDB para programar e executar o código.

Passo 1

Clique aqui para acessar o site indicado.
Escolha a linguagem Python no menu suspenso à direita.

Passo 2

Digite o código da Figura 5 que medirá o tempo de execução do algoritmo de ordenação com o conjunto de dados no editor do OnlineGDB para implementar e comparar os algoritmos de ordenação. Ao implementar os algoritmos das figuras desta lição, lembre-se de digitar somente as funções de ordenação e nada após # Aplicação.

Figura 5 - Aferindo a velocidade dos algoritmos de ordenação em Python
Fonte: o autor.

#PraCegoVer: na Figura 5, temos na Linha 1: import Random; na Linha 2: import time; na Linha 4 # Gerando o conjunto de dados; na Linha 5: tamanho = 10000 # Número de elementos na lista; na Linha 6: dados = [random.randint(1, 1000000) for _ in range(tamanho)]; na Linha 8: # Implemente aqui o algoritmo Bubble Sort disponível na Figura 1 desta lição; na Linha 10: # Implemente aqui o algoritmo Insertion Sort disponível na Figura 2 desta lição; na Linha 12: # Implemente aqui o algoritmo Quick Sort disponível na Figura 3 desta lição; na Linha 14: # Implemente aqui o algoritmo Merge Sort disponível na Figura 4 desta lição; na Linha 16: # Função para medir o tempo de execução de cada algoritmo; na Linha 17: def medir_tempo(funcao, dados):; na Linha 18: copia = dados[:] # Cria uma cópia dos dados para manter o mesmo conjunto para todos; na Linha 19: inicio = time.time(); na Linha 20: funcao(copia); na Linha 21: fim = time.time(); na Linha 22: return fim – inicio; na Linha 24: # Comparação dos algoritmos; na Linha 25: print("Comparando os algoritmos de ordenação com", tamanho, "elementos:"); na Linha 26: tempos = { na linha 27 "Bubble Sort": medir_tempo(bubble_sort, dados); na Linha 28: "Insertion Sort": medir_tempo(insertion_sort, dados); na Linha 29: "Quick Sort": medir_tempo(quick_sort, dados); na Linha 30: "Merge Sort": medir_tempo(merge_sort, dados), na Linha 31: }; na Linha 33: for algoritmo, tempo in tempos.items():; na Linha 34: print(f"{algoritmo}: {tempo:.5f} segundos"); na Linha 36: # Identificando o mais rápido e o mais lento; na Linha 37: mais_rapido = min(tempos, key=tempos.get); na Linha 38: mais_lento = max(tempos, key=tempos.get); na Linha 40: print(f"\nO algoritmo mais rápido foi: {mais_rapido}"); na Linha 41: print(f"O algoritmo mais lento foi: {mais_lento}"). Nas Linhas 3, 7, 9, 11, 13, 15, 23, 32, 35 e 39 não há conteúdo escrito. Fim da descrição.

Passo 3:

Após digitar o código, clique no botão Run no OnlineGDB.
O programa executará os quatro algoritmos de ordenação com o mesmo conjunto de dados, medirá o tempo de execução de cada um e exibirá os resultados.

Passo 4:

Compare os tempos de execução para determinar o desempenho de cada algoritmo.
Observe que algoritmos, como Bubble Sort e Insertion Sort, tendem a ser mais lentos em grandes volumes de dados, enquanto Quick Sort e Merge Sort, geralmente apresentam melhor desempenho.

Esse exercício permite entender o impacto do volume de dados e das características de cada algoritmo no tempo de execução, fornecendo uma base prática para selecionar a melhor técnica de ordenação em cenários reais da ciência de dados. Como desafio adicional, altere o conjunto de dados para outros tipos de dados, discuta com seus colegas e professores.

Bom trabalho!

REFERÊNCIAS

BORIN, V. Estrutura de dados. São Paulo, SP: Contentus, 2020.

GRONER, L. Estrutura de dados e algoritmos em javascript. 2. ed. São Paulo, SP: Novatec, 2019.

ZIVIANI, N. Projeto de algoritmos com implementação em java e c++. São Paulo, SP: Cengage Learning, 2006.

Page updated

Google Sites

Report abuse