Algoritmo de ordenação por seleção

No ultimo post que eu fiz, falei um pouco sobre o Algoritmo de busca binária - Binary Search e sua eficiência em comparação ao algoritmo de busca linear. E dando continuação a série de post sobre algoritmos, hoje vou falar um pouco sobre o algoritmo de Ordenação por seleção - Selection Sort.

ps: esse post foi baseado na minha leitura do livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos, caso queira se aprofundar melhor e entender mais sobre, indico muito a leitura. Algumas imagens também foram retiradas do livros para melhor a ilustrações dos exemplos.

Entendendo a memoria do computador

Antes de mais nada, é preciso entender um pouco sobre o funcionamento da memoria do computador para poder compreender os outros tópicos que eu vou abordar nesse post. Se você já tem um conhecimento sobre o funcionamento da memoria, sintase a vontade para pular esse tópico: Entendo o algoritmo.

Continuando, imagine a memória do computador como se fosse um armário com várias gavetas vazias, prontas para armazenar algum item. Essas gavetas na memória são chamadas de slot.

E cada gaveta pode armazenar apenas um único objeto. Portanto, quando você decide guardar dois itens no armário, você precisa abrir duas gavetas para acomodar esses dois itens na gaveta.

A memória de seu computador funcionar mais ou menos como o exemplo sitado. Quando você precisa salvar algum dado na memória, seu computador libera um slot(espaço na memória) para poder armazenar o dado. É como se fosse um conjunto de várias gavetas, e cada gaveta tem um endereço que você pode acessar e recuperar aquele dado que foi guardado.

Então quando você armazena um item na memória, você esta pedindo ao seu computador um slot na memória para guardar aquele item.

Arrays

Acredito que você já sabe o que são arrays! Se não, basicamente são estruturas de dados que armazenam uma sequência de dados do mesmo tipo tudo em uma sequencia. Nesse tópico vamos ver como os arrays são armazenados na memória do computador, para entender melhor como eles funcionam.

Imagine que você e seus 4 amigos estão indo ao cinema, animados para assistir a um filme juntos. Ao chegarem na bilheteria, vocês querem garantir que todos possam sentar lado a lado, criando uma experiência mais unida. Agora, cada um de vocês é como um elemento em um array, e ao escolher os lugares, você está basicamente organizando esses elementos no array de assentos para que todos fiquem juntos, facilitando a diversão do grupo.

Agora, imagine que um amigo adicional chega de surpresa ao cinema. Vocês, empolgados para tê-lo junto, decidem mudar de lugar para acomodar todos. O problema é que a cadeira ao seu lado já está ocupada por outra pessoa, então, como um time unido, você e seus 4 amigos se levantam e começam a procurar novos lugares. Nessa busca por assentos contíguos, estão basicamente rearranjando-se para garantir que todos fiquem juntos, assim como acontece quando você ajusta os elementos em um array para acomodar novos dados.

Quando você está construindo um app de lista de tarefas, e opta por usar um array para armazenar suas tarefas, é como se estivesse reservando assentos no cinema para cada item da lista. Esses "assentos" (slots de memória) ficam organizados em sequência, facilitando o acesso aos elementos. Agora, quando você adiciona uma nova tarefa, o array segue a lógica do cinema: se não houver um espaço vago ao lado dos assentos já ocupados, ele rearranja os itens para abrir um novo espaço contíguo na memória. Assim, todos os elementos ficam juntos, criando uma sequência organizada e eficiente.

Entendo o algoritmo de ordenação por seleção

O algoritmo de ordenação por seleção, é um algoritmo que organiza os elementos desordenado e organiza em ordem crescente.

Mas como funciona? Imagine o seguinte cenario, onde seu código pegou alguns dados e colocou em um array: [9,4,8,2,5,7,3,6,1]. Agora você quer ordenar esses dados em ordem crescente: [1, 2, 3, 4, 5, 6, 7, 8, 9].

Vaja o código:

listOfNumbers = [9,4,8,2,5,7,3,6,1]

def findSmallerElement(array):
   smaller = array[0]
   smaller_index = 0
   for i in range(1,len(array)):
      if array[i] < smaller:
         smaller = array[i]
         smaller_index = i
   return smaller_index

def selection_sort(array):
   newArray = []
   while(len(array)):
      smaller_index = findSmallerElement(array)
      newArray.append(array.pop(smaller_index))
   return newArray

print(f'Your original array is: {listOfNumbers}') # saida: [9,4,8,2,5,7,3,6,1]
print(f'Your new array is: {selection_sort(listOfNumbers)}') # saida: [1,2,3,4,5,6,7,8,9]

Observe que no código exite uma lista com 9 elementos, tudo organizado aleatoriamente.

listOfNumbers = [9,4,8,2,5,7,3,6,1]

Para, ordenar a lista em ordem crescente, primeiro devemos saber qual é o menor número que está na lista. Para isso, vamos criar uma função que vá buscar o menor número que está no array.

def findSmallerElement(array):
   smaller = array[0]
   smaller_index = 0
   for i in range(1,len(array)):
      if array[i] < smaller:
         smaller = array[i]
         smaller_index = i
   return smaller_index

A função usa o primeiro elemento do array como referência. Se qualquer número for menor que esse primeiro elemento, as variáveis smaller e smaller_index são atualizadas com esse novo número menor. Para fazer isso, usamos um loop for que percorre todo o array, verificando cada elemento em busca do menor número.

Se o elemento atual, representado por array[i], for menor que o número de referência (smaller), as variáveis são atualizadas com esse novo número menor e seu índice. Esse loop continua até percorrer todos os elementos da lista, resultando na função retornando o índice do menor número no final.

Agora, com o menor número encontrado, podemos construir um novo array com os valores em ordem crescente.

def selection_sort(array):
   newArray = []
   while(len(array)):
      smaller_index = findSmallerElement(array)
      newArray.append(array.pop(smaller_index))
   return newArray

a função selection_sort vai receber o array que está com os números desorganizado. Com isso, a função vai entrar em um loop e usar a função findSmallerElement para procurar o menor número do array e o mover para a nova lista newArray. Isso se repete até que a lista original esteja vazia, retornando a lista ordenada.

A função pop no Python remove e retorna o último elemento de uma lista. É como pegar o último biscoito do pacote! Explicação mais detalhada aqui.

Todos os exemplos e imagens foram tirado do livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos. Se gostou ou teve interesse no algoritmos desse post, indico muito a leitura do livro.