Knyga/Paieška ir Rikiavimas - Versijų istorija

ArturasNik 12:14, 6 rugpjūčio 2025

2025-08-06T12:14:46Z

← Ankstesnė versija		15:14, 6 rugpjūčio 2025 versija
1 eilutė:		1 eilutė:
	{{navigation \|previous=Spausdinimas ir formatavimas \|next=Daugiau apie sąrašus}}		{{navigation \|previous=Spausdinimas ir formatavimas \|next=Daugiau apie sąrašus}}

			=== Ką išmoksi šiame skyriuje? ===
			* Kaip rasti elementą sąraše naudojant tiesinę paiešką
			* Kaip veikia dvejetainė paieška ir kokiose situacijose ji taikoma
			* Kaip skiriasi paieškos algoritmų efektyvumas
			* Kaip veikia įvairūs rikiavimo algoritmai:
			** Įterpimo rikiavimas (Insertion sort)
			** Burbulinis rikiavimas (Bubble sort)
			** Greitasis rikiavimas (Quicksort)
			** Suliejimo rikiavimas (Merge sort)
			* Kada ir kodėl naudoti vieną ar kitą rikiavimo būdą

	Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.		Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.
18 eilutė:		29 eilutė:
	</syntaxhighlight>		</syntaxhighlight>

	Ši funkcija priima masyvą <code>sąrašas</code> ir tikslinę reikšmę <code>ieškomas_žodis</code> ir grąžina tikslinės reikšmės indeksą masyve. Jei tikslinė vertė nerandama masyve, funkcija grąžina -1. Labai ~~praprasta~~ ir aišku.		Ši funkcija priima masyvą <code>sąrašas</code> ir tikslinę reikšmę <code>ieškomas_žodis</code> ir grąžina tikslinės reikšmės indeksą masyve. Jei tikslinė vertė nerandama masyve, funkcija grąžina -1. Labai paprasta ir aišku.

			💡 Tiesinė paieška tinkama neredaguotiems sąrašams arba kai duomenys nėra surikiuoti.

	== Dvejetainė paieška ==		== Dvejetainė paieška ==
69 eilutė:		82 eilutė:
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
	viduriukas = 5 # (5 + 6) // 2		viduriukas = 5 # (5 + 6) // 2
	# sąrašas[5] saugo ~~reikmę~~ 6. Vėl pro šalį. Nustatome naują apatinę reikšmę:		# sąrašas[5] saugo reikšmę 6. Vėl pro šalį. Nustatome naują apatinę reikšmę:
	apačia = 6 # (5 + 1)		apačia = 6 # (5 + 1)
	</syntaxhighlight>		</syntaxhighlight>
79 eilutė:		92 eilutė:

	Atkreipk dėmesį, kad dvejetainės paieškos algoritmas atrado reikšmę per 4 ciklus. Kaip manai, kiek ciklų prireiktų tiesinės paieškos algoritmui? Pasufleruosiu... Daugiau :)		Atkreipk dėmesį, kad dvejetainės paieškos algoritmas atrado reikšmę per 4 ciklus. Kaip manai, kiek ciklų prireiktų tiesinės paieškos algoritmui? Pasufleruosiu... Daugiau :)

			💡 Dvejetainė paieška veikia tik tada, kai sąrašas yra iš anksto surikiuotas.

	= Rikiavimas =		= Rikiavimas =

	Rikiavimo algoritmai naudojami duomenų sąrašui išdėstyti tam tikra tvarka. Rikiavimo algoritmų yra daug ir įvairių, bet papasakosiu tik kelis naudingiausius. Pateiktus algoritmus tu ~~gelėsi~~ nesunkiai pritaikyti ir kitokiems duomenų tipams, ne tik žodžiams. Bet apie tai vėliau.		Rikiavimo algoritmai naudojami duomenų sąrašui išdėstyti tam tikra tvarka. Rikiavimo algoritmų yra daug ir įvairių, bet papasakosiu tik kelis naudingiausius. Pateiktus algoritmus tu galėsi nesunkiai pritaikyti ir kitokiems duomenų tipams, ne tik žodžiams. Bet apie tai vėliau.

	== Įterpimo rikiavimas (Insertion Sort) ==		== Įterpimo rikiavimas (Insertion Sort) ==

			💡 Veiksmingas su mažais ar beveik surikiuotais sąrašais

	Įterpimo rikiavimas yra paprastas rikiavimo algoritmas, kuris veikia padalydamas sąrašą į dvi dalis: surikiuotą ir nesurikiuotą. Tada iteratyviai paimamas elementas iš nerikiuotos dalies ir įterpiamas į reikiamą vietą surikiuotoje dalyje, kol visas sąrašas surikiuojamas.		Įterpimo rikiavimas yra paprastas rikiavimo algoritmas, kuris veikia padalydamas sąrašą į dvi dalis: surikiuotą ir nesurikiuotą. Tada iteratyviai paimamas elementas iš nerikiuotos dalies ir įterpiamas į reikiamą vietą surikiuotoje dalyje, kol visas sąrašas surikiuojamas.
