Massiv turlari; Massiv o‘lchamlar

2. Sharsimon saralash algoritmi

Massiv elementlarini tepadan pastga qarab saralaymiz. Bunda faqat juft elementlar a_i <= a_i+1 ( i = 0 dan n-1 gacha) shart bilan tekshiriladi, agar shart bajarilmasa ular o‘zaro o‘rin almashtiriladi.

Bu jarayon ohirgi element qolguncha bajariladi. Natijada massiv elementlari o‘sish tartibida saralanadi.

Dasturdagi bosqichlar:


long i, j,

float x, a[];

for( i=0; i < size; i++)

for( j = size-1; j > i; j-- )

{ if ( a[j-1] > a[j] )

{ x=a[j-1]; a[j-1]=a[j]; a[j]=x; } }

Saralashning maqsadi keyinchalik, saralashgan to‘plamni qidirilayotgan elementini topishdan iborat. Bu qariyb universal, fundamental jarayon. Biz bu jarayon bilan har kuni uchrashamiz – telefon daftaridagi saralash, kitoblar sarlavhasida, kutubxonalarda, lugʻatlarda, pochtada va h.k. Hatto yosh bolalar ham o‘z narsalarini tartiblashga o‘rganadi. Saralashning juda ko‘p usullari mavjud. Ular turli to‘plamlar uchun turlicha bo‘lishi mumkin. Massivlarni saralash uchun ishlatiladigan usul unga berilgan xotirani ixcham holda ishlatish lozim. Boshqacha qilib aytganda, saralanayotgan massiv xuddi shu massivni o‘zida amalga oshirilishi lozim. Saralanayotgan a massivni elementlarini kiritib, unda boshqa bir d massivda saralangan holda tashkil topgan bizga hech qanday qiziqish uygʻotmaydi. Biz quyidagi saralash bo‘yicha bir nechta sodda va ma’lum usullarni qaraymiz. Ular to‘gʻri usullar deb aytiladi. Saralash usullari to‘gʻrisida quyidagi fikrlarni bildirish mumkin:

1. To‘gʻri usullar ko‘plab saralashning asosiy tamoyillarining xarakterini ochib berishi uchun qulay.

2. Bu usullarni dasturlar oson tushuniladi va ular qisqa. Eslatib o‘tamiz, dasturning o‘zi ham xotira egallaydi.

3. Murakkab usullar ko‘p sondagi amallarni talab qiladi, lekin bu amallarning o‘zlari yetarlicha murakkab bo‘lganlari uchun, kichik n larda tez va katta n larda sekin ishlaydi. Ammo ularni katta n larda ishlab bo‘lmaydi.

Bitta massivni o‘zida saralashni ularni mos aniqlangan tamoyillari bilan uch kategoriyaga ajratish mumkin:

1. Qo‘shish orqali saralash (by insertion);

2. Ayirish orqali saralash (by selection);

3. Almashish orqali saralash (by exchange).