Binary Insertion Sort ist eine Variante der Insertion Sort, bei der die Einfügeposition mithilfe der binären Suche ermittelt wird. Die zeitliche Komplexität des Algorithmus beträgt O(n2)
Der Algorithmus funktioniert folgendermaßen:
- Eine Schleife beginnt bei Null bis zum Ende der Liste
- In der Schleife wird eine Zahl zum Sortieren ausgewählt, die Zahl wird in einer separaten Variablen gespeichert
- Die binäre Suche sucht nach dem Index, um diese Zahl gegen die Zahlen auf der linken Seite einzufügen
- Sobald der Index gefunden wurde, werden die Zahlen auf der linken Seite beginnend beim Einfügeindex um eine Position nach rechts verschoben. Dabei wird die zu sortierende Nummer gelöscht.
- Die zuvor gespeicherte Nummer wird am Einfügeindex eingefügt
- Am Ende der Schleife wird die gesamte Liste sortiert
Bei einer binären Suche kann es sein, dass die Nummer nicht gefunden wird und der Index nicht zurückgegeben wird. Aufgrund der Besonderheit der binären Suche wird die Zahl gefunden, die der gesuchten Zahl am nächsten kommt. Um den Index zurückzugeben, müssen Sie ihn mit der gesuchten Zahl vergleichen. Wenn die gesuchte Zahl kleiner ist, sollte die gesuchte Zahl bei sein der Index links, und wenn größer oder gleich, dann rechts.
Go-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)
}
Links
Quellen
https://www.geeksforgeeks.org/binary-insertion- sort/
https://www.youtube.com/watch?v=-OVB5pOZJug