Tanlash yoki ajratilgan oraliq asosida saralash usullari - Информатика и ИТ - Курсовые работы

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

Цена	9000UZS
Размер	447.6KB
Покупки	0
Дата загрузки	13 Май 2023
Расширение	docx
Раздел	Курсовые работы
Предмет	Информатика и ИТ

Tanlash yoki ajratilgan oraliq asosida saralash usullari

Купить

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI QARSHI DAVLAT UNIVERSITETI FIZIKA-MATEMATIKA FAKULTETI 5130200-Amaliy matematika va infarmatika yo‘nalishi ALGARITMLAR asoslari fanidan Mavzu: Tanlash yoki ajratilgan oraliq asosida saralash usullari 1KURS ISHI

MUNDARIJA: I. KIRISH. II. ASOSIY QISM. 1. Tanlash va saralash tushunchasi. 2. Tanlash yoki ajratilgan oraliq asosida saralash usull ariga doir masalalar. 3. Selection sort saralash algaritmi. III. XULOSA. IV. FOYDALANILGAN ADABIYOTLAR VA TA’LIM SAYTLARI RO’YXATI 2

KIRISH Dastur so‘zi ham komandalarning alohida blokini (berilgan kodini) aniqlovchi so‘z, ham yaxlit holdagi bajariluvchi dasturiy mahsulotni belgilovchi so‘z sifatida ishlatiladi. Dasturlashga talabni o‘zgarishi nafaqat tillarning o‘zgarishiga balki uni yozish texnologiyasini ham o‘zgarishiga olib keldi. Dasturlash evolyusiyasi tarixida ko‘pgina bosqichlar bo‘lishiga qaramay biz bu kursimizda protsedurali dasturlashdan ob’ektlarga mo‘ljallangan dasturlashga o‘tishni qaraymiz. Keyingi yillarda amaliy dasturchilarga juda ko‘p integratsion dastur tuzish muhitlari taklif etilayapti. Bu muhitlar u yoki bu imkoniyatlari bilan bir–biridan farq qiladi. Aksariyat dasturlashtirish muhitlarining fundamental asosi C++ tiliga borib taqaladi. Vaqt o‘tishi bilan dasturchilar oldiga quyilgan masalalar o‘

ASOSIY QISIM 1. Tanlash va saralash tushunchasi 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 jismoniy tarbiya darslarida talabalar bo`ylariga qarab safda turadi, lekin o`quv jurnalida esa ularning universitetga qabul qilingan o`rni bo`yicha joylashgan. Shu yerning o`zida ikkita saralashdan foydalanilayapti. Birinchisi bo`y uzunligi bo`yicha , ikkinchisi esa o`quv jurnalidagi yozilgan o`rinlari bo`yicha. Saralash – bu berilgan to’plam elementlarini biror bir tartibda joylashtirish jarayonidir. Saralashni maqsadi tartiblangan to’plamda kerakli elementni topishni osonlashtirishdan iborat. Saralash dasturlarni translyasiya qilinayotganda, ma’lumotlar

Saralashni ikkita turi mavjud:  ichki saralash – bu operativ xotiradagi saralash ; tashqi saralash – tashqi xotirada saralash . Saralash bu ma’lumotlarni kalitlari bo’yicha xotirada regulyar ko’rinishda joylashtirishdir . Regulyarlik deganda ma’lumotlar kalit qiymatlari bo’yicha massivda boshidan oxirigacha o’sishi yoki kamayishi tushiniladi. Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi. Ushbu sarfni kamaytishi maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi. Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi. Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralanagandan key

Faraz qilaylik, N = 0,01n 2 + 10n – taqqoslashlar soni. Agar n < 1000 bo’lsa, u holda ikkinchi qo’shiluvchi katta, aks holda ya’ni, n > 1000 bo’lsa, birinchi qo’shiluvchi katta bo’ladi. Demak, kichkina n larda taqqoslashlar soni n ga teng bo’ladi, katta n larda esa n 2 ga teng bo’ladi. Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi: 0(n log n) dan 0 (n 2 ) gacha; 0 (n) – ideal holatda. Saralashni quyidagicha usullari bor :  qat’iy ( to’g’ridan-to’g’ri ) usullar . yaxshilangan usullar . Qat’iy usullar : 1. to’g’ridan-to’g’ri qo’shish usuli . 2. to’g’ridan-to’g’ri tanlash usuli . 3. to’g’ridan-to’g’ri almashtirish usuli. Yuqorida keltirilgan uchala usulda ham almashtirishlar soni deyarli bir hil bo’ladi. To’g’ridan-to’g’ri qo’shish usuli bilan saralash Bunday usul karta o’yin