102 eilutė:		119 eilutė:
	Ši funkcija paima sąrašą <code>sąrašas</code> ir sutikiuoja jį didėjimo tvarka, naudodama įterpimo rikiavimą. Ji pradeda iteruoti per sąrašą nuo antrojo elemento (indeksas 1) iki galo. Kiekvieno elemento reikšmė išsaugoma kaip <code>raktas</code>, o jo indeksas - kaip <code>i</code>, tada einama atgal per surikiuotą sąrašo dalį (nuo indekso <code>i-1</code> iki 0) ir ieškoma tinkamos vietos rakto reikšmei įterpti. Tai daroma lyginant rakto vertę su kiekvienu išrikiuotos sąrašo dalies elementu ir perstumiant didesnius elementus viena pozicija į dešinę, kol randama tinkama pozicija. Suradęs tinkamą poziciją, į ją įterpia rakto reikšmę.		Ši funkcija paima sąrašą <code>sąrašas</code> ir sutikiuoja jį didėjimo tvarka, naudodama įterpimo rikiavimą. Ji pradeda iteruoti per sąrašą nuo antrojo elemento (indeksas 1) iki galo. Kiekvieno elemento reikšmė išsaugoma kaip <code>raktas</code>, o jo indeksas - kaip <code>i</code>, tada einama atgal per surikiuotą sąrašo dalį (nuo indekso <code>i-1</code> iki 0) ir ieškoma tinkamos vietos rakto reikšmei įterpti. Tai daroma lyginant rakto vertę su kiekvienu išrikiuotos sąrašo dalies elementu ir perstumiant didesnius elementus viena pozicija į dešinę, kol randama tinkama pozicija. Suradęs tinkamą poziciją, į ją įterpia rakto reikšmę.

	Įterpimo rikiavimo laiko sudėtingumas blogiausiu atveju yra O(n<sup>2</sup>), o tai reiškia, kad didelių įvesties sąrašų atveju jis gali būti lėtas. Tačiau jis turi mažesnes pridėtines išlaidas nei kai kurie kiti ~~rikiavivmo~~ algoritmai ir gali būti efektyvesnis už juos mažiems įvesties sąrašams arba iš dalies surikiuotiems įvesties sąrašams.		Įterpimo rikiavimo laiko sudėtingumas blogiausiu atveju yra O(n<sup>2</sup>), o tai reiškia, kad didelių įvesties sąrašų atveju jis gali būti lėtas. Tačiau jis turi mažesnes pridėtines išlaidas nei kai kurie kiti rikiavimo algoritmai ir gali būti efektyvesnis už juos mažiems įvesties sąrašams arba iš dalies surikiuotiems įvesties sąrašams.

	== Burbulinis rikiavimas (Bubble sort) ==		== Burbulinis rikiavimas (Bubble sort) ==

			💡 Paprastas, bet labai neefektyvus dideliems sąrašams

	Burbulinis rikiavimas - tai paprastas rikiavimo algoritmas, kuris pakartotinai pereina per sąrašą, palygina gretimus elementus ir sukeičia juos vietomis, jei jų eiliškumas netinkamas. Pažiūrėkime į burbulinio rikiavimo funkcijos pavyzdį:		Burbulinis rikiavimas - tai paprastas rikiavimo algoritmas, kuris pakartotinai pereina per sąrašą, palygina gretimus elementus ir sukeičia juos vietomis, jei jų eiliškumas netinkamas. Pažiūrėkime į burbulinio rikiavimo funkcijos pavyzdį:

