Algoritmas

Algoritmų palyginimas

Paprastai yra daugiau nei vienas problemos sprendimo būdas. Gali būti daug skirtingų receptų, kaip pagaminti tam tikrą patiekalą, kuris atrodo skirtingai, bet galiausiai jo skonis yra toks pat. Tas pats pasakytina ir apie algoritmus. Tačiau kai kurie iš šių būdų bus geresni už kitus. Jei receptui reikia daug sudėtingų ingredientų, kurių neturite, jis nėra toks geras kaip paprastas receptas. Kai į algoritmus žiūrime kaip į problemų sprendimo būdą, dažnai norime sužinoti, kiek laiko kompiuteriui prireiktų išspręsti problemą taikant tam tikrą algoritmą. Kai rašome algoritmus, norime, kad mūsų algoritmas užimtų kuo mažiau laiko, kad galėtume kuo greičiau išspręsti problemą.

Gaminant maistą, kai kuriuos receptus atlikti sunkiau nei kitus, nes jiems užbaigti reikia daugiau laiko arba reikia daugiau dalykų, kuriuos reikia stebėti. Taip pat yra ir su algoritmais, o algoritmai yra geresni, kai juos lengviau atlikti kompiuteriui. Dalykas, kuriuo matuojamas algoritmo sudėtingumas, vadinamas sudėtingumu. Kai klausiame, koks sudėtingas yra algoritmas, dažnai norime sužinoti, kiek laiko užtruks kompiuteriui išspręsti uždavinį, kurį norime, kad jis išspręstų.

Rūšiavimas

Tai algoritmo, skirto kortelėms su spalvomis rūšiuoti į tos pačios spalvos krūveles, pavyzdys:

1. Pasiimkite visas kortas.
2. Išsirinkite kortelę iš rankų ir pažvelkite į jos spalvą.
3. Jei jau yra tos spalvos kortų krūvelė, padėkite šią kortą ant tos krūvelės.
4. Jei nėra šios spalvos kortų krūvelės, sukurkite naują šios spalvos kortų krūvelę.
5. Jei rankoje vis dar yra kortelė, grįžkite prie antrojo žingsnio.
6. Jei rankoje vis dar nėra kortų, kortos surūšiuojamos. Jūs baigėte.

Rūšiavimas pagal numerius

Tai algoritmų, skirtų kortelių su daugybe skirtingų skaičių krūvai rūšiuoti taip, kad skaičiai būtų išdėstyti eilės tvarka, pavyzdžiai.

Pradžioje žaidėjai turi nesurūšiuotų kortų krūvą.

Pirmasis algoritmas

Šis algoritmas eina per kortelių krūvą po vieną kortelę. Ši korta lyginama su kita korta krūvoje. Atkreipkite dėmesį, kad ši pozicija keičiasi tik 6 žingsnyje. Šis algoritmas vadinamas burbuliniu rūšiavimu. Jis yra lėtas.

1. Jei kortų krūvelė tuščia arba joje yra tik viena korta, ji surūšiuota ir baigta.
2. Paimkite kortų krūvą. Pažvelkite į pirmąją (viršutinę) krūvelės kortelę.
3. Kortelė, į kurią žiūrite, yra kortelė A. Šiuo metu kortelė A yra P krūvelėje.
4. Jei po A kortelės krūvelėje daugiau kortelių nėra, pereikite prie 8 veiksmo.
5. Kita kortelė krūvelėje yra B kortelė.
6. Jei kortelėje B yra mažesnis skaičius nei kortelėje A, sukeiskite kortelių A ir B pozicijas vietomis. Kai sukeičiate kortas vietomis, nekeiskite pozicijos P.
7. Jei po P pozicijos krūvelėje yra dar viena kortelė, pažvelkite į ją; grįžkite prie 3 veiksmo.
8. Jei per paskutinį ėjimą nepakeitėte nė vienos kortos padėties, baigėte; kortų krūva surūšiuota.
9. Priešingu atveju grįžkite prie 2 veiksmo.

Žingsnis po žingsnio pavyzdys

Paimkime kortelių su skaičiais "5 1 4 2 8" krūvą ir surūšiuokime ją nuo mažiausio skaičiaus iki didžiausio naudodami šį algoritmą. Kiekviename žingsnyje algoritmas lygina elementus, užrašytus paryškintu šriftu. Kortelių krūvos viršus yra kairėje pusėje.

Pirmas perdavimas:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 5 4 2 8 ) Čia algoritmas palygina pirmuosius du elementus ir juos sukeičia vietomis.
( 1 5 4 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 2 5 8 ) Šie elementai jau yra išdėstyti eilės tvarka, todėl algoritmas jų nekeičia.
Antrasis ėjimas:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )(
1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 4 5 8 )
Dabar kortų krūva jau
 yra surūšiuota, bet mūsų algoritmas to nežino. Algoritmui reikia viso vieno perėjimo be jokio apsikeitimo, kad sužinotų, jog ji surūšiuota.
Trečias ėjimas:
( 1 2 4 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 4 5 8 )
Galiausiai masyvas surūšiuotas ir algoritmas gali būti sustabdytas.

Istorija

Tai lengvai suprantamas rūšiavimo algoritmas. Kompiuterių mokslininkai jį pavadino Bubble sort (burbulinis rūšiavimas), nes mažesni elementai pakyla į viršų, keisdami savo padėtį kiekvienoje eilutėje. Deja, šis algoritmas nėra labai geras, nes jam surūšiuoti reikia daug laiko (daug perėjimų per kortelių krūvą).

Antrasis algoritmas

Šis algoritmas naudoja kitą idėją. Kartais uždavinį išspręsti sunku, tačiau uždavinį galima pakeisti taip, kad jis būtų sudarytas iš paprastesnių uždavinių, kuriuos lengviau išspręsti. Tai vadinama rekursija. Jį suprasti sunkiau nei pirmąjį pavyzdį, tačiau jis leis sukurti geresnį algoritmą.

Pagrindinė idėja

1. Jei krūvelėje nėra kortelių arba yra tik viena kortelė, ji surūšiuota ir baigta.
2. Padalykite kortų krūvelę į dvi maždaug vienodo dydžio dalis. Jei kortų skaičius nelyginis, vienoje iš dviejų krūvelių bus viena korta daugiau nei kitoje.
3. Surūšiuokite kiekvieną iš dviejų krūvų pagal šį algoritmą (Kiekvieną krūvą pradėkite nuo 1 šio sąrašo elemento).
4. Sujunkite abi surūšiuotas krūvas, kaip aprašyta toliau.
5. Rezultatas - surūšiuota kortelių krūva. Baigta.

Dviejų stekų sujungimas

Tai veikia su dviem kortų krūvelėmis. Viena iš jų vadinama A, kita - B. Pradžioje yra trečia tuščia krūvelė, vadinama C. Pabaigoje joje bus rezultatas.

1. Jei A arba B krūvelė yra tuščia, visas ne tuščios krūvelės korteles padėkite ant C krūvelės viršaus; viskas baigta, C krūvelė yra sujungimo rezultatas. (Pastaba: paimkite visą krūvelę ir uždėkite ją ant C krūvelės; jei tai darysite kortelę po kortelės, tvarka pasikeis ir neveiks taip, kaip turėtų veikti.)
2. Pažvelkite į viršutines A ir B krūvelių korteles. Kortelę su mažesniu skaičiumi padėkite ant C krūvelės viršaus. Jei C krūvelėje nebuvo kortelių, dabar joje bus viena kortelė.
3. Jei A arba B krūvelėje liko kortelių, grįžkite prie 1 veiksmo ir jas surūšiuokite.

Istorija

Johnas von Neumannas šį algoritmą sukūrė 1945 m. Jis pavadino jį ne rūšiavimu pagal skaičius, o "Mergesort". Tai labai geras rūšiavimo algoritmas, palyginti su kitais.

Trečiasis algoritmas

Pirmuoju algoritmu korteles surūšiuoti užtrunka daug ilgiau nei antruoju, tačiau jį galima patobulinti (pagerinti). Žvelgiant į burbulinį rūšiavimą, galima pastebėti, kad kortos su dideliais skaičiais iš krūvos viršaus juda gana greitai, tačiau kortos su mažais skaičiais, esančios krūvos apačioje, ilgai kyla (juda į viršų). Norint patobulinti pirmąjį algoritmą, štai idėja:

Vietoj to, kad būtų lyginamos dvi viena šalia kitos esančios kortos, pradžioje pasirenkama "speciali" korta. Visos kitos kortos lyginamos su šia korta.

1. Pradedame nuo krūvos A. Bus dar dvi krūvos B ir C, kurios bus sukurtos vėliau.
2. Jei A krūvelėje nėra kortelių arba yra tik viena kortelė, rūšiavimas baigtas.
3. Iš A krūvelės atsitiktine tvarka pasirenkama kortelė, jei įmanoma. Tai vadinama apsisukimu.
4. Visos likusios A krūvelės kortos lyginamos su šia ašimi. Kortos su mažesniu skaičiumi keliauja į B krūvelę, o su tokiu pat arba didesniu skaičiumi - į C krūvelę.
5. Jei B arba C krūvelėse yra kortelių, šias krūveles reikia surūšiuoti pagal tą patį algoritmą (Pradėkite nuo 1 pozicijos šiame sąraše tiek B, tiek C krūvelėje iš eilės).
6. Atlikta. Išrūšiuotoje kortų krūvoje pirmiausia yra išrūšiuota B krūva, po to - ašis, o tada - išrūšiuota C krūva.

Istorija

Šį algoritmą 1960 m. sukūrė C. A. R. Hoare'as. Šiandien tai vienas plačiausiai naudojamų rūšiavimo algoritmų. Jis vadinamas Quicksort.

Animacija, rodanti, kaip veikia burbulų rūšiavimas


7 skaičių rūšiavimas naudojant antrąjį rūšiavimo pagal skaičius algoritmą (Mergesort)


Trečiasis kortelių rūšiavimo algoritmas. Elementas su raudona juosta pasirenkamas kaip ašis. Pradžioje tai yra elementas, esantis į dešinę. Šis algoritmas vadinamas Quicksort.

Algoritmų sudarymas

Jei žaidėjai turi kortelių su spalvomis ir skaičiais, jie gali jas surūšiuoti pagal spalvas ir skaičius, jei atliks "rūšiavimo pagal spalvas" algoritmą, tada kiekvienai spalvotai krūvelei taikys "rūšiavimo pagal skaičius" algoritmą ir sudės krūveles kartu.

Rūšiavimo pagal skaičius algoritmus atlikti sunkiau nei rūšiavimo pagal spalvas algoritmą, nes gali tekti daug kartų kartoti veiksmus. Galima sakyti, kad rūšiavimas pagal skaičius yra sudėtingesnis.

Susiję puslapiai

• Euklido algoritmas buvo atrastas daugiau nei prieš 2000 metų. Juo galima rasti dviejų skaičių didžiausią bendrąjį daliklį.