Usporiadanie čísiel

Zdravím, Chcel by som pomôcť s usporiadaním čísiel.
Zadanie bolo: Program vygeneruje čísla a zapíše ich do pola a vypíše ich od najmenšieho po najväčšieho.
Program:

Na usporiadanie si pozri na nete sorty, je viac druhov ale stačí ti naučiť sa 1-2 viac ani používať nebudeš. Taký základný bubblesort a quicksort. S generovaním do poľa snáď problém nemáš.

Bubbblesort ma ez algoritmus, no pri niekolko-milionovych poliach exponencialne narasta dlzka trvania cyklov. Ak mas cisel pod milion mozes pouzit aj ten.

Ak ich je viac, quicksort je lepsia volba, vacsina pouzivanych programovacich jazykov ho ma definovanu ako fuknciu aby si nemusel pisat cely algoritmus

merge sort ^_^

Myslim ze tu je prave ucelom pisat cely algoritmus, aby student vedel ako funguje

Pokiaľ viem bubble sort ma kvadraticku zložitosť, určite nie exponenciálnu.

Každopádne bubblesort je asi najjednoduchší na pochopenie pre začiatočníka. Určite nezacinaj quicksortom či merge sortom. Keď tak môžeš skúsiť aj Insert sort alebo Select sort, tie sú tiež z tých jednoduchších.

exponent "2" ? n^2 sice si presnejsi ale miso122 to nenapisal zle
inak suhlasim, mitko. Ak ti je ukradnuty processorovy cas a nemas specificky zadane ze musis pouzit jeden z komplexnejsich sortov, zober bubble.

Tak tento argument by na skúške určite neprešiel, aspoň nie u nás na fakulte. A radšej to mať napísane korektne ako by sa tu mal niekto naučiť blbosť ;-).


Nemyslím si že v časoch keď sa učí ako zoradiť náhodne vygenerované čísla ho trápi niečo ako zložitosť.

Technicky spravne je najspravnejsie spravne imo. Neostava nez aby si vyskusal a dal nam vediet
Mozes mat ale pravdu. Kvadraticky si mozno predstavit "n^2" a exponencialne viac ako "2^n", ale nikdy nam to nikto takto nedefinoval.(aspon teda co si pamatam na svk matfyze)

U nas na FI MU sme to tak urcite mali . Dokaz k bubble sortu mozes najst tu uplne dole. Niesom si isty o com sa bavime teraz, ci o tom, aku zlozitost ma bubble sort, alebo o tom, ci sa da n^2 nazvat exponencialnou funkciou.

To druhe teraz. Sorty tak trochu poznam

Takze ty tvrdis ze n^2 rastie rovnako rychlo ako 2^n?

Tymto by sme mohli ukoncit diskusiu k zlozitosti a venovat sa tomu o com je tato tema: https://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost

Urcite by som zacal bubble sort a este by som si po kazdom prejdeni vnoreneho forcyklu nechal vypisat aktualny stav pola, aby bolo pekne vidiet ako ten algoritmus postupuje

Este si odpustim posledne OT.
Bavime sa o tom ze TECHNICKY je kvadraticka funkcia exponencialna. A bud tej lasky a nerob zo mna idiota...

Na margo otazky tohto vlakna diskusie, pouzi princip KISS(Keep it simple, stupid), kym nie je zadane inak, pouzi najjednoduchsie riesenie.

Nie je exponencialna funkcia taka, ktora ma premennu v exponente ? n^2 je len konkretna hodnota pre exponencialnu funkciu so zakladom n v bode x = 2.

Prepac, nechcel som ta urazit, len som ti chcel doplnit znalosti. Idiota zo seba robis sam. Tvrdit ze kvadraticka funkcia je technicky exponencialna je uplny nonsens. Su to predsa dve diametralne rozlicne veci.

// Spojený príspevok Pon 27.03.17 15:20:44



Rozdiel v exponencialnej a kvadraticke funkcii je taky, ze v kvadratickej funkcii je neznama v zaklade a v exponencialnej funkcii je neznama v exponente. Takze nie, kvadraticka funkcia nieje konkretnou hodnotou exponencialnej.

Konkretne hodnoty napr: 10^2 vs 2^10, 11^2 vs 2^11 atd atd.

