Logowanie

Ile porównań muszą wykonać dwa rodzaje sortowania?

pytanie zadane 23 listopada 2017 w C i C++ przez antek782 Początkujący (490 p.)

Witam,

Ile porównań musi wykonać każdy z algorytmów sortowania(bąbelkowanie i przez wstawianie) dla 4 elementowego ciągu odwróconego (np. 10,5,3,1) i już posortowanego (np. 1, 3, 5, 10)?

1 odpowiedź

odpowiedź 23 listopada 2017 przez Frendom Pasjonat (18,900 p.)

Poczytaj sobie o tych algorytmach w jaki sposob dzialaja i sprobuj sobie na kartce rozrysowac kazdy przebieg sortowania. Ogolnie jezeli chodzi o sortowanie babelkowe, to przy takim ukladzie zlozonosc wynosi O(n^2), A jezeli chodzi o sortowanie przez wstawianie to w takim ulozeniu chyba wynosi O(n).

komentarz 23 listopada 2017 przez Marcin_N_97 Stary wyjadacz (10,290 p.)

Wszystko tak naprawdę zależy od tego w jaki sposób sortujesz. Polecam poczytać Cormena - Wprowadzenie do algorytmów.

Podobne pytania

–1 głos

2 odpowiedzi 299 wizyt

Ile porównań muszą wykonać dwa rodzaje sortowania?

pytanie zadane 23 listopada 2017 w C i C++ przez antek782 Początkujący (490 p.)

0 głosów

1 odpowiedź 231 wizyt

Sortowanie przez wstawianie, obliczyć czas sortowania

pytanie zadane 13 czerwca 2018 w C i C++ przez Halpi Początkujący (300 p.)

0 głosów

1 odpowiedź 747 wizyt

Modyfikacja sortowania przez wstawianie (malejące)

pytanie zadane 23 listopada 2017 w C i C++ przez antek782 Początkujący (490 p.)

...