Saralash algoritmlari. Saralashning yaxshilangan usullari. Tez saralash (Quick sort) saralash usuli



Download 214,92 Kb.
bet1/2
Sana27.01.2022
Hajmi214,92 Kb.
#412392
  1   2
Bog'liq
Mustaqil ish MT


Mavzu: Saralash algoritmlari. Saralashning yaxshilangan usullari. Tez saralash (Quick sort) saralash usuli.

Reja:


  1. Saralash algoritmlari.

  2. Quick sort saralash algoritmi.

  3. Xulosa .

Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi.

Tasavvur qilaylik sizda telefon raqamlari saqlanadigan daftarchasi bor (hali qo’l telefonlari ommalashmagan vaqtni eslang) va undagi nomlar tartibsiz holda yozilgan. Siz, aytaylik, Nodir ismli do’stingizning raqamini topishingiz uchun bu daftarchani boshidan boshlab axtarib chiqishga majbur bo’lasiz, bu esa ko’p vaqtni oladi. Lekin, agar ular alifbo tartibida saralab qo’yilgan bo’lsa, siz to’g’ri N harfiga o’tib izlashni boshlaysiz va vaqtdan bir necha barobarga yutasiz.

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)



Biz saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni nazarda tutamiz va bu kabi saralash algoritmlarining olti xilini ko’rib chiqamiz:

  1. Selection sort (Tanlab saralash)

  2. Bubble sort (Pufakchali saralash)

  3. Insertion sort (Joylashtirib saralash)

  4. Quick sort (Tezkor saralash)

  5. Merge sort (Qo’shib saralash)

  6. Radix sort

Ularning deyarli hammasi (6-sidan tashqari) ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(n*log(n)) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.

Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:

  • Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.

Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.

Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi.

Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi.

Yana haqli savol tug’ilishi mumkin, “Bu narsaning kimga keragi bor, baribir natija 1 1 2 3 4 5 bo’ladiku?” degan. Albatta, bu holatda turg’unlik ahamiyati sezilmasligi mumkin. Lekin, aytaylik siz biror korxona ishchilari ma’lumotlarini ularning nomiga ko’ra saralagan paytda turg’unlik kerak bo’lib qolishi mumkin. Ya’ni, birinchi Nodirbek ma’lumotlari, ikkinchi Nodirbek ma’lumotlaridan keyin turishi kerak degan kabi.

Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor).

Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi.



Tezkorsaralash (Quick Sort) algoritmi.

1964-yilda Charlz Hoar tamonidan taklif qilingan.

Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi

Sohasida yetuk mutaxassis. Uning “Tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm.

Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.

Algoritmning g’oyasi:

Massivda bo’luvchi element X tanlanadi.

Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin.



Keyin ularni alohida saralaymiz.


17

10

5

9

3

7

6

1

12

3

2

L



R

m


  • [L, R] saralanishi kerak bo’lgan oraliq.

  • m = (L+R) / 2 – kesmaning o’rtasi.

  • X=a[m] -bo’luvchi element.

  • Chap tamondan X dan kichik katta yoki teng bo’lgan birinchi elementni topamiz.


  • i

    i

    5

    9

    10

    7

    6

    1

    12

    10

    17

    2

    i

    3

    5

    9

    10

    7

    6

    1

    12

    10

    17

    2

    i

    3

    5

    2

    10

    7

    6

    1

    12

    10

    17

    9

    i

    j
    O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.

  • Ikkalasining qiymatini almashtiramiz.

9

10

6

7

5

2

1

17

10

3

12


j

i





3





j



j



2

10

3

5

6

7

1



12

10

17

9

i

j

12

10

17

9

i

j

5

2

1

7

6

10

12

10

17

9

i

j



1

6

10

7

2

3

5



3





Download 214,92 Kb.

Do'stlaringiz bilan baham:
  1   2




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