Ordenação por Seleção com Arrays e Listas Encadeadas

Adaptado do Livro: Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos

Como funciona a memória

Imagine que você vai a um show e precisa guardar as suas coisas na chapelaria. Algumas gavetas estão disponíveis. Cada gaveta pode guardar um elemento. Você deseja guardar duas coisas, então pede duas gavetas.

É praticamente assim que a memória do computador funciona. O computador se parece com um grande conjunto de gavetas, e cada gaveta tem seu endereço.

feØffeeb é o endereço de um slot na memória.

Cada vez que quer armazenar um item na memória, você pede ao computador um pouco de espaço e ele te dá um endereço no qual você pode armazenar o seu item. Se quiser armazenar múltiplos itens, existem duas maneiras para fazer isso: arrays e listas.

Arrays e listas encadeadas

Algumas vezes, você precisa armazenar uma lista de elementos na memória. Suponha que você esteja escrevendo um aplicativo para gerenciar os seus afazeres. É necessário armazenar os seus afazeres como uma lista na memória.

Você deve usar um array ou uma lista encadeada? Vamos armazenar os afazeres primeiro em um array, pois assim a compreensão fica mais fácil.

Usar um array significa que todas as suas tarefas estão armazenadas contiguamente (uma ao lado da outra) na memória.

Agora, suponha que você queira adicionar mais uma tarefa. No entanto a próxima gaveta está ocupada por coisas de outra pessoa. É como se você estivesse indo ao cinema com os seus amigos e encontrasse um lugar para sentar, mas outro amigo se juntasse a vocês e não houvesse lugar para ele.

Vocês todos precisariam se mover e encontrar um lugar onde todos coubessem. Neste caso, você precisaria solicitar ao computador uma área de memória em que coubessem todas as suas tarefas. Então você as moveria para lá. Se outro amigo aparecesse, vocês ficariam sem lugar novamente — e todos precisariam se mover uma segunda vez! Que incômodo. Da mesma forma, adicionar novos itens a um array será muito lento.

Reservando espaço na memória

Uma maneira fácil de resolver isso é “reservando lugares”: mesmo que você tenha três itens na sua lista de tarefas, você pode solicitar ao computador dez espaços, só por via das dúvidas. Então, você pode adicionar dez itens a sua lista sem precisar mover nada. Isto é uma boa maneira de contornar o problema, mas você precisa ficar atento às desvantagens:

  • Você pode não precisar dos espaços extras que reservou; então a memória será desperdiçada. Você não está utilizando a memória, mas ninguém mais pode usá-la também.
  • Você pode precisar adicionar mais de dez itens a sua lista de tarefas, então você terá de mover seus itens de qualquer maneira.

Embora seja uma boa forma de contornar o problema, não é uma solução perfeita.

Listas encadeadas resolvem este problema de adição de itens.

Listas encadeadas

Com as listas encadeadas, seus itens podem estar em qualquer lugar da memória.

Cada item armazena o endereço do próximo item da lista. Um monte de endereços aleatórios de memória estão ligados.

Endereços de memória ligados.

É como uma caça ao tesouro. Você vai ao primeiro endereço e ele diz “o próximo item pode ser encontrado no endereço 123”. Então vai ao endereço 123 e ele diz “O próximo item pode ser encontrado no endereço 847”, e assim por diante.

Adicionar um item a uma lista encadeada é fácil: você o coloca em qualquer lugar da memória e armazena o endereço do item anterior.

Com as listas encadeadas você nunca precisa mover os seus itens

Digamos que você vá a um cinema famoso com os seus amigos. Vocês seis estão tentando procurar um lugar para sentar-se, mas o cinema está cheio. Não há seis lugares juntos.

Algumas vezes isso acontece com arrays. Imagine que está tentando encontrar 10.000 slots para um array. Sua memória tem 10.000 slots, mas eles não estão juntos. Você não consegue arrumar um lugar para o seu array!

Usar uma lista encadeada seria como dizer “vamos nos dividir e assistir ao filme”. Se existir espaço na memória, você terá espaço para a sua lista encadeada.

Se as listas encadeadas são muito melhores para inserções, para que servem os arrays?

Arrays

Os websites que apresentam listas “top 10” usam uma tática trapaceira para conseguir mais visualizações. Em vez de mostrarem a lista em uma única página, eles colocam um item em cada página e fazem você clicar em “próximo” para ler o item seguinte. Esta técnica fornece aos sites dez páginas inteiras para incluir anúncios, mas fica chato ficar clicando em “próximo” nove vezes até chegar ao número 1. Seria muito melhor se a lista estivesse em uma única página e você pudesse clicar no nome de cada vilão para saber mais.

