Kurs ishi bajardi: S2-kt-21 guruh talabasi

Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:

1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element birinchi element bilan o'rin almashinadi.
3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritm samaradorligi:

• 
  Taqqoslashlar soni
  
• 
  Massiv tartiblanganda o'rinlashtirishlar soni
  
• 
  Massiv teskari tartiblanganda o'rinlashtirishlar soni
  

Ushbu usul bo'yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o'rinlashtirishlar soni tartibi n2 bo'ladi.

3.Piramidali saralash usuli.
Xo'sh, biz algoritmga keldik, unda biz ma'lumotlar tuzilmalari haqida gapirishni boshlaymiz. HeapSort takomillashtirilgan SelectionSort, lekin to'p bilan ishlaydi. Bu algoritm QuickSort-ga qaraganda bir oz sekinroq, lekin eng yomon holatda ham u O (n ^ 2) ga tushadigan bir xil QuickSort-dan farqli o'laroq, O (nlogn) murakkabligiga ega.
Xo'sh, to'p nima? Uyma - bu daraxtga o'xshash tuzilish bo'lib, unda bitta qoida bajariladi: agar B elementi A elementining avlodi bo'lsa, u holda A>B qiymati.
Uyumni amalga oshirishdan biri ikkilik to'p bo'lishi mumkin, unda quyidagi shartlar bajariladi:

1. 
   Otalar qadri zurriyot qadridan baland (maks-uyma, min-yiv ham bor bu yerda hammasi teskari☺)
   
2. 
   Barglarning chuqurligi 1 qatlamdan ko'p bo'lmagan holda farqlanadi
   
3. 
   Oxirgi qatlam chapdan o'ngga to'ldiriladi.
   

bilan
Birinchidan, ma'lumotlar strukturasini o'zi quramiz. Amalda ko'rganlarimni 2 turga bo'lish mumkin:

1. 
   Usullari bilan strukturani qurish va shunga o'xshashlar (OOP tillari, Sagewick, barcha holatlar)
   
2. 
   Qo'shimcha usullar bilan oddiy massivdan foydalanish
   

Biz keyingi postda to'pning OOP amalga oshirilishini albatta muhokama qilamiz, shuning uchun bugun biz faqat 2-usuldan foydalanamiz.
Shunday qilib, avval tartiblanmagan massivdan to'p hosil qiladigan usulni yozishimiz kerak:


/ **
* bolalarga chuqur kirib boradi va bolalar ota-onadan kamroq ekanligini tekshiring
* /
function sink (massiv, i, max) {
var big_index, child;
while (i big_index = i;
childl = 2 * i + 1;
childr = childl + 1; if (childl massiv [big_index])
big_index = childl;

if (childr massiv [big_index])
big_index = childr;

agar (big_index == i) qaytish; array.swap (i, katta_indeks);
i = katta_indeks;
}
}/ **
* massivdan yig'ish qurish
* /
funktsiya build_heap (massiv) {
var index = Math.floor ((array.length / 2) - 1); while (indeks> = 0) {
sink (massiv, indeks, massiv.uzunlik);
indeks --;
}
}
Ko'rib turganingizdek, bizda build_heap funksiyasi mavjud bo'lib, u massivning yarmidan boshlab sink funksiyasini chaqiradi. Cho'kish funktsiyasi biz ko'rsatgan varaqning barcha bolalari ustidan ishlaydi va ular haqiqatan ham kichikroq yoki yo'qligini tekshiradi, agar bo'lmasa, biz elementlarni almashtiramiz. Biz barcha bolalarni va uning bolalarining bolalarini bosib o'tganimizdan so'ng, biz orqaga qaytib, tekshirilgan elementdan oldin elementni tekshirishni boshlaymiz va hokazo. Natijada eng katta element birinchi o'rinda joylashgan ikkilik to'p hosil bo'ladi.
Barcha elementlarni aniq tekshirish uchun yarmini boshlaymiz☺
Saralash kodining o'zi juda oddiy:
/ **
* saralashni boshlash
* /
funktsiya heapSort (massiv) {
build_heap (massiv); var end = array.length - 1;

while (end> = 0) {
array.swap (0, end);
sink (massiv, 0, oxiri);
oxiri - = 1
} qaytish massivi;
}
Biz faqat birinchi elementni olamiz va uni oxirgisi bilan almashtiramiz, shuning uchun eng pastki qismida bizda eng katta element bor. Shundan so'ng, birinchi element uchun sink chaqiriladi, bu oxirgi elementni hisobga olmaganda, massivdagi eng katta elementga ildiz otadi. Va shunga o'xshash birinchi elementga qadar.



Aslida, gif-da ko'rib turganingizdek, boshida massivdan ikkilik to'p quriladi va undan keyin u tartiblanadi.
Afsuski, men venger raqsini topa olmadim, shuning uchun sizga biroz zamonaviy kerak:
Shunday qilib, natijalar:


Xulosa

Saralashga doir algoritmlar dasturlarni ishlashini biz kutgandan ham yaxshiroq holatda tezlashtirib beradi. Kichik dasturlarda ularning tez va foydali ishlashi sezilmasligi mumkin, lekin juda katta dasturlar yoki saytlarda bu saralash algoritmlar o’z effektini ko’rsatadi. Masalan, birgina Google saytida 1 soniyada millionlab yoki bo’lmasa milliarlab so’rovlar amalga oshirilad. Natijada sayt serverida qotishlar yuzaga kelishi mumkin. Ana shu holatlarda tezkor saralash algoritmlari har bir so’rovni topishni 1 soniyaga tezlashtirsa ham bu o’sha sayt uchun juda katta ish hisoblanadi.

Demak, biz hali ham bugungi kungacha ma’lum bo’lgan saralash algoritmlaridan ham tezroq ishlaydigan algoritmlarni yaratishga muhtojmiz.


Foydalanilgan adabiyotlar

• 
  Dasturlash asoslari. Aripov M .M ., O taxanovN.A “TAFAKKUR BO‘STONI” TOSHKENT-2015
  
• 
  hozir.org
  
• 
  fayllar.org
  
• 
  janobmusayev.medium.com
  
• 
  uz.mazorhomes.com
  
• 
  tuit.uz
  
• 
  texnoman.uz
  
• 
  aim.uz
  
• 
  arxiv.uz