119 eilutė:		139 eilutė:

	== Greitasis rikiavimas (Quicksort) ==		== Greitasis rikiavimas (Quicksort) ==

			💡 Vienas greičiausių praktikoje, bet ne visada stabilus

	Greitasis rikiavimas yra plačiai naudojamas rikiavimo algoritmas, kuriame taikomas "skaldyk ir valdyk" metodas. Jis veikia iš masyvo (arba sąrašo) išrenkant ašinį elementą ir kitus elementus suskirstant į du papildomus masyvus pagal tai, ar jie mažesni, ar didesni už ašinį elementą. Tada šis procesas rekursiškai kartojamas kiekviename pogrupyje.		Greitasis rikiavimas yra plačiai naudojamas rikiavimo algoritmas, kuriame taikomas "skaldyk ir valdyk" metodas. Jis veikia iš masyvo (arba sąrašo) išrenkant ašinį elementą ir kitus elementus suskirstant į du papildomus masyvus pagal tai, ar jie mažesni, ar didesni už ašinį elementą. Tada šis procesas rekursiškai kartojamas kiekviename pogrupyje.

160 eilutė:		183 eilutė:
	Galutinis rezultatas yra surikiuotas sąrašas, kuris yra grąžinamas iš pradinių sąrašų iškvietimo vietos.		Galutinis rezultatas yra surikiuotas sąrašas, kuris yra grąžinamas iš pradinių sąrašų iškvietimo vietos.

	Pvz. jei iškviečiame funkciją <code>greitasis_rikiavimas([3, 1, 4, 1, 5, 9, 2, 6, 5])</code>, tai ~~gražins~~ <code>[1, 1, 2, 3, 4, 5, 5, 6, 9]</code>, kuris yra pradinis sąrašas surikiuotas didėjimo tvarka.		Pvz. jei iškviečiame funkciją <code>greitasis_rikiavimas([3, 1, 4, 1, 5, 9, 2, 6, 5])</code>, tai grąžins <code>[1, 1, 2, 3, 4, 5, 5, 6, 9]</code>, kuris yra pradinis sąrašas surikiuotas didėjimo tvarka.

	== Suliejimo rikiavimas (Merge sort) ==		== Suliejimo rikiavimas (Merge sort) ==

			💡 Visada greitas (O(n log n)), bet reikalauja daugiau atminties

	Suliejimo rikiavimas - tai rikiavimo algoritmas, kuris veikia pagal dalinimo ir sujungimo principą. Tai efektyvus algoritmas, kuris naudoja rekursiją.		Suliejimo rikiavimas - tai rikiavimo algoritmas, kuris veikia pagal dalinimo ir sujungimo principą. Tai efektyvus algoritmas, kuris naudoja rekursiją.

ArturasNik 11:41, 20 vasario 2025

2025-02-20T11:41:59Z

← Ankstesnė versija		14:41, 20 vasario 2025 versija
1 eilutė:		1 eilutė:
	{{navigation \|next=Daugiau apie sąrašus}}		{{navigation \|previous=Spausdinimas ir formatavimas \|next=Daugiau apie sąrašus}}

	Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.		Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.
228 eilutė:		228 eilutė:
	[1, 1, 2, 3, 4, 5, 5, 6, 9]		[1, 1, 2, 3, 4, 5, 5, 6, 9]

	{{navigation \|next=Daugiau apie sąrašus}}		{{navigation \|previous=Spausdinimas ir formatavimas \|next=Daugiau apie sąrašus}}
	[[Category:Knyga]]		[[Category:Knyga]]

ArturasNik: Naujas puslapis: {{navigation |next=Daugiau apie sąrašus}} Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas. = Paieška = Paieškos algoritmai naudojami norint rasti konkretų elementą sąraše ar duomenų masyve. Yra keletas paieškos algoritmų, tačiau parodysiu du dažniausiai naudojamus - tie...

