Ktoś jest mi w stanie wytłumaczyć sortowanie połówkowe? Dlaczego akurat sortowanie połówkowe? Co to sortowanie ma związane z połówkami, co tam się dzieli na połówki?
0
0
Nie ma takiego sortowania. Jest sortowanie przez scalanie (merge sort). Dzielisz zbiór na pół, sortujesz obie połowy (znów przez scalanie) a następnie je scalasz.
0
Chodzi ci moze o Quicksort (Sortowanie szybkie)?
0
https://pl.wikisource.org/wiki/Sortowanie_przez_wstawianie/kod
i mamy kod zwykłej wersji sortowania przez wstawianie i wersje sortowania przez wstawianie z wyszukiwaniem połówkowym.
1
Sortowanie przez wstawianie polega na dodaniu kolejnego elementu do posortowanego zbioru. Robimy to poprzez przesuwanie wszystkich elementów większych od nowego elementu w prawo:
[1 2 4 7] <-- 3
przesuwamy 4 i 7
[1 2 _ 4 7]
wstawiamy 3 do wolnego miejsca
[1 2 3 4 7]
Wersja z wyszukiwaniem połówkowym (binarnym) wygląda jak jakaś bezużyteczna modyfikacja. Najpierw się wyszukuje miejsce, w które należy nowy element wstawić za pomocą wyszukiwania binarnego, a potem się przesuwa wszystkie elementy większe w prawo, żeby to miejsce zwolnić i się wstawia nowy element w zwolnione miejsce. Czyli na moje oko złożoność nadal taka sama, czas wykonywania się wydłuża, a program jest wiele razy dłuższy i brzydszy.
Chyba że czegoś tutaj nie widzę to niech ktoś mnie poprawi.