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
Zestaw: "Algorytmy sortujące - algorytm Shella"
Algorytm Shella, jest to algorytm, który jest uogólnieniem metody sortowania:
przez wstawianie
przez scalanie
przez zliczanie
kubełkowego
Sortowanie Shella nazywany jest:
metodą malejących przyrostów
metodą stałych przyrostów
metodą rosnących przyrostów
metodą rnieskończonych przyrostów
Algorytm Shella został opisany po raz pierwszy w latach:
50. XX wieku
60. XX wieku
70. XX wieku
80. XX wieku
Algorytm Shella polega na:
wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie
dzieleniu sortowanego zbioru na podzbiory, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h
cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru
dzieleniu sortowanego zbioru na dwa podzbiory, które są niezależnie sortowane
Bardzo ważnym elementem, który wpływa na efektywność sortowania metodą Shella jest:
odpowiednie dobranie ciągu odstępów
zmienna cykliczna
klasa czasowej złożoności obliczeniowej
odpowiednie dobranie wzoru rekurencyjnego
W algorytmie Shella 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.
prawda
fałsz
W praktyce, okazało się, że zaproponowany ciąg odstępów przez Shella jest jednym z najlepszych, ponieważ w kolejnych podzbiorach uczestniczą wielokrotnie te same elementy.
prawda
fałsz
Naukowcem, który opracował wzór na dobór odpowiedniego ciągu odstępów był:
Pierre Bouchard
Donald Knuth
Paulus Moreelse
Rob Box
Klasa złożoności obliczeniowej algorytmu Shella, przy zbiorach nieposortowanych to:
O(n!)
O(n log n)
O(n1,5)
O(n)
W metodzie sortowania Shella:
algorytm jest stabilny, sortowanie odbywa się w miejscu
algorytm jest niestabilny, sortowanie odbywa się w miejscu
algorytm jest niestabilny, sortowanie nie odbywa się w miejscu
algorytm jest stabilny, sortowanie nie odbywa się w miejscu
Algorytm sortowania Shella jest uważany za:
bardzo zły algorytm sortujący w klasie złożoności obliczeniowej O(n2)
bardzo dobry algorytm sortujący w klasie złożoności obliczeniowej O(n2)
średniej klasy algorytm sortujący w klasie złożoności obliczeniowej O(n2)
dobry algorytm sortujący w klasie złożoności obliczeniowej O(n!)
Sortowanie Shella jest bezkonkurencyjne w klasie złożoności obliczeniowej O(n2) algorytmów sortujących przy sortowaniu:
zbiorów nieuporządkowanych i zbiorów posortowanych odwrotnie
zbioru o losowym rozkładzie elementów
zbiorów uporządkowanych
zbiorów częściowo posortowanych
Do sortowania zbiorów w dużym stopniu uporządkowanych, najlepszy jest algorytm:
Shella
przez wstawianie
przez scalanie
Quicksort
Badania wykazały, że lepsza efektywność algorytmu występuje w przypadku, gdy przyrosty nie są swoimi dzielnikami oraz potęgami liczby 2.
prawda
fałsz
O(n2) zapis klasy złożoności obliczeniowej algorytmu oznacza:
algorytm o liniowej zależności czasu wykonania od ilości danych
algorytm, w którym czas wykonania rośnie z kwadratem liczby przetwarzanych elementów
bardzo pesymistyczny algorytm, czas wykonania rośnie szybko wraz ze wzrostem liczby elementów wejściowych
algorytm o rekurencyjnej zależności czasu wykonania od ilości danych




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