Jizzax filiali mustaqil ish



Download 0,66 Mb.
bet1/5
Sana06.07.2022
Hajmi0,66 Mb.
#743813
  1   2   3   4   5
Bog'liq
Mustaqil ish 3-Olimov Laziz




MIRZO ULUG‘BEK NOMIDAGI
OʻZBEKISTON MILLIY UNIVERSITETI
JIZZAX FILIALI


MUSTAQIL ISH
Mavzu: Saralash va izlashning samarali algoritmlari

FAN: ALGORITMIK TILLAR VA DASTURLASH


914-21-guruh Olimov Laziz Tolipovich

Saralash algoritmlari



Bugungi mavzumiz algoritmlashning to`rt asosiy yo`nalishlaridan biri hisoblangan saralash algoritmlariga bag`ishlanadi. Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`yicha.
Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):
Sonlar berilishi: 23, 54, 3, 22, 1, 45;

  1. Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turibdi)

  2. Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)

  3. Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)

  4. Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)


Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Ular:

  1. Bubble sort;

  2. Selection sort;

  3. Insertion sort;

  4. Quick sort;

  5. Merge sort.

Saralash tushunchasi va algoritmi. Tanlash orqali saralash va uning qo’llanilishi.


 Nima uchun kerak?
Saralash va izlash amalda juda ko’p qo’llaniladi, fayldagi so’zlarnini izlashdan tortib, internetda ma’lumot izlashgacha.

Saralash

  • a[0], a[1], a[2] .. a[n-1] massiv elementlari berilgan.

  • Ularni shunday joylashtirish kerakki, ular kamaymaslik tartibida bo’lib qolsin.

Masalan:
5 8 9 1 5 2 3 9
Saralangandan so’ng
1 2 3 5 5 8 9 9


Saralash algoritmlari

Saralash algoritmlari ikki tipga bo’linadi.

  1. O( ) vaqtda saralovchi algortimlar.

  2. O(n•log(n)) vaqtda saralovchi algoritmlar.

Algoritmlarda log(n) bu .
n= bo’lganda taqqoslang:
O( ) = , O(n•log(n)) = 1660964.

Tanlash orqali saralash algoritmi

  • Xar qadamda hali ko’rilmagan elementlar orasidan eng kichigini tanlaymiz.

  • Bu jarayon (n-1) marta davom etadi.


min







9

3

8

15

20

9

2

1

9

3

2

15

20

9

8

1

9

3

2

15

1

9

8

20


9

15

20

9

8

3

2

1

9

9

20

15

8

3

2

1

9

9

8

15

20

3

2

1



20

15

9

9

8

3

2

1

20

15

9

9

8

3

2

1

20

15

9

9

8

3

2

1

Ikki o’zgaruvchining qiymatini almashtirish.

  • a va b ning qiymatlarini almashtirish kerak. Qo’shimcha t o’zgaruvhci kiritamiz.

  • t = a;

  • a = b;

  • b = t;

Qo’shimcha o’zgaruvchi kiritmasdan almashtirish.

  • a = a+b; (a+b, b);

  • b = a-b; (a+b, a);

  • a = a-b; (b, a);


Download 0,66 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5




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