Fizika-matematika fakulteti algoritm fanidan

1.2. MA'LUMOTLARNI SARALASH USULLARI

1. Tuzilma elementlarini saralash

Ma'lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda ma'lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma'lumotlarni kalitlari bo'yicha doimiy ko'rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma'lumotlarni massivda kalitlari bo'yicha o'sishi tartibida berilishi tushuniladi.

Ma'lumotlarga qayta ishlov berilayotganda ma'lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.

Saralashning ikkita turi mavjud: ichki va tashqi:

• 
  ichki saralash bu operativ xotiradagi saralash;
  
• 
  tashqi saralash – tashqi xotirada saralash.
  

Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma'nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma'lumot ko'rsatkichlari almashtirilib, massiv o'z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi.

Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang'ich tartibda qanday joylashgan bo'lsa, shu tartibda qoldirilishi maqsadga muvofiq bo'ladi (Bir xil kalitlilar o'zlariga nisbatan). Bunday usulga turg'un saralash deyiladi.

Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`ycha.

Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):

Sonlar berilishi: 23, 54, 3, 22, 1, 45;

Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turipti)

Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)

Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)

Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)

Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ldi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralshdan 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. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Ular:

1. 
   Bubble sort
   
2. 
   Selection sort
   
3. 
   Insertion sort
   
4. 
   Quick sort
   
5. 
   Merge sort
   

Saralash samaradorligini bir necha mezonlar bo'yicha baholash mumkin:

• 
  saralashga ketgan vaqt;
  
• 
  saralash uchun talab qilingan operativ xotira;
  
• 
  dasturni ishlab chiqishga ketgan vaqt.
  

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin.

Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo'lsa, u holda ikkinchi qo'shiluvchi katta, aks holda ya'ni, n > 1000 bo'lsa, birinchi qo'shiluvchi katta bo'ladi.

Demak, kichkina n larda taqqoslashlar soni n ga teng bo'ladi, katta n larda esa n2 ga teng bo'ladi.

Saralashda taqqoslashlar soni quyidagi oraliqlarda bo'ladi:

dan gacha; – ideal holatda.

Saralashning quyidagicha usullari bor:

• 
  qat'iy (to'g'ridan-to'g'ri) usullar;
  
• 
  yaxshilangan usullar.
  

Qat'iy usullarning afzalliklarini ko'rib chiqaylik:

1. Bilamizki, dasturlarning o'zlari ham xotirada joy egallaydi. To'g'ridan-to'g'ri saralash usullarining dasturlari qisqa bo'lib, ular tushunishga oson.

2. To'g'ridan-to'g'ri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay.

3. Murakkablashtirilgan usullarda uncha ko'p amallarni bajarish talab qilinmasada, ushbu amallarning o'zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.

Shu joyni o'zida qat'iy usullarni ishlash tamoyillariga ko'ra 3 ta toifaga bo'lish mumkin:

1. To'g'ridan-to'g'ri qo'shish usuli (by insertion);

2. To'g'ridan-to'g'ri tanlash usuli (by selection);

3. To'g'ridan-to'g'ri almashtirish usuli (by exchange).