Saralash usullari mavzusi bo’yicha ma’ruza matni

Saralash usullari mavzusi bo’yicha ma’ruza matni

2.1.1. Saralash algoritmlari haqida umumiy ma’lumot

Saralash – bu berilgan to’plamda ob’ektlarni belgilangan tartibda joyini almashtirish jarayoni. Saralash maqsadi – saralangan to’plamda kelasi elementni izlashni osonlashtirish. Shu sababdan ko’plab amaliy dasturlash masalalarida saralash elementlari ishtirok etadi.
“O’z joyida” saralash algoritmlarini (oddiy saralash algoritmlar), ya’ni massivning nusqasini ishlatmaydigan algoritmlarni qaraymiz.
Oddiy saralash algoritmining samaradorligining qo’lay choralari saralash chog’idagi zarur taqqoslashlar va elementlarni zarur uzatishlar sonida ko’rinadi.
Samarali saralash algoritmlari qo’yidagi taqqoslash tartibini talab qiladi:

bu erda, N – elementlar soni, С – zarur taqqoslashlar soni. Biz taqqoslash tartibi soni: ni talab qiladigan oddiy saralash usulini qaraymiz.
Oddiy saralash usullarini asosiy uchta sinfga ajratish mumkin:

• 
  tanlash bilan saralashlar (Selection sorts);
  
• 
  joylashtirish bilan saralashlar (Insertion sorts);
  
• 
  almashish bilan saralashlar (Exchange sorts).
  

Tanlash bilan saralashda eng katta element tanlanadi va oxirgi element bilan o’rin almashadi. So'ngra shu narsa s-1 element uchun takrorlanadi.

1-rasm. Oddiy tanlash bilan saralash
Eng katta qiymati bilan topilgan element joyini oxiridan oldingi element bilan almashtiradi va h.k.(1-rasm).
Saralashda kiritilgan elementlari tartiblashtirilmagan va alloqashon tartiblashtirilgan bo’lib bo’linadi. Dastlab tartiblashtirilgan qismi faqat bitta elementni o’z ichiga oladi. Tartiblanmagan qismidan boshlab navbattagi element tartiblangan qismidagi mos joyiga qo’yiladi. Bu holda tartiblangan qismi bitta elementga uzaytiriladi, tartiblanmagan qismi esa qisqartiriladi. Tartiblanmagan qismi yo’qolishi bilan saralash tugatiladi. (2-rasm).

2-rasm. Oddiy joylashtirish bilan saralash
Almashish bilan saralashning asosiy xususiyati – ikki qo’shni elementning joyini o’zgartirsh, agar ular saralammagan massiv talabida joylashmagan bo’lsa.

3-rasm. Oddiy almashish bilan saralash
Ko’rilayotgan klassifikatsiyalashda har xil algoritmlar mavjud. Ular murakkabliligi, bajarilish tezligi, amallar ketme-ketligi bilan farq qiladi
Masalan:

• 
  joylashtirish bilan saralash (Insertion sort);
  
• 
  ko’piksimon saralash (Bubble sort);
  
• 
  ildizsimon saralash (Root sort);
  
• 
  piramidasimon saralash  (Heapsort);
  
• 
  birlashtirib saralash (Mergesort);
  
• 
  tez saralash (Quicksort);
  
• 
  Shell saralash (Shell sort) va h.k..
  

Saralashning asosiy turlasi va ko’rinishlarini batafsil ko’rib o’tamiz (dastlab oddiy keyin murakkab saralashlar).