Selection Sort

Continuando meus estudos de algoritmos, agora consigo explicar o algoritmo selection sort (ordenação por seleção).

O selection sort é um algoritmo simples. Ele funciona encontrando o menor elemento de um array, adicionando esse elemento a um novo array e removendo-o do array original. Esse processo se repete até o array original ficar vazio. Quando isso acontece, o novo array contém os elementos em ordem.

Neste exemplo, não estou focando em performance, e sim na simplicidade do algoritmo.

Este é o array que vamos usar no exemplo:

arr := []int{100, 5, 3, 6, 2, 10}

No próximo passo, crio a função que recebe esse array e retorna o array ordenado:

func orderIntArray(arr []int) []int {
	var result []int
	var min int

	for len(arr) > 0 {
		min = getSmallerItem(arr)
		result = append(result, arr[min])
		arr = remove(arr, min)
	}

	return result
}

A função getSmallerItem é responsável por obter o índice do menor elemento do array:

func getSmallerItem(arr []int) int {
	var min int = arr[0]
	var pos int

	for i := 1; i < len(arr); i++ {
		if arr[i] < min {
			min = arr[i]
			pos = i
		}
	}
	return pos
}

A função getSmallerItem compara cada elemento do array com a variável min. Se o elemento for menor que min, a variável min é atualizada com o valor do elemento, e a variável pos é atualizada com o índice dele. Quando o loop termina, a variável pos é retornada.

A função remove é responsável por remover o elemento do array:

func remove(s []int, i int) []int {
	s[i] = s[len(s)-1]
	return s[:len(s)-1]
}

A função remove recebe o array e o índice do elemento que será removido.

Agora podemos testar a função:

func main() {
	arr := []int{100, 5, 3, 6, 2, 10}
	result := orderIntArray(arr)
	fmt.Println(result) // return is [2 3 5 6 10 100]
}

Este algoritmo não é eficiente, mas é um bom exemplo para entender o selection sort.

Espero que você tenha gostado deste post, até o próximo!