Ordenação por Seleção — Arrays e Listas

Irei escrever sobre algoritmos e estruturas de dados em paralelo com o livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos de Aditya Y. Bhargava.

Estou usando o livro para aprender sobre algoritmos e estruturas de dados, e escrever sobre o que estou aprendendo, pois acredito que assim eu consiga fixar melhor o conteúdo.

Capítulo 1 — Ordenação por Seleção

Arrays e Listas Encadeadas

Arrays e listas encadeadas são estruturas de dados que armazenam uma coleção de itens. A diferença entre elas é que os arrays são armazenados em blocos de memória contíguos, enquanto as listas encadeadas são armazenadas em blocos de memória não contíguos.

Nesse capítulo do livro, é ensinado a construir um algoritmo de ordenação, pois muitos algoritmos de busca e outros algoritmos dependem de uma lista ordenada para funcionar, como, por exemplo, o algoritmo de pesquisa binária.

Como funciona a memória?

A memória é um conjunto de células de memória, cada uma com um endereço único. Cada célula de memória pode armazenar um byte de informação. Um byte é um conjunto de 8 bits, e cada bit pode ser 0 ou 1.

Eu gosto do exemplo da biblioteca para entender como funciona a memória. Imagine que você está na biblioteca e quer pegar um livro. Você vai até a estante e pega o livro que está na posição 1. Depois você vai até a estante e pega o livro que está na posição 2. E assim por diante. Cada livro tem um número de identificação único, e você pode pegar o livro que você quiser, desde que você saiba o número de identificação dele.

A memória funciona da mesma forma. Cada célula de memória tem um endereço único, e você pode acessar qualquer célula de memória desde que você saiba o endereço dela.

Listas Encadeadas

Uma lista encadeada é uma estrutura de dados que armazena uma coleção de itens. Cada item da lista contém um campo de dados e um campo de referência. O campo de dados armazena o valor do item, e o campo de referência armazena o endereço da próxima célula de memória.

Referência: https://saulo.arisa.com.br/wiki/index.php/Listas_Encadeadas_Simples

Dessa forma, a lista encadeada é armazenada em blocos de memória não contíguos. O primeiro item da lista é armazenado em uma célula de memória, e o campo de referência desse item aponta para o endereço da próxima célula de memória. A próxima célula de memória armazena o segundo item da lista, e o campo de referência desse item aponta para o endereço da próxima célula de memória. E assim por diante.

Você pode acessar qualquer item da lista encadeada desde que você saiba o endereço do item que você quer acessar.

Arrays

Um array é uma estrutura de dados que armazena uma coleção de itens. Cada item do array é armazenado em uma célula de memória, e cada célula de memória tem um endereço único.

Referência: https://www.geeksforgeeks.org/array-data-structure/

Já que cada célula de memória tem um endereço único, você pode acessar qualquer item do array desde que você saiba o endereço do item que você quer acessar.

No entanto, os arrays são armazenados em blocos de memória contíguos. Isso significa que você não pode adicionar um novo item no meio do array, pois você precisaria mover todos os itens depois do item que você quer adicionar para uma nova posição na memória.

Desempenho

O desempenho de um algoritmo é medida em termos de tempo e espaço. O tempo é medido em termos de operações básicas, e o espaço é medido em termos de memória.

Caso você não saiba o que é Notação Big O, eu recomendo que você leia o artigo Introdução a algoritmos — Notação Big O.

O tempo de execução de um algoritmo é medido em termos de operações básicas. Uma operação básica é uma operação que leva o mesmo tempo para ser executada, independentemente do tamanho da entrada.

No caso de um array, a operação básica é a leitura de um item. No caso de uma lista encadeada, a operação básica é a leitura de um item e a leitura do campo de referência. Dessa forma, a operação básica de uma lista encadeada é mais complexa que a operação básica de um array, pois são necessárias duas leituras para acessar um item.

Por outro lado, a operação de adicionar ou remover um item de um array é mais complexa que a operação de adicionar ou remover um item de uma lista encadeada, pois é necessário mover todos os itens depois do item que você quer adicionar ou remover.

Recapitulando

• Arrays e listas encadeadas são estruturas de dados que armazenam uma coleção de itens.
• Os arrays são armazenados em blocos de memória contíguos, enquanto as listas encadeadas são armazenadas em blocos de memória não contíguos.
• Arrays possuem um tamanho fixo, enquanto listas encadeadas não possuem um tamanho fixo.
• Cada célula de memória tem um endereço único, e você pode acessar qualquer célula de memória desde que você saiba o endereço dela.
• A desempenho de um algoritmo é medida em termos de tempo e espaço. O tempo é medido em termos de operações básicas, e o espaço é medido em termos de memória.
• A operação básica de uma lista encadeada é mais complexa que a operação básica de um array, pois são necessárias duas leituras para acessar um item.
• A operação de adicionar ou remover um item de um array é mais complexa que a operação de adicionar ou remover um item de uma lista encadeada, pois é necessário mover todos os itens depois do item que você quer adicionar ou remover.

Finalização

Essa foi uma pequena documentação dos meus estudos, espero que possa ajudar mais pessoas.
Qualquer dúvida, correção ou sugestão pode deixar nos comentários.