O’zbekiston respublikasi oliy va orta

Pufaksimon saralash algoritimi

Ushbu usulning g’oyasi quyidagicha: n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo’lsa, u holda ularning o’rni almashtiriladi. Misol : massiv - 4, 3, 7, 2, 1, 6

3-rasm

Pufaksimon saralash usulida massiv elementlarining o’rnini almashtirish

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.

“Pufaksimon” saralash usulini hisoblashga misol

4-rasm

Massivni pufaksimon saralashga misol berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o’tishlar soni 5-1=4 marta bo’ladi. Misoldan ko’rinib turibdiki, algoritm ichki siklda

3. 
   qadamdan boshlab massivni “bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo’ladi.
   

Berilgan usullarning afzalligi:

1. 
   Eng sodda algoritm;
   

2. 
   Amalga oshirish sodda;
   

3. 
   Qo’shimcha o’zgaruvchilar shart emas.
   

Kamchiliklari:

1. 
   Katta massivlarni uzoq qayta ishlaydi;
   

2. 
   Har qanday holatda ham o’tishlar soni kamaymaydi.
   

2. Tez saralash va birlashtirish sort nima?

Tez saralash nima?

Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzogʻi bilan O(n²) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi.
Quick Sort - bo'linish va zabt etish yondashuviga asoslangan yuqori samarali, ammo samarali tartiblash algoritmi, bu muammoni ikki yoki undan ortiq kichik masalalarga ajratib, so'ngra rekursiv ravishda echiladigan dinamik yondashuvga juda o'xshaydi. Agar kichik muammolarning hajmi etarlicha kichik bo'lsa, ular hech qanday muammosiz oddiygina hal qilinadi. Tez bo'linish algoritmi bo'limlar almashinuvi turi deb ham ataladi, saralanadiganlar ro'yxatini uchta asosiy qismga ajratadi:

1. 
   Umumiy element (markaziy elementlar);
   

2. 
   aylanadan kichik elementlar;
   
3. 
   pivotdan kattaroq elementlar.
   

O'chirishning o'zi ikki guruh o'rtasida oxirgi holatiga o'tkaziladi va QUICK SORT rezursiv ravishda qo'llaniladi.

5-rasm

• 
  1Ishlash printsipi
  
• 
  2Tez saralash (QuickSort) algoritmining javascriptdagi realizatsiyasi
  
  • 
    2.1C
    

o 2.2C++

• 
  2.3Java
  
• 
  2.4Python
  
• 
  2.5Joy
  
• 
  2.6PHP
  
• 
  2.7Haskell
  
• 
  2.8Prolog
  
• 
  2.9Ruby
  
• 
  2.10SML
  

Ishlash printsipi

1. 
   Massivda ixtiyoriy tayanch element tanlaymiz.
   
2. 
   Keyin undan kichik yoki teng elementlarni uning chap tomoniga, katta elementlarni oʻng tomoniga oʻtkazamiz.
   
3. 
   1-2-chi qadamlarni tayanch elementning oʻng va chap tomonlaridagi elementlar uchun qoʻllaymiz.
   

Algorimning 2 qadami turlicha boʻlib uning bir nechta realizatsiyalari mavjud. Ayni shu 2 qadamda elementlarni joylashtirish algoritmi tufayli algoritm saralash algoritmlari ichida eng tez ishlaydiganlaridan biridir.
Tez saralash (QuickSort) algoritmining javascriptdagi realizatsiyasi