[harnasiek]

#algorytmy #strukturadanych #sortowanie #informatyka #studbaza
Hejka
Czy jest ktoś kto chciałby mi pomóc w zadaniu na studia, bo mam problemy z napisaniem go?
Musze dokładnie opisać algorytmy sortowania, tzn ile jest iteracji, porównań i zamian w każdym przypadku tj. pesymistyczny średni i optymistyczny a kompletnie nie wiem jak się za to zabrać.

[Kolczaneiro]

@harnasiek to wszystko przecież jest w internecie

[harnasiek]

@Kolczaneiro: niestety jak szukam to jest np tylko wytłumaczenie, że optymistyczny bo jest już tablica posortowana a nie ma wyjaśnienia ile wykonuje sie np porownan itp

[Kolczaneiro]

@harnasiek https://eduinf.waw.pl/inf/alg/003_sort/0010.php

[panopel]

@harnasiek:
a) To jest w necie. Serio.
b) Polecam zacząć od ustalenia jaki to ma być algorytm sortowania, bo różne są. Może wtedy łatwiej pójdzie googlowanie.

[harnasiek]

@panopel: ogólnie to ma do opisania z 8 algorytmów i je porównać. Najgorsze jest to, że znam działanie ich ale ciężko mi określić ile będzie zamian itp

[mk321]

@harnasiek: weź wypożycz jakąś książkę do algorytmiki. Szukaj pod złożoność obliczeniowa, jej wyliczanie.

Na studiach wymagają tego, a chyba nigdzie nie tłumaczą jak to liczyć.

[BornToDie69]

@harnasiek: Daj botowi niech ci zrobi

[ZdeformowanyKreciRyj]

@mk321:

nigdzie nie tłumaczą jak to liczyć

Bo nie ma jednej dobrej metody. Wyznaczanie złożoności może być dowolnie trudne. Może być dużo trudniejsze od wymyślenia samego algorytmu i udowodnienia jego poprawności. Są pewne standardowe sposoby, których czasem się używa ale na przykład wymagają więcej matematyki niż przeciętny student drugiego roku informatyki zna.

[mk321]

@ZdeformowanyKreciRyj: no ale wyliczenie podstawowych znanych algorytmów np. sortowania to chyba nie jest jakieś rocket science? Nie można by pokazać "gotowca" jak obliczyć? Lub jak nie ma jednego sposobu, to kilka różnych?

Na żadnej stronie, ani w żadnej książce tego nie widziałem.

Jedynie już gotowe wyliczone.

[Ralox]

@harnasiek: w Cormenie masz całkiem ładnie rozpisane analizy algorytmów, niestety średnią złożoność ma tylko dobrze rozpisany quick sort, ale wątpię żebyś potrzebował czegoś trudniejszego

[ZdeformowanyKreciRyj]

@mk321: a no to analizę zlozonosci sortowania masz chociażby tu https://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Sortowanie:_MergeSort,_HeapSort_i_QuickSort

[Ralox]

@harnasiek: liczba iteracji to będzie złożoność, a liczba porownan i zamian zależy od algorytmu, w quick sorcie zamian powinno byc oczekiwanie dwa razy mniej niż porównań, w bubble sorcie podobnie, w insertion sorcie mniej więcej tyle samo, a w liniowe nie są oparte na porównaniach