Listas encadeadas têm um problema similar. Suponha que você queira ler o último item de uma lista encadeada. Você não pode fazer isso porque não sabe o endereço dele. Em vez disso, precisa ir ao item #1 para pegar o endereço do item #2. Então, é necessário ir ao item #2 para encontrar o endereço do item #3, e assim por diante, até conseguir o endereço do último item. Listas encadeadas são ótimas se você quiser ler todos os itens, um de cada vez: você pode ler um item, seguir para o endereço do próximo item e fazer isso até o fim da lista. Mas se você quiser pular de um item para outro, as listas encadeadas são terríveis.

Com arrays sabemos o endereço de cada item

Com arrays é diferente. Você sabe o endereço de cada item. Por exemplo, suponha que o array tenha cinco itens e que você saiba que o primeiro está no endereço 00. Qual é o endereço do item #5? A matemática lhe dá a resposta: está no endereço de posição 04.

Arrays são ótimos se você deseja ler elementos aleatórios, pois pode encontrar qualquer elemento instantaneamente em um array. Na lista encadeada, os elementos não estão próximos uns dos outros, então você não pode calcular instantaneamente a posição de um elemento na memória.

Terminologia

Os elementos em um array são numerados. Essa numeração começa no 0, não no 1. Começar no 0 simplifica todos os tipos de array na programação, logo, os programadores não podem fugir disso. Quase todas as linguagens de programação começarão os arrays numerando o primeiro elemento como 0. Logo você se acostuma!

A posição de um elemento é chamada de índice. Portanto, em vez de dizer “o número 2 está na posição 1”, a terminologia correta seria dizer “o número 2 está no índice 1”.

Aqui está o tempo de execução para operações comuns de arrays e listas.

Tempo de execução de arrays e listas

Inserindo algo no meio da lista

Imagine que você queira a que a lista de tarefas se pareça mais com um calendário. Antes, você adicionava os itens ao final da lista. Agora, quer adicionar suas tarefas na ordem em que elas devem ser realizadas.

Lista desordenada

O que seria melhor se você quisesse inserir elementos no meio de uma lista: arrays ou listas encadeadas?

  • Usando listas encadeadas, basta mudar o endereço para o qual o elemento anterior está apontando.
  • Já para arrays, você deve mover todos os itens que estão abaixo do endereço de inserção.

Se não houver espaço, pode ser necessário mover tudo para um novo local. Por isso, listas encadeadas são melhores caso queira inserir um elemento no meio de uma lista.

Deleções de elementos

E se quiser deletar um elemento? Novamente, é mais fácil fazer isso usando listas encadeadas, pois é necessário mudar apenas o endereço para o qual o elemento anterior está apontando. Com arrays, tudo precisa ser movido quando um elemento é eliminado.

Ao contrário do que ocorre com as inserções, a eliminação de elementos sempre funcionará. A inserção poderá falhar quando não houver espaço suficiente na memória.

O que é mais usado: arrays ou listas?

Isso depende do caso em que se aplicam. Entretanto os arrays são mais comuns porque permitem acesso aleatório. Existem dois tipos de acesso: o aleatório e o sequencial.

Acesso sequencial (Listas encadeadas)

O acesso sequencial significa ler os elementos, um por um, começando pelo primeiro. Listas encadeadas só podem lidar com acesso sequencial. Se você quiser ler o décimo elemento de uma lista encadeada, primeiro precisará ler os nove elementos anteriores para chegar ao endereço do décimo elemento.

Acesso aleatório (Arrays)

O acesso aleatório permite que você pule direto para o décimo elemento. Muitos casos requerem o acesso aleatório, o que faz os arrays serem mais utilizados. Arrays e listas são usados para implementar outras estruturas de dados.

Ordenação por seleção

Suponha que você tenha um monte de músicas no seu computador. Para cada artista, você tem um contador de plays. Você quer ordenar uma lista de artistas, do artista mais tocado para o menos tocado, para que possa categorizar os seus artistas favoritos. Como fazer isso? Uma maneira seria pegar o artista mais tocado da lista de músicas e adicioná-lo a uma nova lista e ir fazendo isso de novo para encontrar o próximo artista mais tocado até terminar a lista ordenada.

Recapitulando

- A memória do computador é como um conjunto gigante de gavetas.

- Quando se quer armazenar múltiplos elementos, usa-se um array ou uma lista.

- No array, todos os elementos são armazenados um ao lado do outro.

- Na lista, os elementos estão espalhados e um elemento armazena o endereço do próximo elemento.

- Arrays permitem leituras rápidas.

- Listas encadeadas permitem rápidas inserções e eliminações.

Todos os elementos de um array devem ser do mesmo tipo (todos ints, todos doubles, e assim por diante).

Obrigado.

Composing a repository of books (i bought), authors (i follow) & blogs (direct ones) for my own understanding.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store