Rozważmy następującą metodę sortowania (sortowanie grzebieniowe):...

Rozważmy następującą metodę sortowania (sortowanie grzebieniowe): Niech : n – ilość obiektów w ciągu wejściowym, m=[n/k], dla pewnego k>1.
Porównujemy kolejno wszystkie pary obiektów odległych o m pozycji:
jeśli są ułożone niemonotonicznie – zamieniamy je miejscami.
Powtarzamy to działanie dla m=[m/k], do momentu kiedy m osiągnie wartość 1.
Gdy m spadnie do 1 wykonujemy sortowanie przez zamianę (bąbelkowe) w wariancie z flagą pozwalającą na stwierdzenie, czy w przebiegu nastąpiła choćby jedna zamiana i zakończenie działania w przypadku braku zamian.
Zadanie polega na empirycznym wyznaczeniu optymalnej wartości współczynnika k.
Należy zbadać średni czas działania metody z 10 losowych prób dla tablic o rozmiarze 10000,20000,30000, …, 1000000 i k z przedziału (1.05;2) z krokiem 0.05.

Dodatkowo należy oszacować zależność pomiędzy rozmiarem tablicy, a czasem wykonania tej metody i porównać ją z metodami klasycznymi (przez wstawianie, przez wybór i zamianę).

Proszę o pomoc, totalnie nie wiem jak to ugryźć :/

Rozwiązania (0)