2024-10-10T10:14:55Z

Naujas puslapis: {{navigation |next=Daugiau apie sąrašus}} Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas. = Paieška = Paieškos algoritmai naudojami norint rasti konkretų elementą sąraše ar duomenų masyve. Yra keletas paieškos algoritmų, tačiau parodysiu du dažniausiai naudojamus - tie...

Naujas puslapis

{{navigation |next=Daugiau apie sąrašus}}

Atlikęs praeito skyriaus uždavinius, jau daug žinai apie sąrašo sukūrimą ir visus bazinius sąrašo metodus. Dabar pasinaudosime įgytomis žiniomis ir susipažinsime su labai dažnai sutinkamais uždaviniais: paieška ir rikiavimas.

= Paieška =

Paieškos algoritmai naudojami norint rasti konkretų elementą sąraše ar duomenų masyve. Yra keletas paieškos algoritmų, tačiau parodysiu du dažniausiai naudojamus - tiesinę paiešką ir dvejetainę paiešką.

== Tiesinė paieška ==
Tiesinė paieška - tai paprastas paieškos algoritmas, kuris, ieškodamas tikslinės reikšmės, peržiūri kiekvieną sąrašo elementą. Pažiūrėk į tiesinės paieškos funkcijos pavyzdį "Python" kalba:

<syntaxhighlight lang="python">
def tiesinė_paieška(sąrašas, ieškomas_žodis):
for i in range(len(sąrašas)):
if sąrašas[i] == ieškomas_žodis:
return i
return -1 # ieškomas_žodis nerastas
</syntaxhighlight>

Ši funkcija priima masyvą <code>sąrašas</code> ir tikslinę reikšmę <code>ieškomas_žodis</code> ir grąžina tikslinės reikšmės indeksą masyve. Jei tikslinė vertė nerandama masyve, funkcija grąžina -1. Labai praprasta ir aišku.

== Dvejetainė paieška ==
Kita vertus, dvejetainė paieška yra efektyvesnis paieškos algoritmas, kuris veikia tik surikiuotose masyvuose (sąrašuose). Jis veikia pakartotinai dalydamas paieškos intervalą per pusę, kol randama tikslinė reikšmė. Painu? Daug aiškiau bus pažiūrėjus šį pavyzdį:

<syntaxhighlight lang="python">
def dvejetainė_paieška(sąrašas, tikslas):
# išsisaugome sąrašo pirmą ir paskutinį indeksą
apačia = 0
viršus = len(sąrašas) - 1

while apačia <= viršus:
# atrandame vidurį pagal formulę: (pradžios indeksas + pabaigos indeksas) padalintas per pusę, be liekanos
viduriukas = (apačia + viršus) // 2
# patikriname, ar `viduriukas` indekse yra mūsų ieškomas tikslas, ir jį atradus grąžiname indeksą.
if sąrašas[viduriukas] == tikslas:
return viduriukas
# jeigu ne, tai pagal tai, kurioje pusėje yra ieškomas elementas pakeičiame viršutinį arba apatinį indeksą
elif sąrašas[viduriukas] < tikslas:
apačia = viduriukas + 1
else:
viršus = viduriukas - 1
# ir kartojame iš naujo, bet jau su nauju, per pus mažesniu rėžiu

return -1 # tikslas nerastas

sąrašas = [1,2,3,4,5,6,7,8,9,10]
print(dvejetainė_paieška(sąrašas, 7)) # 6
</syntaxhighlight>