Faraz qilaylik, kalit qiymati 4, 5, 3, 8, 1, 7 bo’lgan elementlar berilgan bo’lsin. Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. Taqqoslashlar amalga oshirish mobaynida, navbatdagi a(j) element bilan solishtiriladi, keyin esa x bo’sh joyga qo’yiladi yoki a( j ) o’nga suriladi va jarayon chapga “ketadi”. Shuni e’tiborga olish lozimki, saralash jarayoni quyidagi shartlarni birortasi bajarilganda yakunlanadi:  x elementi kalitidan kichik kalitli a(j) element topildi .  tayyor ketma-ketlikning chap tomoni oxiriga yetib borildi . algoritm samaradorligi Faraz qilaylik, taqqoslashlar soni S, o’rinlashtirishlar soni M bo’lsin. Agar massiv elementlari kamayish tartibida bo’lsa, u holda taqqqoslashlar soni eng katta bo’lib, u Cmax = n(n−1) 2 ga teng bo’ladi, ya’ni

1. Berilgan elementlar 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 . A lgoritm samaradorligi : Taqqoslashlar soni M = n 2 (n− 1)= n2− n 2 . Almashtirishlar soni C min = 3(n - 1), C max = 3(n - 1) n 2 (n 2 tartib ). Ushbu usul bo’yicha saralash bajarilsa, eng yomon xolda taqqoslashlar va almashtirishlar soni tartibi n 2 bo’ladi . To’g’ridan-to’g’ri almashtirish usuli bilan saralash ( pufaksimon ) Ushbu usulni g’oyasi quyidagicha: n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi juft

A lgoritm samaradorligi : taqqoslashlar soni M = n 2 ⋅n 2 = n2 4 , almashtirishlar soni C max = 3 n2 4 . Saralash jarayoni qanday bo`ladi degan savolga javob berishga urinib ko`ramiz. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanar ekan. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma – bir tahlil qilib chiqamiz. Buning uchun saralanmagan (tartiblanmagan) sonlar ketma ketligini olamiz: Quyidagi sonlar berilgan bo`lsin: 23, 54, 3, 22, 1, 45; 1. Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54; 2. Yana 1-da qilgan ishimizni takrorlaymiz: 3, 22, 1, 23, 45, 54; 3. Yuqoridagi amalni yana bajaramiz: 3, 1, 22, 23, 45, 54; 4. Oxirgi marta almashtiramiz: 1, 3, 22, 23, 45, 54; Demak miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma’lum

dasturi ishlash prinsipini eslashimiz kifoya. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Hozirgi tizimlarda esa 30% emas anchagina kamroq tezlik va xotira sarflanadi. Chunki tezlik masalasi tobora yuqoriga chiqayotgan va ishlanayotgan ma’lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish maqsadga muvofiq emas. Ma’lumotlar o`lchami juda katta, shu sababli 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. Kalitli so’zlar: saralash, ichki saralash, tashqi saralash, regulyarlik, saralash samaradorligi, qo’shish or

2.Tanlash yoki ajratilgan oraliq asosida saralash usullariga doir masalalar Bubble sort Bubble sort saralash algoritmi qanday usulda saralash? Ushbu so`z pufakcha usulida saralash degan ma’noni anglatadi. Bu saralash usulida massiv elementlarining ikki qo`shni elementlari taqqoslanadi va agarda noto`g`ri joylashgan bo`lsa ularnung o`rinlari almashtiriladi. Umumiy n-1 marta ushbu jarayon bajariladi. Har safar ikkita qo`shni element taqqoslanadi. Yuqoridagi jarayonda har bir element o`z o`rniga siljib boradi xuddi suvdagi pufakchaga o`xshab. Shu sababli ham uning nomi pufakcha usulida saralash deb nomlanadi. Bu algoritmning asosiy g‘oyasini yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «y

using namespace std; int main(){ int a[100], i, j, n, t; cin>>n; for(i=0; i<n; i++) cin>>a[i]; for(i=n; i>=1; i--) { for(j=0; j<i-1; j++) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } for(i=0; i<n; i++) cout<<a[i]<<" "; return 0; } Insertion sort Yana bir saralash usuli insertion sort bo`lib, u ham massiv elementlarini saralashda qulay usullardan biri hisoblanadi. Insertion sort saralash algoritmida asosan boshidan boshlab 2 ta elementini keyin 3 ta so`ngra 4 ta va hakozo n ta elementni tartiblanadi. (1) - qadamda dastlabki 2 ta element tartiblanganda faqat 2 ta element, (2) - qadamda 3 ta element tartiblanganda esa 3 - element dastlabki 2 tasi bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 tasi bilan va hakozo ( n -1) - qadamda n ta element tartibl

int main() { int *a, i, n, j, m; cin >> n; a=new int [n]; for(i=0; i<n; i++) cin>>a[i]; for(i=1; i<n; i++) { j=i; while(j>0&&(a[j]<a[j-1])) { m=a[j]; a[j]=a[j-1]; a[j-1]=m; j--; } } for(i=0; i<n; i++) cout << a[i] << " "; delete []a; return 0; } 3. Quick sort Quicksort saralash algoritmi bu tezkor saralash degan ma’noni anglatadi. Tezkor saralash ( Quick sort ) algoritmi 1964 - yilda Charlz Hoar tomonidan taklif qilingan. Charliz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “ Tezkor saralash ” algoritmi saralash bo`yicha eng ommabop algoritm. 13

Bu algoritm ham “ Bo`lib tashla va hukmronlik qil “ ( Bu metod algoritmlarni qurishning asosiy metodlaridan biri. Murakkab masalani yechish uchun uni oddiyroq bo`laklarga ajratish kerak. Massivni ham xuddi shunday saralash mumkin . buning uchun uni ikki bo`lakka ajratamiz, bo`laklarni alohida saralaymiz, saralangan massivlarni birlashtiramiz ) metodiga asoslanadi. Algoritmining g`oyasi: Massivda bo`luvchi element x dan kichik yoki teng bo`lgan elementlar joylashsin, keyin undan katta bo`lgan elementlar joylashsin. Keyin ularni alohida saralaymiz. Agar a massivda n ta element bo`lsa, bo`luvchi element sifatida x=a[n/2] ni olamiz. Chap tomondan x dan kichik katta yoki teng bo`lgan birinchi elementni topamiz, o`ng tomondan esa x dan katta bo`lmagan birinchi elementni topamiz va ikkalasining o

i=l; j=r; while(i<=j){ while(a[i]<x) i++; while(a[j]>x) j--; if(i<=j) { t=a[i]; a[i]=a[j]; a[j]=t; i++; j--;} } if(l<j) qsort(l,j); if(i<r) qsort(i,r); } int main() { int i, n; cin>>n; for(i=0; i<n; i++) cin>>a[i]; qsort(0,n-1); for(i=0; i<n; i++) cout << a[i] << " "; return 0; } 15

3. Selection sort saralash algaritmi Selection sort alagaritmi – bu tanlash algoritmidir. Tanlash algoritmi saralash algoritmlarining eng oddiy saralash usuli hisoblanadi. Ushbu saralash algoritmi ro’yhatning ikki qismga bo’linadigan qismi, chap tomonning oxiridagi qismi va o’ng tomonning ajralmas qismiga bo’linadigan joylarda taqqoslashga asoslangan saralash algoritmidir. Dastlabki holda, tartiblangan qism bo’sh va sarlavha qilinmagan qism butun ro’yhat hisoblanadi. Eng kichik eliment unsorted qatordan tanlanadi va eng chap element bilan almashtiriladi va bu element tartiblangan qatorning bir qismiga aylanadi. Ushbu jarayonni bajarish tartibsiz qator qatorni o’nga bir element bilan harakat qilishni davom ettiradi. Uishbu saralash algaritmi juda katta malumotlar majmui uchun mos emas, chun

Agar belgilangan massiv a[i] ( bu yerda i=0 ) elementi bilan undan keyin turgan ixtiyoriy a[j] ( j>i ) element a[i]>a[j] shartni qanoatlantirsa t ga j qiymatlanadi va ikkala massiv elementlari o’rni almashadi: Keying qadamlarda xuddi yuqoridagi jarayon takrorlanadi. Faqat har safar i ning qiymati oshib boradi. Ya’ni quyidagicha: Quyida tanlash asosida saralash algoritmining dastur matnini C++ dasturlash tilida keltirib o’tamiz: #include <iostream> using namespace std; int main() { int *a, i, j, buf, n, t; cin>>n; a=new int[n]; for(i=0; i<n; i++) 181 8 10 2 4 1 8 10 2 4 1 2 10 8 4 1 2 10 8 4 1 2 4 8 1045 3938

