3-Amaliy mashg’ulot

Algoritm samaradorligi: 

taqqoslashlar soni M = 

n n n

2 2

4

2

 

, 

 

 

almashtirishlar soni C

max

 = 3

n

2

4

. 

 

Saralashning yaxshilangan usullari 

---

 

Quiksort – tez saralash usuli 

 

G’oyasi:  Bu  usul  almashtirish  usulidagi  saralashga  tegishli  bo’lib  uning  asosini 

kalitlarni tanlangan kalitga nisbatan ajratish tashkil qiladi. 

 

 

6 dan chap tomonda kalitlari kichik, o’ng tomonda esa kalitlari 6 dan katta bo’lgan 

elementlar joylashadi (yuqoridagi chizma). 

procedure Sort (L, R: integer); 

begin 

  i := L; 

  j := r; 

  x := a[(L + r) div 2]; 

  repeat 

    while a[i] < x do 

      i := i + 1;     

    while a[j] > x do 

      j := j - 1; 

    if i <= j then 

      begin 

        y := a[i]; 

        a[i] := a[j]; 

        a[j] := y; 

        i := i + 1; 

        j := j - 1 

      end; 

  until i > j; 

  if L < j then sort (L, j); 

  if i < r then sort (i, r); 

end; 

 

procedure QuickSort; 

---

begin 

  sort (1, n); 

end; 

Algoritm samaradorlig: 

O(n log n) – eng samarali usul. 

 

SHell saralashi (qisqarib boruvchi qadamlar orqali saralash) 

 

To’g’ri qo’shish usulini 1959 yilda D. SHell tomonidan mukammallashtirish taklif 

qilingan. Quyidagi chizmada ushbu usul tasvirlangan: 

 

 

Boshida  bir  biridan  4  qadamda  joylashgan  elementlar  o’zaro  guruhlanib  saralash 

amalga oshiriladi. Bunday jarayon to’rtlik saralash deb ataladi. Birinchi o’tishdan keyin 

elementlar  qayta  guruhlanib,  endi  har  ikki  qadamdagi  elementlar  taqqoslanadi.  Bu  esa 

ikkilik  saralash  deb  nomlanadi.  Va  nihoyat,  uchinchi  o’tishda  oddiy  yoki  yakkalik 

saralashi amalga oshiriladi.  

Bir  qarashda  mazkur  usul  bilan  saralash  amalga  oshirilganda  saralash  jarayoni 

kamayish  o’rniga  ortib  boradigandek  tuyulsada,  elementlarni  o’rin  almashtirishlar 

nisbatan kam amalga oshiriladi.  

Ko’rinib  turibdiki,  bu  usul  natijasida  tartiblangan  massiv  hosil  bo’lib,  har  bir 

o’tishdan  keyin  saralashlar  kamayib  boradi.  Eng  yomon  holatda  oxirgi  ishni  yakkalik 

saralash amalga oshiradi.  

Barg’er usulidan foydalanilganda har bir saralash o’zining barg’eriga ega bo’lishi 

lozim hamda dastur uning joyini aniqlashi uchun uni iloji boricha osonlashtirish lozim. 

SHuning uchun massivni [-h1..N] gacha kengaytirish lozim bo’ladi. 

h[1..t] – qadamlar o’lchami massivi 

a[1..n] - saralanayotgan massiv 

k – saralash qadami 

x – qo’shilayotgan element qiymati 

Subroutine  ShellSort 

const   t = 3; 

            h(1) = 5; 

            h(2) = 3; 

            h(3) = 1; 

var 

  h: array [1..t] of integer; 

---

  a: array [1..n] of integer; 

   k, x, m, t, i, j: integer; 

 begin 

   for  m = 1 to t do 

     begin 

       k:= h(m); 

       for i = k + 1 to n do 

         begin 

          x:= a(i);             

          for j = i-k  downto k   do 

             begin 

              if  x < a(j ) then 

                a(j+k):= a(j); 

               else  

                 goto 1; 

              end ; 

             end; 

            end; 

1:          a(j+1) = x ; 

         end;    

    end . 

 

Umuman  olganda,  qanday  qadamlar  tanlanganda  eng  yaxshi  natija  olinishi 

isbotlanmagan bo’lsada, lekin bu qadamlar biri ikkinchisini ko’paytuvchilari bo’lmasligi 

lozimligi aniqlangan. 

D. Knut qadamlarni quyidagicha ketma-ketligini taklif qilgan (teskari tartibda): 

1,3,7,15,31,…,ya’ni: h

m-1

=2h

m

+1, h

t

=1, t = [log

2

n] - 1. Agar qadamlar ushbu 

ko’rinishda, algoritm samaradorligi tartibi  O(n

1.2

).