Panagrinėkim detaliai, kaip vyksta procesas. Ieškome, kur yra skaičius 7, sąraše [1,2,3,4,5,6,7,8,9,10]. Funkcijos pradžios kintamieji:
<syntaxhighlight lang="python">
apačia = 0
viršus = 9 # (ilgis 10 - 1 )
</syntaxhighlight>
Pirmas `while` ciklas:
<syntaxhighlight lang="python">
viduriukas = 4 # (0 + 9) // 2
# sąrašas[4] saugo reikšmę 5. Ne mūsų ieškomas skaičius.
# kadangi tikslas yra surasti 7, tai mūsų kito ciklo metu ieškosime viršutinėje sąrašo dalyje, todėl nusistatome naują apačios reikšmę, viduriukas + 1.
apačia = 5 # (4 + 1)
</syntaxhighlight>
Antras `while` ciklas:
<syntaxhighlight lang="python">
viduriukas = 7 # (5 + 9) // 2
# sąrašas[7] saugo reikšmę 8. Jau arčiau, bet ne dar vis ne mūsų ieškoma reikšmė 7. Nustatome šįkartą naują viršutinę reikšmę, viduriukas - 1
viršus = 6 # (7 - 1)
</syntaxhighlight>
Trečias `while` ciklas:
<syntaxhighlight lang="python">
viduriukas = 5 # (5 + 6) // 2
# sąrašas[5] saugo reikmę 6. Vėl pro šalį. Nustatome naują apatinę reikšmę:
apačia = 6 # (5 + 1)
</syntaxhighlight>
Ketvirtas `while` ciklas:
<syntaxhighlight lang="python">
viduriukas = 6 # (6 + 6) // 2
sąrašas[6] saugo reikšmę 7. Valio! Radom. Grąžinam indeksą 7.
</syntaxhighlight>

Atkreipk dėmesį, kad dvejetainės paieškos algoritmas atrado reikšmę per 4 ciklus. Kaip manai, kiek ciklų prireiktų tiesinės paieškos algoritmui? Pasufleruosiu... Daugiau :)

= Rikiavimas =

Rikiavimo algoritmai naudojami duomenų sąrašui išdėstyti tam tikra tvarka. Rikiavimo algoritmų yra daug ir įvairių, bet papasakosiu tik kelis naudingiausius. Pateiktus algoritmus tu gelėsi nesunkiai pritaikyti ir kitokiems duomenų tipams, ne tik žodžiams. Bet apie tai vėliau.

== Įterpimo rikiavimas (Insertion Sort) ==

Įterpimo rikiavimas yra paprastas rikiavimo algoritmas, kuris veikia padalydamas sąrašą į dvi dalis: surikiuotą ir nesurikiuotą. Tada iteratyviai paimamas elementas iš nerikiuotos dalies ir įterpiamas į reikiamą vietą surikiuotoje dalyje, kol visas sąrašas surikiuojamas.
Pažiūrėkim, kaip tai atrodo:

<syntaxhighlight lang="python">
def įterpimo_rikiavimas(sąrašas):
for i in range(1, len(sąrašas)):
raktas = sąrašas[i]
j = i - 1
while j >= 0 and sąrašas[j] > raktas:
sąrašas[j+1] = sąrašas[j]
j -= 1
sąrašas[j+1] = raktas
</syntaxhighlight>

Ši funkcija paima sąrašą <code>sąrašas</code> ir sutikiuoja jį didėjimo tvarka, naudodama įterpimo rikiavimą. Ji pradeda iteruoti per sąrašą nuo antrojo elemento (indeksas 1) iki galo. Kiekvieno elemento reikšmė išsaugoma kaip <code>raktas</code>, o jo indeksas - kaip <code>i</code>, tada einama atgal per surikiuotą sąrašo dalį (nuo indekso <code>i-1</code> iki 0) ir ieškoma tinkamos vietos rakto reikšmei įterpti. Tai daroma lyginant rakto vertę su kiekvienu išrikiuotos sąrašo dalies elementu ir perstumiant didesnius elementus viena pozicija į dešinę, kol randama tinkama pozicija. Suradęs tinkamą poziciją, į ją įterpia rakto reikšmę.

Įterpimo rikiavimo laiko sudėtingumas blogiausiu atveju yra O(n<sup>2</sup>), o tai reiškia, kad didelių įvesties sąrašų atveju jis gali būti lėtas. Tačiau jis turi mažesnes pridėtines išlaidas nei kai kurie kiti rikiavivmo algoritmai ir gali būti efektyvesnis už juos mažiems įvesties sąrašams arba iš dalies surikiuotiems įvesties sąrašams.

== Burbulinis rikiavimas (Bubble sort) ==
Burbulinis rikiavimas - tai paprastas rikiavimo algoritmas, kuris pakartotinai pereina per sąrašą, palygina gretimus elementus ir sukeičia juos vietomis, jei jų eiliškumas netinkamas. Pažiūrėkime į burbulinio rikiavimo funkcijos pavyzdį:

