Recursão e Quick Sort

Neste post, vou explicar dois conceitos importantes da ciência da computação: recursão e quick sort. Preciso explicar recursão antes de explicar o quick sort, porque o quick sort usa recursão para ordenar o array.

Recursão

Recursão é uma técnica da ciência da computação em que uma função chama a si mesma. Essa técnica é usada para resolver problemas que podem ser divididos em problemas menores do mesmo tipo.

Este é um exemplo de função recursiva que calcula o fatorial de um número:

func factorial(n int) int {
	if n == 0 {
		return 1
	}
	return n * factorial(n-1)
}

Neste exemplo, a função factorial chama a si mesma com um número menor até chegar ao caso base. O caso base é quando n é igual a 0, situação em que a função retorna 1.

É importante reforçar o caso base: sem ele, teríamos um loop infinito, e você pode testar isso com o código abaixo

func factorial(n int) int {
	return n * factorial(n-1)
}

Você pode usar ctrl+c para cancelar.

Quick Sort

Enfim, agora vamos falar do quick sort.

O quick sort é um algoritmo de ordenação que usa recursão para ordenar um array. Ele usa a estratégia de Dividir para Conquistar para ordenar o array. Mas o que seria essa estratégia?

Dividir para Conquistar é uma técnica da ciência da computação em que um problema é dividido em problemas menores do mesmo tipo.

Por exemplo, digamos que temos um array:

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

Primeiro, pegamos o elemento pivô, que é o primeiro elemento do array:

pivot := arr[0]

Com o pivô, dividimos o array em dois: um com os elementos menores que o pivô e outro com os elementos maiores que ele:

var left []int
var right []int

for i := 1; i < len(arr); i++ {
	if arr[i] < pivot {
		left = append(left, arr[i])
	} else {
		right = append(right, arr[i])
	}
}

E aqui usamos recursão para ordenar os arrays da esquerda e da direita:

left = quickSort(left)
right = quickSort(right)

Por fim, concatenamos o array da esquerda, o pivô e o array da direita:

return append(append(left, pivot), right...)

Deixei de propósito para o final para dizer que não podemos esquecer o caso base.

O caso base é quando o array tem só um elemento, situação em que retornamos o próprio array:

if len(arr) < 2 {
	return arr
}

Quando o array tem só um elemento, retornamos o array porque ele já está ordenado.

Agora podemos criar a função quickSort:

func quickSort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}

	pivot := arr[0]

	var left []int
	var right []int

	for i := 1; i < len(arr); i++ {
		if arr[i] < pivot {
			left = append(left, arr[i])
		} else {
			right = append(right, arr[i])
		}
	}

	left = quickSort(left)
	right = quickSort(right)

	return append(append(left, pivot), right...)
}

Agora podemos testar a função:

func main() {
	arr := []int{100, 5, 3, 6, 2, 10}
	fmt.Println(quickSort(arr))
}

Ao rodar o código acima, você vai ver o array ordenado:

[2 3 5 6 10 100]

É isso! Espero que você tenha gostado deste post. Se tiver alguma dúvida, me conte nos comentários abaixo.

Conclusão

Neste post, expliquei dois conceitos importantes da ciência da computação: recursão e quick sort. Espero ter conseguido explicar de forma simples, para que a maioria das pessoas entenda, principalmente quem tem dificuldade ou até medo de algoritmos!

Abraços.