Reja Algoritmlar va ularning to’liq tuzulishining bosqichlari

TARTIBLASH ALGORITMLARI. XOARA USULI


Tartiblash masalalarining turlari

Umuman tartiblash deganda berilgan ob’yektlar to’plamini ma’lum tartibda joylash uchun qayta ishlash jarayoni tushuniladi.

Tartiblash natijasida to’plamdagi elementlarni izlash jarayonlari yengillashadi. Undan tashqari tartiblashlar misolida qanday qilib algoritmni murakkablash evaziga samaradorlikni oshirishga erishish mumkinligini ko’rsatsa bo’ladi.
Hozirgi kunda ko’pgina tartiblash algoritmlari mavjud. Algoritmni tanlash qayta ishlanayotgan ma’lumotlar strukturasiga bog’liq va shu sababli tartiblash usullari asosan 2 sinfga ajratiladi. Bular massivlarni tartiblash va fayllarni tartiblash. Ularni yana ichki va tashqi tartiblash ham deb nomlaydilar.Chunki massivlar mashinaning tezkor xotirasida joylashadi. Fayllar esa odatda ancha hajmi katta bo’lgan lekin sekin ishlaydigan tashqi xotiradan olinadilar.
Xoaraning tartiblash algoritmi mazmuni

Eng yahshi tartiblash algoritmlaridan biri deb Ch. Xoara usuli hisoblanadi. Bu usul almashuvga asoslangan.

Bu yerda yahshi samaradorlikka erishish uchun dastlab katta masofadagi ya’ni bir-biriga eng uzoq joylashgan elementlarni almashtirish qo’llaniladi. Faraz qilaylik bizda n ta element kalitlar bo’yicha qayta tartibda berilgan. Xoara usuli bo’yicha ularni ta almashuv bilan tartiblash mumkin. Buning uchun dastlab eng chap va eng o’ng tomonda joylashgan elementlarni almashtiramiz. Keyin ikki tomondan o’rtaga qarab kelamiz. Lekin bu faqatgina qayta tartib aniq bo’lganda amalga oshiriladi.
Endi massiv ixtiyoriy tartibda berilgan bo’lsin. Ixtiyoriy X elementni tanlab massivni chapdan o’ngga qandaydir a_i>x element uchramaguncha ko’rib chiqamiz. Keyin massivni o’ngdan chapga qandaydir a_jelement uchramaguncha o’tamiz.
a_i va a_j elementlarni o’rinlarini almashtirib massivni ikki tomondan ko’rib chiqish jarayonini massiv o’rtasiga kelmaguncha davom ettiramiz. Natijada massiv 2 qismga bo’linadi. Chap qismdagi elementlar x dan katta yoki teng bo’ladilar. O’ng tomondagi elementlar x dan kichik yoki teng bo’ladi.
Dastur tuzayotganda bu jarayonni prosedura yordamida amalga oshirish mumkin. Prosedurani rekursiv va norekursiv usullar bilan tuzish mumkin.