<syntaxhighlight lang="python">
def burbulinis_rikiavimas(sąrašas):
sąrašo_ilgis = len(sąrašas)

for i in range(sąrašo_ilgis):
for j in range(0, sąrašo_ilgis-i-1):
if sąrašas[j] > sąrašas[j+1]:
sąrašas[j], sąrašas[j+1] = sąrašas[j+1], sąrašas[j]
</syntaxhighlight>
Ši funkcija paima sąrašą <code>sąrašas</code> ir surikiuoja jį didėjančia tvarka, naudodama burbulinį rikiavimą.

== Greitasis rikiavimas (Quicksort) ==
Greitasis rikiavimas yra plačiai naudojamas rikiavimo algoritmas, kuriame taikomas "skaldyk ir valdyk" metodas. Jis veikia iš masyvo (arba sąrašo) išrenkant ašinį elementą ir kitus elementus suskirstant į du papildomus masyvus pagal tai, ar jie mažesni, ar didesni už ašinį elementą. Tada šis procesas rekursiškai kartojamas kiekviename pogrupyje.

Štai greitojo rikiavimo funkcijos pavyzdys "Python" kalba:

<syntaxhighlight lang="python">
def greitasis_rikiavimas(masyvas):
mažiau = []
lygus = []
daugiau = []
if len(masyvas) > 1:
ašis = masyvas[0]
for x in masyvas:
if x < ašis:
mažiau.append(x)
elif x == ašis:
lygus.append(x)
elif x > ašis:
daugiau.append(x)
# neužmiršk grąžinti rezultato!
return greitasis_rikiavimas(mažiau) + lygus + greitasis_rikiavimas(daugiau)
# Atkreipk dėmesį, kad naudojame `lygus`, o ne `ašis`
else:
return masyvas
</syntaxhighlight>

Funkcijos parametras <code>masyvas</code> yra sąrašas, kurį norime surikiuoti.

Pagrindinė funkcijos dalis yra sąlyga <code>if len(masyvas) > 1:</code>, kuri tikrina, ar sąraše yra daugiau nei vienas elementas. Jei sąraše yra tik vienas arba nulis elementų, tai jis jau yra surikiuotas, todėl tiesiog grąžinamas toks pat sąrašas.

Jei sąraše yra daugiau nei vienas elementas, algoritmas tęsiasi. Pirma, parenkamas elementas <code>ašis</code>, šiuo atveju tai yra pirmas sąrašo elementas <code>masyvas[0]</code>. Tuomet algoritmas eina per visus sąrašo elementus ir prideda juos į tris skirtingus sąrašus (<code>mažiau</code>, <code>lygus</code>, <code>daugiau</code>), priklausomai nuo to, kaip jie lyginami su <code>ašis</code>.

* Jei elementas '''x''' yra mažesnis už '''ašis''', jis pridedamas į '''mažiau''' sąrašą.
* Jei elementas '''x''' yra lygus '''ašis''', jis pridedamas į '''lygus''' sąrašą.
* Jei elementas '''x''' yra didesnis už '''ašis''', jis pridedamas į '''daugiau''' sąrašą.

Tai vadinama ''dalijimo procesu''. Po šio proceso turime tris naujus sąrašus: '''mažiau''', '''lygus''' ir '''daugiau''', kurie yra dalinai surikiuoti (mažesni už '''ašis''', lygūs '''ašis''' ir didesni už '''ašis''').

Toliau funkcija naudoja rekursiją ir kviečia save su <code>mažiau</code> ir <code>daugiau</code> sąrašais, taip pritaikydama dalijimo ir surikiavimo procesą šiems dviejams sąrašams atskirai. Rekursyviai kviečiant save, galiausiai bus pasiektas atvejis, kai sąrašai <code>mažiau</code> ir <code>daugiau</code> bus sudaryti iš nulio arba vieno elemento, o tai reiškia, kad jie jau surikiuoti. Tada funkcija grąžina sudėtą sąrašą: <code>greitasis_rikiavimas(mažiau) + lygus + greitasis_rikiavimas(daugiau)</code>, kuris sudarys pilnai surikiuotą sąrašą.

