Tag Archives: binary insertion sort

A classificação por inserção binária é uma variante da classificação por inserção na qual a posição de inserção é determinada usando pesquisa binária. A complexidade de tempo do algoritmo é O(n²)

O algoritmo funciona assim:

1. Um loop começa de zero até o final da lista
2. No loop, um número é selecionado para classificação, o número é armazenado em uma variável separada
3. A pesquisa binária procura o índice para inserir esse número nos números à esquerda
4. Uma vez encontrado o índice, os números à esquerda são deslocados uma posição para a direita, começando no índice de inserção. No processo, o número que precisa ser classificado será apagado.
5. O número salvo anteriormente é inserido no índice de inserção
6. No final do loop, a lista inteira será classificada

Durante uma pesquisa binária, é possível que o número não seja encontrado e o índice não seja retornado. Devido à peculiaridade da busca binária será encontrado o número mais próximo do buscado, então para retornar o índice será necessário compará-lo com o procurado, se o procurado for menor então o procurado deverá estar em o índice à esquerda e, se for maior ou igual, à direita.

Código Go:

import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Fontes

https://www.geeksforgeeks.org/binary-insertion- ordenar/
https://www.youtube.com/watch?v=-OVB5pOZJug