Reja: Algoritm tushunchasi

O(nlogn)  T(n)  O(n²);

T(n)=O(n) – идеал ҳолатда.

Қўйиш орқали саралаш

Объектлар сараланган a(1),...,a(i-1) ва сараланмаган a(i),...,a(n) каби 2 та кетма-кетликларга бўлинади. Ҳар бир қадамда (i=2 дан бошлаб) сараланмаган кетма-кетликдан i-чи элемент ажратиб олиниб сараланган кетма-кетликнинг керакли жойига қўшилади.

Қўйиш орқали саралаш алгоритми самарадорлиги

Таққослашлар сони:

Ўринлаштиришлар сони:



Саралашга кетган вақт:



Танлаш орқали саралаш

1. Берилган объектлар ичидан энг кичик калитга эга элемент танланади.

2. Ушбу элемент бошланғич кетма-кетликдаги биринчи элемент a₁ билан ўрин алмашади.

3. Ундан кейин ушбу жараён қолган n-1 та элемент, n-2 та элемент ва хоказо, токи битта энг “катта” элемент қолгунча давом эттирилади.

Misol:

Ustuvor navbatlar. Agar biz S-dan elementlarni o'chirishni va qo'shishni, shuningdek, algoritm talab qilganda S-dan elementni tanlash imkoniyati bo’lishini xohlasak, albatta S dinamik bo’lishi lozim. Ustuvor navbatlar shunday ilovalarga mo’ljallanganki, unda har bir elementga ustuvorlikni bildiruvchi (kalit) tayinlanadi va har safar S-dan elementni tanlash talab qilinsa, ustuvorlik darajasi yuqori bo'lgan element tanlanishi kerak bo’ladi. Ustuvor navbat – bu shunday ma'lumotlar tuzilmasiki, u S ning elementlari asosida tuzilgan bo’lib, xar bir element v uchun uning ustuvorligini belgilaydigan key(v) kalit mos qo’yiladi; kichik kalitlar vakili bo’lgan element yuqori ustuvorlikka ega bo’ladi. Ustuvor navbatlar element qo'shishni, elementlarni navbatdan olib tashlash amallarini qo'llab-quvvatlaydi va, shuningdek, eng kichik kalitga ega elementni, ya’ni eng ustuvor elementni tanlash imkonini beradi. Umuman olganda uctuvor navbatlarni ishlatganda, boshqa amallarni ham bajarish mumkin bo’ladi. ustuvor navbatlarning umumiy imkoniyatlarini muhokama qilishda albatta e'tiborga olish kerak bo’lgan qo’llanish soxasi bu - real vaqtda jarayonlarni boshqarish masalasidir. (masalan, jarayonlarni kompyuterda bajarilishini rejalashtirish). Har bir jarayonga ba'zi ustuvorliklar beriladi, ammo jarayonlarni qabul qilish tartibi ularning ustuvorliklari tartibiga to'g'ri kelmaydi. Buning o'rniga faol jarayonlarning ketma-ketligi mavjud; biz eng ustuvor jarayonni ajratib olishni va uni faollashtirishni xohlaymiz.

Ko'p jarayonlar ustuvor navbat sifatida taqdim etilishi mumkin. Jarayon kaliti ustuvor qiymatni anglatadi. Eng ustuvor jarayonni rejalashtirish ustuvorlik navbatidan eng kichik kalitli elementni tanlashga mos keladi ; parallel ravishda yangi jarayonlar ustuvorlik qiymatlariga muvofiq ravishda ustuvor navbatga qo'yilishi kerak. Ma’lumki solishtirish orqali saralashda ham bajariladigan operatsialar soni (vaqt) eng kamida nlogn ga proportsional bo’ladi. Demak, bundan logn vaqt yuqoridagidan ancha yaxshiligini ko’rish mumkin. Shuni ta'kidlash kerakki, haqiqiy vaziyat biroz murakkabroq: ustuvor navbatlarni amalga oshirish bu yerda keltirilganlarga qaraganda murakkabroq, ular muayyan operatsiyalarni bajarish vaqtini yaxshilaydi va qo'shimcha funktsionallikni ta'minlaydi hamda n ta sonlar k-kini saralovchi ustuvor navbat operatsiyalari k-kgi eng kamida nlogn ga proportsional bo’lishi kerak.

Uyum(kucha) - bizning kontekstimizda bu tartiblangan massiv va ro'yxatning afzalliklari birlashtirilgan ma'lumotlar tuzilimaidir. Kontseptual darajada, uyumni muvozanatlangan binar daraxt deb hisoblash mumkin.

Uyum qoidasi:har bir element kaliti uning ota-onasi kalitidan kichik emas, key (w) ≤ key (v), bu erda w-ota-ona, v-element. Agar istalgan vaqtda elementlarning umumiy soni N oldindan ma'lum bo'lsa, uyumni massiv yordamida amalga oshirish mumkin va ko'rsatkichlarsiz. Bunday uyumlarni i = 1, ..., N indeksli H massivida saqlash mumkin. Uyum tugunlari massivdagi pozitsiyalarga mos keladi. H[1] ildiz boladi, i-joydagi uning merosxo’rlari esa H massivda leftChild(i) = 2i va rightChild(i) = 2i + 1 kabi joylashadi, ota-onasi esa parent (i) = [i/2] joyda bo’ladi.

Uyumga element qo’yish

Uyumni yuqoriga qarab to’g’rilash

Uyumga i-o’rinda element uyum hossasini buzganda to’g’rilash jarayoni—bu jarayon algoritmi:

• 
  Heapify-up(H,i):
  
• 
  agar i > 1
  
• 
  O’zlashtirish j = parent(i) =[i/2]
  
• 
  agar key[H[i]]
• 
  H[i] va H[j] elemtntlar o’rnini almashtirish
  
• 
  Heapify-up(H,j)
  
• 
  agarni tugashi
  
• 
  agarni tugashi
  
• 
  element qo’yish oxiridan bajariladi.
  

Uyumni pastga qarab to’g’rilash

• 
  Heapify-down(H,i):
  
• 
  Присвоить n = length(H)
  
• 
  Если 2i > n
  
• 
  Завершить выполнение без изменения H
  
• 
  Иначе Если 2i < n
  
• 
  Присвоить left = 2i и right = 2i + 1
  
• 
  Присвоить j индекс для минимизации key[H[left]] и key[H[right]]
  
• 
  Иначе Если 2i = n
  
• 
  Присвоить j = 2i
  
• 
  Конец Если
  
• 
  Если key[H[j]] < key[H[i]]
  
• 
  Поменять местами элементы H[i] и H[j]
  
• 
  Heapify-down(H, j)
  
• 
  Конец Если
  

Elementni o’chirish