Galutinis rezultatas yra surikiuotas sąrašas, kuris yra grąžinamas iš pradinių sąrašų iškvietimo vietos.

Pvz. jei iškviečiame funkciją <code>greitasis_rikiavimas([3, 1, 4, 1, 5, 9, 2, 6, 5])</code>, tai gražins <code>[1, 1, 2, 3, 4, 5, 5, 6, 9]</code>, kuris yra pradinis sąrašas surikiuotas didėjimo tvarka.

== Suliejimo rikiavimas (Merge sort) ==
Suliejimo rikiavimas - tai rikiavimo algoritmas, kuris veikia pagal dalinimo ir sujungimo principą. Tai efektyvus algoritmas, kuris naudoja rekursiją.

Šis algoritmas veikia taip:
* Jei sąraše yra nulis arba vienas elementas, tai jis jau yra surikiuotas. Grąžinamas tas pats sąrašas.
* Jei sąraše yra daugiau nei vienas elementas, sąrašas yra padalinamas į dvi lygias dalis.
* Kiekviena dalis yra rekursyviai rikiuojama naudojant '''merge sort''' algoritmą.
* Surikiuotos dvi dalys yra sujungiamos į vieną sąrašą. Sujungimo metu elementai yra palyginami ir sudedami į naują sąrašą didėjimo tvarka.

Šis procesas yra pakartojamas tol, kol visi sąrašai yra padalinti iki vieno elemento ir tada sujungti į vieną galutinį surikiuotą sąrašą.

Suliejimo rikiavimo algoritmas yra efektyvus, nes dalijimo ir sujungimo žingsniai yra vykdomi daug kartų, o kiekviename žingsnyje sąrašas yra padalintas į dvi lygias dalis. Tai leidžia efektyviai rikiuoti didelius sąrašus.

<syntaxhighlight lang="python">
def suliejimo_rikiavimas(sąrašas):
# sąraše yra nulis arba vienas elementas
if len(sąrašas) <= 1:
return sąrašas

# Dalinimo žingsnis: padaliname sąrašą į dvi lygias dalis
vidurys = len(sąrašas) // 2
kairė = sąrašas[:vidurys]
dešinė = sąrašas[vidurys:]

# Rekursyviai rikiuojame kiekvieną dalį
kairė = suliejimo_rikiavimas(kairė)
dešinė = suliejimo_rikiavimas(dešinė)

# Sujungimo žingsnis: sujungiame surikiuotas dalis į vieną sąrašą
return suliejimas(kairė, dešinė)

def suliejimas(kairė, dešinė):
rezultatas = []
i = 0 # indeksas kairėje dalyje
j = 0 # indeksas dešinėje dalyje

# Lyginame ir sujungiame elementus
while i < len(kairė) and j < len(dešinė):
if kairė[i] <= dešinė[j]:
rezultatas.append(kairė[i])
i += 1
else:
rezultatas.append(dešinė[j])
j += 1

# Jei viena dalis baigiasi anksčiau, pridedame likusius elementus
while i < len(kairė):
rezultatas.append(kairė[i])
i += 1
while j < len(dešinė):
rezultatas.append(dešinė[j])
j += 1

return rezultatas

# Pavyzdys naudojant suliejimo_rikiavimas funkciją
sąrašas = [3, 1, 4, 1, 5, 9, 2, 6, 5]
surikiuotas_sąrašas = suliejimo_rikiavimas(sąrašas)
print(surikiuotas_sąrašas)
</syntaxhighlight>

Šis pavyzdys naudoja dvi funkcijas: <code>suliejimo_rikiavimas</code> ir <code>suliejimas</code>. <code>suliejimo_rikiavimas</code> funkcija atlieka dalinimo ir rekursyvaus rikiavimo žingsnius, o <code>suliejimas</code> funkcija atlieka surikiuotų dalių sujungimą.

Šio pavyzdžio rezultatas:
[1, 1, 2, 3, 4, 5, 5, 6, 9]

{{navigation |next=Daugiau apie sąrašus}}
[[Category:Knyga]]