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+.
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
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.