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"

Dobór optymalnych odstępów

Zwiększenie efektywności algorytmu Shella w stosunku do zwykłego sortowania przez wstawianie - algorytm porządkowania przez wstawianie jest efektywny dla częściowo uporządkowanych zbiorów. Sortując małe podzbiory, częściowo porządkujemy dany zbiór, tak że w ostatnim kroku jest on już częściowo prawidłowo poukładany. Tak więc liczba zamian jest stosunkowo mała. Wpływ na efektywność w metodzie malejących przyrostów ma także wartość samego przyrostu. Badania wykazały, że lepsza efektywność algorytmu występuje w przypadku, gdy przyrosty nie są swoimi dzielnikami oraz potęgami liczby 2.

Bardzo ważnym elementem, który wpływa na efektywność sortowania metodą Shella jest odpowiednie dobranie ciągu odstępów.

Pierwotnie Shell proponował pierwszy odstęp równy połowie liczby elementów w sortowanym zbiorze, kolejne odstępy otrzymuje się dzieląc odstęp przez 2.
W praktyce, okazało się, że zaproponowany ciąg odstępów przez Shella jest jednym z najgorszych, ponieważ w kolejnych podzbiorach uczestniczą wielokrotnie te same elementy.

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