8-Mavzu: Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari

Download 42,15 Kb.
bet	2/4
Sana	30.05.2024
Hajmi	42,15 Kb.
	#257330

1 2 3 4

Bog'liq
8-Mavzu

/* low --> boshlangʻich index, high --> yuqori index */ quickSort(arr[], low, high) { if (low

Saralashning umumiy mexanizmi. Quicksort – bu ham ―boʻlib tashla va hukmronlik qil‖ prinsipiga asoslanuvchi algoritmdir.
Eng umumiy koʻrinishida psevdokod algoritmi quyida berilgan. (bu yerda A - saralanadigan massiv, low va high esa, mos ravishda, ushbu massivning saralangan qismining pastki va yuqori chegaralari)
Psevdokod nima? Psevdokod - bu imperativ dasturlash tillarining kalit soʻzlaridan foydalanadigan algoritmlarni tavsiflash uchun ixcham, koʻpincha norasmiy til, ammo algoritmni tushunish uchun zarur boʻlmagan tafsilotlar va oʻziga xos sintaksisni chiqarib tashlaydi.
Algoritmni kompyuterga tarqatish va dasturni keyinchalik bajarish uchun emas, balki odamga taqdim etish uchun moʻljallangan.

Rekursiv QuickSort funksiyasi uchun psevdokod:

/* low --> boshlangʻich index, high --> yuqori index */ quickSort(arr[], low, high)
{
if (low < high)
{
/ * pi - bu qismlarni ajratish koʻrsatkichi, arr [pi] endi kerakli joyda *
/
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Pi oldin quickSort(arr, pi + 1, high); // pi keyin
}
}

“Boʻlib tashlash” algoritmi. ―Boʻlib tashlash‖ni amalga oshirishning koʻplab usullari boʻlishi mumkin, psevdokoddan soʻng quyidagi algoritm qoʻllaniladi. Mantiqan sodda, biz eng chap elementdan boshlaymiz va kichik (yoki teng) elementlarning indeksini i sifatida kuzatamiz. Tekshirish paytida kichik element topsak, joriy elementni arr [i] bilan almashtiramiz. Aks holda biz joriy elementni e‘tiborsiz qoldiramiz.

quickSort(arr[], low, high)
{
if (low < high)

Download 42,15 Kb.

1 2 3 4

Download 42,15 Kb.