1. Dasturiy ta’minot va uning turlari

Insertion sort algoritmining qadamlari:

1. 
   Array boshidagi ikkita element solishtirib, saralab olinadi.
   
2. 
   Qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya)
   
3. 
   Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda array chegaralaridan o’tib ketib qolmaslikka e’tibor berish kerak.
   
4. 
   Tashqi takrorlanish tugashi bilan array ham saralangan bo’ladi.
   

Insertion sort algoritmining murakkabligi - Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi. Aynan, array elementlari deyarli saralangan holatda Insertion sort algoritmi Merge yoki Quick sort algoritmidan ham ko’ra tezroq ishlaydi.
Shaker saralash ilg'or pufakchali tartiblash usuli hisoblanadi. Pufakchani saralash usulini tahlil qilib, ikkita narsani ta'kidlash mumkin: - agar massivning bir qismi bo'ylab harakatlanayotganda hech qanday almashtirish sodir bo'lmasa, massivning bu qismi allaqachon tartiblangan va shuning uchun uni ko'rib chiqishdan chiqarib tashlash mumkin. - massiv oxiridan boshiga o'tganda minimal element birinchi holatga "suzadi", maksimal element esa faqat bitta pozitsiyani o'ngga siljitadi.
Ushbu ikki g'oya pufakchani saralash usulini o'zgartirishga olib keladi.
- Oxirgi almashtirishdan massivning oxirigacha (boshi) tartiblangan elementlar mavjud. Ushbu haqiqatni hisobga olgan holda, skanerlash massivning oxirigacha (boshiga) emas, balki ma'lum bir pozitsiyaga qadar amalga oshiriladi. Massivning tartiblangan qismining chegaralari har bir iteratsiyada 1 pozitsiyaga siljiydi.
- Massiv o'ngdan chapga va chapdan o'ngga navbatma-navbat skanerlanadi.
- Massiv barcha elementlar o'sish (kamayish) tartibida bo'lgunga qadar skanerdan o'tkaziladi.
- Massiv elementlarini ko'rish soni uning elementlarini tartiblash momenti bilan belgilanadi.
59. Birlashtirib saralash algoritmlari (Merge Sort, algoritm bajarilishi, algoritmning murakkabligi, algoritmning kamchiligi)
Merge Sort(birlashtirib saralash) bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo’lib, uning ishlash prinsipi “Bo’lib tashla va hukmronlik qil” paradigmasi asosiga qurilgan. Merge sort algoritmi asosiy ikkita qismdan iborat:
- Berilgan arrayni rekursiv holda teng ikkita qismlarga bo’lib chiqish. Bu qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo’lib qolguncha davom etadi.
- Hosil bo’lgan arraylarni qaytib birlashtirib chiqish va bir vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash.