Referati toshkent 2023 saralash algoritmlari mohiyati va ularning samaradorligini baholash. Reja

bubbleSort(arr, N); cout << "Sorted array: \n"; printArray(arr, N); return 0; }

Shunday qilib pufakchali saralash algoritmining ketma-ketligi quyidagicha

(arr[] = {2, 4, 6, 9, 12, 23, 0, 1, 34} misolida ko‘ramiz):

• 2, 4, 6, 9, 12, 23, 0, 1, 34, // 1-qadam.

  
  

• 2, 4, 6, 9, 12, 0, 1, 23, 34, // 2-qadam.

  
  

• 2, 4, 6, 9, 0, 1, 12, 23, 34, // 3-qadam.

  
  

• 2, 4, 6, 0, 1, 9, 12, 23, 34, // 4-qadam.

  
  

• 2, 4, 0, 1, 6, 9, 12, 23, 34, // 5-qadam.

  
  

• 2, 0, 1, 4, 6, 9, 12, 23, 34, // 6-qadam.

  
  

• 0, 1, 2, 4, 6, 9, 12, 23, 34, // 7-qadam.

  
  

• 0, 1, 2, 4, 6, 9, 12, 23, 34, // 8-qadam.

  
  

• 0, 1, 2, 4, 6, 9, 12, 23, 34, // 9-qadam.

  
  

• 0, 1, 2, 4, 6, 9, 12, 23, 34, // saralangan holdagi massiv.

  
  

Insertion sort (Joylashtirib saralash)
Insertion sort (Joylab saralash) ham tartibsiz massiv elementlarini saralash uchun moʻljallangan. Uning ishlash algoritmi xuddi qoʻldagi kartani saralashga oʻxshab ketadi. Tartibsiz turgan kartalar ichidan birini olasiz va uni oʻzi turishi kerak boʻlgan joyga joylashtirib qoʻyasiz.
Insertion sort ham shu koʻrinishda ishlaydi. Algoritm oldin massiv boshidagi ikkita elementni saralab olib, massivning qolgan elementlarini shunga qarab oʻz oʻrniga joylashtirib chiqadi.

4-rasm. Insertion sort

Joylab saralashning xususiyatlari. Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir. Insertion sort kichik maʼlumotlarni saralash uchun samarali hisoblanadi. Joylab saralash tabiatan moslashuvchan, yaʼni qisman saralangan maʼlumotlar toʻplamlari uchun mos keladi.
Insertion sort ham Selection sort va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan koʻra samaraliroq algoritm hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion sort algoritmi Merge sort yoki Quick sort algoritmidan ham koʻra tezroq ishlaydi.
Joylab saralash algoritmining ishlashi:
Algoritmni ushbu massiv misolida ko‘rib chiqamiz: arr[] = {12, 11, 13, 5, 6}

Birinchi oʻtish
Dastlab, massivning dastlabki ikkita elementi joylash tartibida taqqoslanadi.

Bu yerda 12 11 dan katta, ular oʻsish tartibida emas va 12 oʻzining toʻgʻri joyida emas. Shunday qilib, 11 va 12 ning oʻrnini almashtiring. Shunday qilib, hozircha 11 tartiblangan pastki qatorda saqlanadi.

Ikkinchi oʻtish
Endi keyingi ikkita elementga oʻting va ularni solishtiring

Bu yerda 13 12 dan katta, shuning uchun ikkala element ham oʻsish tartibida turibdi, almashtirish sodir boʻlmaydi. 12, shuningdek, 11 bilan birga tartiblangan pastki qatorda saqlanadi.

Uchinchi oʻtish
Endi tartiblangan kichik massivda ikkita element mavjud, ular 11 va 12 Keyingi ikkita elementga oʻtish: 13 va 5

5 va 13 ikkalasi ham oʻz joyida emas, shuning uchun ularni almashtiring

Almashtirilgandan soʻng, 12 va 5 elementlar tartiblanmadi, shuning uchun yana almashtiriladi.

Bu yerda yana 11 va 5 tartiblanmadi, shuning uchun yana almashtiring

bu yerda u oʻzining toʻgʻri holatida