O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti



Download 18,83 Mb.
bet101/225
Sana30.12.2021
Hajmi18,83 Mb.
#89889
1   ...   97   98   99   100   101   102   103   104   ...   225
Bog'liq
“MTA” fani boyicha oquv uslubiy qollanma

Algoritm samaradorligi:

taqqoslashlar soni M = ,

almashtirishlar soni Cmax = 3 .
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.

Baryer usulidan foydalanilganda har bir saralash o’zining baryeriga 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


Download 18,83 Mb.

Do'stlaringiz bilan baham:
1   ...   97   98   99   100   101   102   103   104   ...   225




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish