Tartiblash va saralash algoritmlari

Insertion sort’ning ustunliklari:

• 
  Oddiy algoritm
  
• 
  Kichik array’lar uchun mahsuldorlik yuqori
  

Kamchiliklari:

• 
  Katta array’larda mahsuldorlik pasayib ketadi, sababi juda ko’p solishtirishlarni amalga oshirish kerak bo’ladi.
  
• 
  Upper bound – ¼ N² ~ O(N²). Algoritm mergesort va quicksort bilan solishtirganda yaxshi natija ko’rsatmaydi.
  

Ishlash konsepti

1. 
   Arrayning ikkinchi elementini birinchi elementi bilan solishtiramiz. Agar ikkinchi element katta bo’lsa, birinchi element va ikkinchi element o’rnini almashtiramiz.
   
2. 
   Arrayning uchinchi elementini ikkinchi elementi bilan solishtiramiz. Agar uchinchi elementi ikkinchi elementidan katta bo’lsa, uchinchi va ikkinchi element o’rnini almashtiramiz. So’ng 1-qadamni takrorlaymiz.
   
3. 
   Arrayning to’rtinchi elementini uchinchi elementi bilan solishtiramiz. Agar to’rtinchi elementi uchinchi elementidan katta bo’lsa, to’rtinchi va uchinchi element o’rnini almashtiramiz. So’ng 2-qadamni takrorlaymiz.
   

Animatsion ko’rinishda:

Insertion sort
Kod:

	function insertionSort(arr = []) {
	const length = arr.length
	for (let i = 1; i < length; i++) {
	for (let j = i; j > 0; j--) {
	if (arr[j] < arr[j - 1]) {
	// Ikki element o'rnini almashtiramiz.
	[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
	}
	else {
	// Keyingi solishtirishlarning foydasi yo'q.
	// Ular allaqachon tartiblangan.
	break
	}
	}
	}
	return arr
	}

Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni tartiblash uchun «<» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.


3. Saralash algoritmlari
Saralash - tartiblash (Sorting Algorithms) 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 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 tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatnin g boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz.
Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan sizning sinfingizda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida saralash mumkin.
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) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54;
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;

1. 
   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 turibdi)
   
2. 
   Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)
   
3. 
   Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
   
4. 
   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`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. 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. 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. 
   Selection sort (Tanlab saralash)
   
2. 
   Bubble sort (Pufakchali saralash)
   
3. 
   Insertion sort (Joylashtirib saralash)
   
4. 
   Quick sort (Tezkor saralash)
   
5. 
   Merge sort (Qo’shib saralash)
   
6. 
   Radix sort
   

Ularning deyarli hammasi (6-sidan tashqari) ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.
Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:

• 
  Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.
  

• 
  Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.
  

Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi.
Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi.
Yana haqli savol tug’ilishi mumkin, “Bu narsaning kimga keragi bor, baribir natija 1 1 2 3 4 5 bo’ladiku?” degan. Albatta, bu holatda turg’unlik ahamiyati sezilmasligi mumkin. Lekin, aytaylik siz biror korxona ishchilari ma’lumotlarini ularning nomiga ko’ra saralagan paytda turg’unlik kerak bo’lib qolishi mumkin. Ya’ni, birinchi Nodirbek ma’lumotlari, ikkinchi Nodirbek ma’lumotlaridan keyin turishi kerak degan kabi.
Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor).
Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi.
Bu darsimizda sizlar bilan saralash haqida umumiy tushunchani va saralash algoritmlari bir-biridan qanday farqlanishini ko’rib chiqdik. Keyingi darslardan sarlash algoritmlarini ko’rib chiqish mobaynida bu narsalar haqida yana batafsilroq gaplashamiz.


FOYDALANILGAN ADABIYOTLAR RO’YHATI:

1. 
   В.А.Успенский, А.Л.Семенов. Теория алгоритмов: основные открытия и приложения. – М: Наука, 1987, 287 с.
   
2. 
   Т..Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. Сер: Классические учебники. М.: МЦНМО, 2001.- 960 с.
   
3. 
   Gulomov S.S. va boshqalar. Axborot tizimlari va texnologiyalari. Toshkent, 2000 y.
   
4. 
   Jumanov I.I. Mingbaev N.S., Informatika.- Samarqand: SamDU nashri, 2002, 107 bet.
   
5. 
   Ahatov A.R., Zaripova G.L. va boshq. Axborot texnologiyalari // Uslubiy qo’llanma. – Samarqand: SamDU nashri, 2008 yil – 112 bet.
   
6. 
   Интеллектуализatsiя ЭВМ. Перспективы развития вычислительной техники. Под ред. Ю.М.Смирнова. М: 1989 г.
   
7. 
   Тыугу Х. Концептуальное программирование. М: Наука, 1984.
   
8. 
   Н. Вирт. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.
   
9. 
   Jumanov I.I., Mingboev N.S. Hisoblash sistemalarining informatsion asoslari. Samarqand: SamDU nashri, 2002, 107 bet.