Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Aktualna kategoria: Nauka » Informatyka » Liceum - lekcje

12345678910111213141516171819
Lekcja: "Algorytmy sortujące - algorytm Shella"

Wiadomości ogólne


Kiedy odstęp h będzie równy 1, sortujemy za pomocą sortowania przez wstawianie (Instertion Sort). Jednakże z uwagi na wcześniejsze obiegi sortujące mamy ułatwione zadanie, ponieważ zbiór został w dużym stopniu uporządkowany.

Dzięki początkowym dużym odstępom elementy były przesuwane w zbiorze bardziej efektywnie - na duże odległości. W wyniku otrzymujemy najlepszy pod względem szybkości czasu wykonania algorytm sortujący w klasie O(n2). Algorytm ten nosi również nazwę algorytmu sortowania przez wstawianie z malejącym odstępem (ang. Diminishing Increment Sort).

Efektywność algorytmu sortowania metodą Shella zależy w dużym stopniu od ciągu przyjętych odstępów. Pierwotnie Shell proponował pierwszy odstęp równy połowie liczby elementów w sortowanym zbiorze. Kolejne odstępy otrzymujemy dzieląc odstęp przez 2 (dzielenie całkowitoliczbowe).

<< Poprzednia plansza   Następna plansza >>
Pobierz lekcję

Udostępnij link do tej lekcji innym uczniom:




Zgłoś uwagę do lekcji:




Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie