Rikiavimo algoritmai

Rikiavimo algoritmai

Įvadas

Rikiavimas, arba kartais dar vadinama rūšiavimu, yra viena

pagrindinių kompiuterio atliekamų operacijų, sakoma, kad

ketvirtadalis viso skaičiavimo laiko kompiuteris skiria

rikiavimui.

Rikiavimu vadiname tai, ką galime sutvarkyti pagal eilę,

remdamiesi skaičių seka arba abėcėle. Pavyzdžiui,

rikiuojame objektus nuo mažiausio iki didžiausio, arba

vardus pagal abėcėlę. Rikiavimas ir paieška neretai yra

sudėtinė kitų algoritmų dalis.

Rikiavimo algoritmai

1. Išrinkimo algoritmas (angl. Selection sort)

2. Greitasis rikiavimas (angl. Quick sort)

3. Burbulo algoritmas (angl. Bubble sort)

4. Įterpimo algoritmas (angl. Insertion sort)

5. Rikiavimas Šelo metodu (angl. Shell sort)

6. Sąlajinis rikiavimas (angl. Merge sort)

7. Išorinis rikiavimas (angl. External sorting)

8. Piramidinis rikiavimas (angl. Heap sort)

Vizualizacija

Internete galima rasti daug vaizdo įrašų apie rikiavimo

metodus. Vienas papuliaresnių – Davido Martino sukurta kai

kurių populiarių rikiavimo algoritmų vizualizacija:

http://www.sorting-algorithms.com

Atverkite nurodytą tinklalapį, peržiūrėkite keletą rikiavimo

metodų. Kas labiausiai patiko? Ką geriausiai įsiminėte?

Išrinkimo (keitimo) algoritmas

Išrinkimo algoritmas yra vienas paprastesnių, tačiau jis

efektyvus tik tada, kai rikiuojamų objektų nėra daug arba kai

objektai beveik surikiuoti, t. y. kai žinoma, jog tik keletas

objektų yra ne savo vietoje. Kitais atvejais šis rikiavimas

užims labai daug laiko. Išrinkimo algoritmas grįstas dviem

etapais: mažiausio elemento išrinkimas ir jo perkėlimas.

Schemoje pavaizduotas mažiausio elemento išrinkimas ir

perkėlimas į sekos pradžią.

Išrinkimo algoritmas (2)

Išrinkimo algoritmas (3)

Kiek kartų atliekami veiksmai?

Norint nustatyti mažiausią objektą iš dviejų, reikia vieną

kartą juodu palyginti. Ieškant lengviausio iš trijų objektų

reikia tuos objektus palyginti du kartus, iš keturių objektų –

reikia juos palyginti tris kartus ir t. t. Rikiuojant aštuonis

objektus ir norint iš jų surasti pirmą lengviausią reikia 7

kartus palyginti visus objektus, šešis kartus – norint surasti

antrą lengviausią objektą ir t. t. Išeina, kad reikia

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 kartus palyginti rikiuojant 8

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!