cin>>a[i]; for(i=0; i<n-1 ; i++) { t=i; for(j=i+1; j<n; j++) { if(a[t]>a[j]) { t=j; } } buf=a[t]; a[t]=a[i]; a[i]=buf; } for(i=0; i<n; i++) cout << a[i] << " "; delete []a; return 0; } Dastur izohi: dastur C++ dasturlash tilining kompyuterlar uchun mo’ljallangan versiyalarida ishga tushirilgach hosil bolgan qora fondagi doskaga dastlab massiv elementlari soni n so’ngra n ta massiv elementini kiritamiz. Massivning birinchi elementi bilan qolgan barcha elementlarni taqqoslab chiqamiz. Agarda massivning birinchi elementi qolgan barcha elementlarni 19

ixtiyoriysidan katta bo’lsa u holda bu elementlar urni almashadi. Kiyingi qadamda ikkinchi element bilan undan kiyin turgan elementlarni taqqoslaymiz. Kiyingi qadamda uchinchi element va hakozo oxirgi qadamda n-1 birinchi element bilan n-element taqqoslanadi. Har qadamda taqqoslash sharti bajarilsa taqqoslangan elementlar o’rni almashadi va bu jarayon taqqoslash sharti bajarilmay qolguncha davom etadi . Dastur natijasi quyidagicha bo’ladi: XULOSA 20

Xulosa qilib shuni aytishim mumkinki, bu mavzuda men massiv elementlarini saralash usullarining ichida quicksort ya’ni tez saralash algoritmining qaysidir sohalarda boshqa usullarga nisbatan qulaylik tomonlari bilan ajralib turishini ko`rsatishga harakat qildim. Bundan tashqari, ya’ni quicksort algoritmidan tashqari saralash algoritmlaridan bubble sort saralash algoritmi, insertion sort saralash algoritmlarini tushuntirishga harakat qildim. Ushbu saralash algoritmlarining dasturlarini c++ tilida yozganligim uchun bu saralash algoritmlariga yanada ko`proq ko`nikma hosil qildim. Hali sanashni bilmay turib sonlar ustida arifmetik amallar bajarib bo`lmaganidek, men ham ushbu kurs ishidagi asosiy qismning birinchi bo`limida massivlar haqida kengroq to`xtalib o`tdim. Ikkinchi bo`limda esa sarals

1. Bjarne Stroustrup . The C++ Programming Language (3th Edition). Addison- Wesley, 1997. 2. Gerbert Shildt. "Java. Polnoye rukovodstvo" 8-ye izdaniye. Yazik russkiy. - M.: Izdatelskiy dom "Vilyams", 2012, — 1104 s. 3. D.S. Malik. C++ Programming: From Problem Analysis to Program Design. Fifth Edition. Course Technology, 2011. 4. Madraximov SH.F., Gaynazarov S.M. C++ tilida programmalash asoslari// Toshkent, О‘zMU, 2009, 196 bet. 5. Madraximov Sh.F., Ikramov A.M., Babajanov M.R. C++ tilida programmalash boyicha masalalar to’plami. O’quv qo’llanma // Toshkent, O’zbekiston Milliy Universiteti, “Universitet” nashriyoti, 2014. - 160 bet. Qо‘shimcha adabiyotlar : 6. Bjarne Stroustrup . The C++ Programming Language (4th Edition). Addison- Wesley, 2013. 1363 page. 7. Bjarne Strous

14. Kultin N.B. C++Builder v zadachax i primerax.-SPb.: BXV-Peterburg, 2005.-336 s. 15. Abramov S.A., Gnezdelova Kapustina YE.N. i dr. Zadachi po programmirovaniY. - M.: Nauka, 1988. Internet saytlari : 1. http://cppstudio.com – C++ tilida programmalash b о‘ yicha namunalar izo h lari bilan keltirilgan. 2. http://cplusplus.com – C++ tilida mavjud konstruksiyalar ta’rifi, ishlatish namunalari bilan keltirilgan. 3. http://www.compteacher.ru/programming - dasturlash bо‘yicha video darsliklar mavjud. 4. http:// www.intuit.ru – internet universitet, dasturlash bо‘yicha yozma va video ma’ruzalar о‘qish, test sinovlaridan о‘tish va sertifikat olish imkoniyati mavjud. 5. http:// www.ziyonet.uz – dasturlash asoslari bо‘yicha referatlar topish mumkin. 23

Купить

Похожие документы
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