10^2 môže byť konkrétnou hodnotou kvadratickej, rovnako ako aj exponencialnej funkcie (so základom 10). Keď už chceš chytať za slovíčka...

Skor by som povedal ze sa ani len neobtazujes citat.

no jasne pustite sa do mna. Ja som len reagoval na toto:



Ta veta mi prisla tak, ze magic nerozumie tomu, ze v kvadratickej funkcii je hodnota x v zaklade a v exp je v exponente, tak som mu to chcel dovysvetlit. Nema to s vami cenu, ste tvrdohlavy ako polena, dobre viete ze mam pravdu a budete sa hadat. Clovek chce zabranit tomu, aby si pytajuci myslel, ze sorty trvaju exponencialne dlho a vy sa mu takto odvdacite, hanbite sa.

preco by nemohla byt "n" hodnota respektive zaklad ? Podla mna x^2 nie je zapis exponencialnej funkcie lebo chyba ta hlavna podmienka: premenna v exponente.

No v kvadratickej funkcii nemoze byt n zaklad, pretoze n vyjadruje konstantu, cize v kazdom bode funkcie je n-ko rovnake. V kvadratickej funkci x^2 sa zaklad meni v kazdom bode.

// Spojený príspevok Pon 27.03.17 16:07:54

Jasne ze x^2 nieje zapis exponencialnej funkcie.

Ved prave, kedze vyjadruje konstantu, tak n^2 moze byt konkretna hodnota exponencialnej funkcie v bode 2. Tak isto to moze byt hodnota kvadratickej v bode n. Nevidim problem.

No tak jasne takto to moze byt, ja som ta zle pochopil, myslel som ze myslis ze to nejako vychadza aj v inych bodoch . Okrem toho, toto je uz ina debata a nijak to nesuvisi s tym o com sme sa bavili.

Složitost bych neřešil, Bubble-sort je prostě jedno z nejpomalejších řazení, ale velmi jednoduše se programuje a pokud je občas potřeba seřadit pár položek, úplně stačí. V případě jen částečně seřazeného pole se dokonce může stát že bude rychlejší než ten Quick-sort! No a zatímco Bubble-sort se dá optimalizovat a zrychlit, Quick-sort se dá akorát zvorat...

Pro tenhle případ bych použil spíš Insert-sort, ten se může provádět současně s generováním náhodných čísel do pole.

Ale protože koukání do kódu je trochu nuda, tak ať se také trochu pobavíme:

• Insert-sort
• Bubble-sort
• Select-sort
• Shell-sort
• Merge-sort
• Quick-sort

Ako nehnevaj sa, nechcel som tu reagovat k zlozitosti, ale toto som nepredychal. Rovnaky vztah ako ako n^2 je hodnota exponencialnej funkcie v bode 2 sa da pouzit potom, ze n je hodnota exponencialnej funkcie v bode 1 a 1 je hodnota exponencialnej funkcie v bode 0. Takymto odvodzovanim sa vykona cely sort na jednu instrukciu a je vybavene.
Jednoducho tresla sa blbost, rozpustal sa tu offtopic na stranu, kde sa tu ta blbost obhajuje pricom stacilo napisat, ze sorry pomylil som sa a je vybavene.

Neviem ci rozumies pisanemu textu ale ja som nikde netvrdil nic o zlozitosti sortu. Skus si to este raz precitat. Tak isto som netvrdil, ze zlozitost kvadraticka a exponencialna sa rovnaju.
Nechcel som uz do tejto temy reagovat ale nemam rad, ked mi niekto nieco vklada do ust.

Vy čo sa tu hádáte o základoch teórie zložitosti by ste mali vrátiť titul z informatiky (ak nejaký máte). Každý absolvent akékoľvek univerzity musí vedieť, aký je rozdiel medzi kvadratickou a exponenciálnou zložitosťou, že bubble sort má zložitosť kvadratickú a že názvoslovie je dôležité. Ak kdekoľvek na akademickej pôde poviete, že n^2 je exponenciálna funkcia, zavolajú na vás ochranku.

A keďže pôvodná otázka už bola niekoľko krát zodpovedaná, tak len toľko som chcel