Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari - Информатика и ИТ - Презентации

Информация о документе

Цена	3000UZS
Размер	827.5KB
Покупки	0
Дата загрузки	06 Декабрь 2024
Расширение	pptx
Раздел	Презентации
Предмет	Информатика и ИТ

Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari

Купить

REJA : 1. Saralash tushunchasi va uning vazifasi 2. Saralash masalasini formal qo‘yilishi Ichki saralash usullari: Qat’iy usullar va yaxshilangan usullar 3. Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari

Saralash tushunchasi va uning vazifasi Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat. Izoh Saralash – bu berilgan to‘plam elementlarini biror bir tartibda ( o‘sish yoki kamayish ) joylashtirish jarayonidir.  dasturlarni translyasiya qilishda;  ma’lumotlar majmuasini tashqi xotirada tashkil qilishda;  kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshq.Saralashning tadbiqi

Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:  ichki saralash – bu operativ xotiradagi saralash;  tashqi saralash – tashqi xotirada saralash. Saralash masalasini formal qo‘yilishi Berilgan: a 1 , a 2 ,…, a n , ob’ektlar to‘plami. Talab qilinadi: Berilgan ob’ektlarni tartiblash, ularni shunday a p1 , a p2 ,…, a pn ketma-ketlikda o‘rinlashtirish lozimki, bunda ularning kalitlari kamaymaydigan tartibda joylashsin: k p1  k p2  …  k pn . Def. Saralash algoritmi turg‘un deyiladi, agarda saralash natijasida bir hil kalitli ob’ektlarlar bir- biriga nisbatan o‘rinlarini o‘zgartirmasa.

Samaradorlik mezonlari saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni); dasturni ishlab chiqishga ketgan vaqt; talab qilinadigan xotira xajmi. Saralashga ketgan vaqt uchun quyidagi o‘rinli bo‘ladi: O( nlogn )  T( n )  O( n 2 ); T( n )=O( n ) – ideal holatda. Ichki saralash usullari Qat’iy usullar Yaxshilangan usullar

Qo‘yish orqali saralash Algoritm g’oyasi Ob’ektlar hayolan “tayyor” a(1),...,a(i-1) va boshlang‘ich ketma-ketliklarga bo‘linadi. Har bir qadamda (i=2 dan boshlab) boshlang‘ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo‘shiladi. Misol: Faraz qilaylik, kalit qiymatlari 40,51,8,38,90,14,2,63 bo‘lgan ob’ektlar berilgan bo‘lsin. - boshlang’ich holat

Qo‘yish orqali saralash algoritmi tahlili Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat. Taqqoslashlar soni: O‘rinlashtirishlar soni: Saralashga ketgan vaqt:

• Qo’yish orqali saralash usuli psevdocodi : • For 1=2 to n • X=a(i) • for j=i-1 downto 1 • if x<a(j) • then a(j+1)=a(j) • Else go to L • endif • Next j • L : a(j+1)=x • Next I • return

Tanlash orqali saralash 1. Berilgan ob’ektlar ichidan eng kichik kalitga ega element tanlanadi. 2. Ushbu element boshlang‘ich ketma-ketlikdagi birinchi element a 1 bilan o‘rin almashadi. 3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi. Misol: - boshlang’ich holat

Tanlash orqali saralash algoritmi tahlili Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat. Taqqoslashlar soni: O‘rinlashtirishlar soni: Saralashga ketgan vaqt:

Tanlash orqali saralash algoritmi: • For i=1 to n-1 • x=a(i) • K=I • For j=i+1 to n • if a(j)< x then • k=j • x=a(k) • endif • Next j • a(k)=a(i) • a(i)=x • Next i return

Almashtirish orqali saralash (Pufaksimon) Algoritm g’oyasi n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ular o‘rni almashtiriladi. Misol:

Almashtirish orqali saralash algoritmi tahlili Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat. Taqqoslashlar soni: O‘rinlashtirishlar soni: Saralashga ketgan vaqt:

Almashtirish usuli uchun psevdokod: • For i=2 to n • for j=n to I step -1 • if a(j)<a(j-1) then • x=a(j-1) • a(j-1)=a(j) • a(j)=x • endif • next j • next I • Return • Bu holatda bitta bo’sh o’tish bo’ladi.Elementlarni ortiqcha almashtirmaslik uchun fl o’zgaruvchi (flajok) kirinish mumkin.

Bu ozgaruvchi agar birorta ham almashtitish bolmasa, false qiymat oladi. Quyida kerakli qo’shimchalar kursiv bilan ko’rsatilgan: • FL=TRUE • For i=2 to n • IF FL=FALSE THEN RETURN • ENDIF • FL=FALSE • for j=n to I step -1 • if a(j)<a(j-1) then FL=TRUE • x=a(j-1) • a(j-1)=a(j) • a(j)= • endif • next j • next I • Return • i.

Купить

Похожие документы
Operatsion tizimlarda journaling file system
I/O scheduling algoritmlari
O‘rta Osiyo kutubxonalarining o‘rganilish masalalari
Funksiyalar va arrow function
Tashkilot xodimlari ma’lumotlarini jamlovchi tizim