Massiv elementlarini saralash algoritmlari, qidiruv algoritmlari

Massiv elementlarini saralash algoritmlari, qidiruv algoritmlari

Saralash - tartiblash (Sorting Algorithms) deb, berilgan obyektlar ketma-ketligini ma’lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash elementlarni keyinchalik foydalanishga qulay holatga keltiradi. Agar bir sonlar massivini o‘sib borish tartibida saralasak, u holda birinchi element har doim eng katta, oxirgi element esa eng kichik bo‘ladi. Misol uchun maktab jurnalida o‘quvchilar familiyasi alifbo tartibiga ko‘ra saralangan bo‘ladi. Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab, ya’ni o‘sib boruvchi qator kabi tartiblaganimizda -50, 0, 8, 23, 100 ko‘rinishiga keladi. Saralash bir necha ko‘rsatkichlarga bog‘liq bo‘lishi ham mumkin. Saralashni amalga oshirishning bir necha usullari ishlab chiqilgan.

Saralash asosan ro‘yxat, massiv elementlari ustida amalga oshiriladi. Masalan sizning guruhingizda 20 ta talaba bor. Ularni familiyasini alifbo tartibida saralashni bilsangiz kerak.
Shu o‘rinda savol tug‘iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o‘zgartirilgan sanasi va o‘lchami. Har birini o‘sish yoki kamayish tartibida saralash mumkin. Agar nomi bo‘yicha saralash lozim bo‘lsa u holda so‘zlar (string - matn) massivi ustida saralash jarayoni amalga oshiriladi. Agarda o‘lchami bo‘yicha saralash lozim bo‘lsa, demak sonlar massivi ustida saralash bajarilishi kerak.


Pufakchali saralash usuli
Pufakchali saralashda har bir element keyingisi bilan taqqoslanadi. Agar ikkita shunday taqqoslanayotga element kerakli tartibda joylashmagan bo‘lsa, ular o‘rin almashadi. Har bir iteratsiyaning yakunida saralash mezoniga bog‘liq ravishda eng katta/ eng kichik element ro‘yxatning oxiriga o‘tadi.
Kod yozishga o‘tishdan oldin, 5 ta sonlardan tashkil topgan massiv elementlarini saralashni vizual misol bilan ko‘rib chiqamiz. Uni o‘sib borish tartibida saralaymiz.

Pufakchali saralash
Birinchi iteratsiya

	Birinchi qadam, massiv boshidagi ikkita sonni taqqoslaymiz. 12 > 5
	Shuning uchun ularning o‘rnini almashtiramiz.
	So‘ngra, ikkinchi va uchinchi o‘rindagi elementlarni taqqoslaymiz: 12 < 48. Demak, bu elementlar o‘z o‘rinlarida qoladi.
	Endi esa, uchinchi va to‘rtinchi o‘rindagi elementlarni taqqoslaymiz: 48 > 0.
	Bu elementlar o‘rin alamashadilar.
	Vanihoyat, to‘rtinchi va beshinchi o‘rindagi elementlar taqqoslanadi: 48 > 4
	Bu elementlar ham o‘rin alamashadilar. Birinchi iteratsiyadan so‘ng massivning eng katta elementi 48 massiv oxiriga o‘tdi.

Ikkinchi iteratsiya

	Birinchi qadam, massiv boshidagi ikkita sonni taqqoslaymiz. 5 < 12. Demak, bu elementlar o‘z o‘rinlarida qoladi.
	So‘ngra, ikkinchi va uchinchi o‘rindagi elementlarni taqqoslaymiz: 12 > 0.
	Shuning uchun ularning o‘rnini almashtiramiz.
	Endi esa, uchinchi va to‘rtinchi o‘rindagi elementlarni taqqoslaymiz: 12 > 4.
	Bu elementlar ham o‘rin alamashadilar. Oldingi iteratsiya yakuniga ko‘ra oxirgi element eng katta element. Shuning uchun to‘rtinchi va beshinchi elementlarni tekshirish shart emas.

Uchinchi iteratsiya

	Birinchi qadam, massiv boshidagi ikkita sonni taqqoslaymiz. 5 > 0.
	Shuning uchun ularning o‘rnini almashtiramiz.
	So‘ngra, ikkinchi va uchinchi o‘rindagi elementlarni taqqoslaymiz: 5 > 4.
	Bu elementlar ham o‘rin alamashadilar.
	Oldingi iteratsiya yakuniga ko‘ra oxirgi ikki element eng katta elementlar. Shuning uchun uchinchi, to‘rtinchi va beshinchi elementlarni tekshirish shart emas.

To‘rtinchi iteratsiya

	Birinchi qadam, massiv boshidagi ikkita sonni taqqoslaymiz. 0 < 4. Demak, bu elementlar o‘z o‘rinlarida qoladi.
	Keyingi elementlarni tekshirish shart emas. Shuning bilan, bizga berilgan sonlar massivi elementlari o‘sib borish tartibida saralandi.

Biz pufakchali saralash uchun dastur yozamiz. Ushbu dasturda biz hosil qiladigan funksiya parametrlari berilgan massivga ko‘rsatkich va uning o‘lchamidir. Elementlar o‘rnini almashtirish uchun swap() standart funksiyasidan foydalanamiz.

#include

using namespace std;

void bubbleSort(int list[], int listLength)

{
while(listLength--)
{
bool swapped = false;
for(int i = 0; i < listLength; i++)
{
if(list[i] > list[i + 1])
{
swap(list[i], list[i + 1]);
swapped = true;
}
}
if(swapped == false)
break;
}
}

int main()

{
int list[5] = {3,19,8,0,48};
cout << "Input array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
bubbleSort(list, 5);
cout << "Sorted array ..." << endl;
for(int i = 0; i < 5; i++)
cout << list[i] << '\t';
cout << endl;
}