Turbo C metódy triedenia

Triedenie poľa dát je jedným z klasických problémov počítačovej vedy , a tak to by malo prísť ako žiadne prekvapenie , že široká škála metód triedenia v Turbo C a ďalších jazykov boli koncipované . Pohybujú sa od neefektívnych , ale jednoduchý - až k - implementovať metódy oveľa rýchlejší , ale zložitejšie metódy . Najlepší algoritmus pre situáciu , závisí od očakávanej veľkosti súboru dát , ktoré majú byť radené a významu účinnosti . Bubble Sort

Bubble Sort je najjednoduchší a najpomalší , triedenie algoritmus . To jednoducho prebieha cez pole , porovnanie aktuálnej prvok k prvku priamo pred ním . Ak sa tieto dva prvky sú mimo prevádzky , prejdú miesta . Keď Bubble Sort dosiahne konca, skontroluje , či sa niečo zmenilo miesta . Ak áno , začne znovu od začiatku . To pokračuje slučky cez pole , kým sa mu nepodarí dokončiť plnú prihrávku , bez toho, aby nejako vymieňať . V priemere , to trvá O (n ² ) času , ale v prípade , že údaje je známe , že skoro uvedená , s možno iba jedným prvkom z miesta , môže sa pracovať v O ( n) . Takže je to dobrý spôsob pre malé pole , ktoré nie sú väčšinou roztriedené alebo väčšie pole , ktoré je známe, že sa už je zoradený ( alebo skoro tak ) , väčšinu času .
Selection Sort

výber druhu je o niečo jemnejší ako Bubble Sort . Algoritmus pokračuje cez celé pole dát nájsť najmenší prvok . Všade tam , kde tento prvok je , že má svoju pozíciu odložené s prvým prvkom , a čítač konštatuje , že prvý prvok v poli je známe , že je správne zoradené . To potom pokračuje cez celé pole znova , s výnimkou prvého prvku ( ktoré je známe, že je na správne miesto . ) Ak zistí najnižšiu prvok , sa presunie do druhého miesta a zvyšuje čítač pre indikáciu , že prvé dva prvky , je známe, že sa ďalej . Celkovo Selection Sort pracuje v O (n ² ) čas , ale má jednu výhodu : na väčšine , len n-1 zmeny niekedy dôjsť do poľa , pretože každý prvok sa pohybuje iba vtedy , ak je známy jeho pozície . To je dobrý algoritmus v niektorých exotických situáciách , kedy zápis dát do pamäte trvá podstatne dlhšie , ako je čítanie robí .
Quicksort

Ako už názov napovedá , Quicksort je veľmi jednoduché . V priemere , môže to vykonať radenie v O (n log n) času . Ale je to oveľa zložitejšie , než mnoho iných programov , a požaduje , aby developer vedieť niečo o dáta v poli pred rukách . Po prvé , " pivot hodnota " musí byť zvolený . To je hodnota , ktorú developer domnieva , že je blízko k mediánu všetkých hodnôt v poli . Lepšie hodnoty pivot , rýchlejší Quicksort vystúpi . Potom, pole je rozdelené do dvoch skupín : na tie , nad hodnotu otočného sú presunuté na pravú stranu , a tie pod hodnotou čapu sú presunuté na ľavej strane . Dúfajme , že obe strany sú v blízkosti sú rovnakej veľkosti , ale nemusí byť presne rovnaké . A konečne , Quicksort algoritmus začína znova od nuly na každej strane , s novými hodnotami zvolených kontingenčnej , a tieto polovice sú nakoniec rozdelený na štvrtiny . Keď Quicksort je rozdelená na pole , aby každá sekcia má len jednu hodnotu , poľa bola uvedená .

Ako väčšina rekurzívnych algoritmov , to môže byť ťažké si predstaviť , takže sa odporúča , aby vidieť krok za krokom - príklad uvedený v treťom odkazu .

• Predchádzajúca strana: Ako si vyrobiť iPhone App Really Simple 
• Ďalšia strana: Ako vymazať stringstream