26 de dezembro de 2023
Algoritmo: Selection Sort
Algoritmos
Lógica
Selection sort é um algoritmo bem simples para ordenação. Ele consiste em dividir uma lista em duas partes: os que já foram ordenados e os que ainda não foram ordenados. O primeiro passo é percorrer a lista buscando seu menor valor. Ao encontrar esse valor, podemos armazenar seu índex (sua localização) e trocar este valor de lugar com o primeiro item não ordenado da lista. Em seguida, vamos passar do próximo item adiante e repetir esse processo. Simples assim. Façamos isso até o penúltimo item, pois o último naturalmente já será o maior da lista e estará no seu lugar correto - no caso de uma ordenação crescente.
Implementação
Vamos ver a implementação na linguagem C:
1#include <stdio.h>
2#include <stdlib.h>
3#include "utils/swap.h"
4
5int* selection_sort(int numbers[], int length){
6 int min_index, i, j;
7 for (int i = 0; i < length-1; i++) // {1}
8 {
9 min_index = i; // {2}
10 for (int j = min_index; j < length; j++)
11 {
12 if (numbers[min_index] > numbers[j]) { // {3}
13 min_index = j; // {4}
14 }
15 }
16 if (min_index != i) { // {5}
17 swap(&numbers[i], &numbers[min_index]); // {6}
18 }
19 }
20 return numbers;
21};{1}: percorrer todos os elementos da lista até seu penúltimo item;
{2}: definir a posição do menor elemento da lista. Antes de percorrer a lista, este aponta para o primeiro elemento. Entretanto, ao encontrar um valor menor {3}, min_index é atualizado {4}. No final, teremos o menor item da parte não ordenada.
{5}: verificamos se esse valor é diferente de i, ou seja, se foi encontrado algum valor menor que o primeiro elemento. Se encontrou, trocamos a posição desse primeiro elemento da lista pelo menor valor encontrado {6}.
Swap é uma função auxiliar que pega a referência de dois números e os troca de lugar:
1void swap(int *first, int *second) {
2 int temp = *first; // {1}
3 *first = *second;
4 *second = temp;
5}{1}: variável temporária, apenas para segurar a referência enquanto trocamos o valor da variável first.
Tempo de execução
Em seu pior caso, Selection Sort possui um tempo de execução de O(n²).
Referência
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
Algoritmo SELECTION SORT | Algoritmos de Ordenação | Algoritmos #3