Tri par insertion binaire

Le tri par insertion binaire est une variante du tri par insertion dans laquelle la position d’insertion est déterminée à l’aide d’une recherche binaire. La complexité temporelle de l’algorithme est O(n²)

L’algorithme fonctionne comme ceci :

1. Une boucle commence de zéro jusqu’à la fin de la liste
2. Dans la boucle, un nombre est sélectionné pour le tri, le nombre est stocké dans une variable distincte
3. La recherche binaire recherche l’index pour insérer ce numéro par rapport aux chiffres de gauche
4. Une fois l’index trouvé, les nombres de gauche sont décalés d’une position vers la droite, en commençant à l’index d’insertion. Au cours du processus, le numéro à trier sera effacé.
5. Le numéro précédemment enregistré est inséré à l’index d’insertion
6. A la fin de la boucle, toute la liste sera triée

Lors d’une recherche binaire, il est possible que le numéro ne soit pas trouvé et que l’index ne soit pas renvoyé. En raison de la particularité de la recherche binaire, le nombre le plus proche de celui recherché sera trouvé, puis pour renvoyer l’index il faudra le comparer avec celui recherché, si celui recherché est inférieur, alors celui recherché doit être à l’index à gauche, et s’il est supérieur ou égal, alors à droite.

Allez code :

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)
}

Liens

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

Sources

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