1. Dasturiy ta’minot va uning turlari


Insertion sort algoritmining qadamlari



Download 14,99 Mb.
bet12/89
Sana22.07.2022
Hajmi14,99 Mb.
#838566
1   ...   8   9   10   11   12   13   14   15   ...   89
Bog'liq
Gost 2022

Insertion sort algoritmining qadamlari:

  1. Array boshidagi ikkita element solishtirib, saralab olinadi.

  2. Qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya)

  3. Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda array chegaralaridan o’tib ketib qolmaslikka e’tibor berish kerak.

  4. Tashqi takrorlanish tugashi bilan array ham saralangan bo’ladi.

Insertion sort algoritmining murakkabligi - Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi. Aynan, array elementlari deyarli saralangan holatda Insertion sort algoritmi Merge yoki Quick sort algoritmidan ham ko’ra tezroq ishlaydi.
Shaker saralash ilg'or pufakchali tartiblash usuli hisoblanadi. Pufakchani saralash usulini tahlil qilib, ikkita narsani ta'kidlash mumkin: - agar massivning bir qismi bo'ylab harakatlanayotganda hech qanday almashtirish sodir bo'lmasa, massivning bu qismi allaqachon tartiblangan va shuning uchun uni ko'rib chiqishdan chiqarib tashlash mumkin. - massiv oxiridan boshiga o'tganda minimal element birinchi holatga "suzadi", maksimal element esa faqat bitta pozitsiyani o'ngga siljitadi.
Ushbu ikki g'oya pufakchani saralash usulini o'zgartirishga olib keladi.
- Oxirgi almashtirishdan massivning oxirigacha (boshi) tartiblangan elementlar mavjud. Ushbu haqiqatni hisobga olgan holda, skanerlash massivning oxirigacha (boshiga) emas, balki ma'lum bir pozitsiyaga qadar amalga oshiriladi. Massivning tartiblangan qismining chegaralari har bir iteratsiyada 1 pozitsiyaga siljiydi.
- Massiv o'ngdan chapga va chapdan o'ngga navbatma-navbat skanerlanadi.
- Massiv barcha elementlar o'sish (kamayish) tartibida bo'lgunga qadar skanerdan o'tkaziladi.
- Massiv elementlarini ko'rish soni uning elementlarini tartiblash momenti bilan belgilanadi.
59. Birlashtirib saralash algoritmlari (Merge Sort, algoritm bajarilishi, algoritmning murakkabligi, algoritmning kamchiligi)
Merge Sort(birlashtirib saralash) bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo’lib, uning ishlash prinsipi “Bo’lib tashla va hukmronlik qil” paradigmasi asosiga qurilgan. Merge sort algoritmi asosiy ikkita qismdan iborat:
- Berilgan arrayni rekursiv holda teng ikkita qismlarga bo’lib chiqish. Bu qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo’lib qolguncha davom etadi.
- Hosil bo’lgan arraylarni qaytib birlashtirib chiqish va bir vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash.

Download 14,99 Mb.

Do'stlaringiz bilan baham:
1   ...   8   9   10   11   12   13   14   15   ...   89




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