Sortowanie przez wstawianie "ulepszone" - jak zdefiniować?


(Laszjwrz) #1

Witam wszystkich!

Jak zdefiniować algorytm InsertSort+ (ulepszony) w odniesieniu do InsertSort? Czy chodzi o Sortowanie przez proste wstawianie i Sortowanie przez przeszukiwanie i wstawianie połówkowe. Nie znam terminologii. Byłbym wdzięczny gdyby ktoś napisał na czym polega ulepszenie algorytmu Insert+.


(system) #2

Sortowanie przez wstawianie z binarnym wyszukiwaniem czyli sprawdzanie jest metodą dziel i zwyciężaj przez połowienie przedziału. Pozwala to zejść ze złożoności liniowej do logarytmicznej


(Marcin 110) #3

Marcin1199 , to nie ma sensu - nic Ci po tym, że szybko znajdziesz miejsce, w które należy wstawić nowy element, skoro nie możesz go tam wstawić w stałym czasie. Nadal musisz "przepchnąć" o jedną pozycję w prawo wszystkie większe elementy, żeby zwolnić dla niego to miejsce.

Jeśli za operację dominującą przyjmiemy porównanie , to faktycznie złożoność "ulepszonego" algorytmu będzie O(n*log(n)) - nie O(n^2), ale nie oczekuj, że będzie on działał szybciej. Tak naprawdę, operacją dominującą jest zamiana sąsiadujących elementów , którą w obydwu przypadkach (w pesymistycznym wypadku) wykonujesz nawet \frac{n*(n-1)}{2} razy.


([alex]) #4

Tu masz opisaną różnice:

http://chinio.fm.interia.pl/sort/insert/InsertSort.htm