Quick sort saralash algoritmi - Информатика и ИТ - Курсовые работы

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

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

Quick sort saralash algoritmi

Купить

MUNDARIJA I. KIRISH. II. ASOSIY QISM. 1. Massivlar tushunchasi. 2. Massiv elementlarini saralash va saralash usullari haqida. 3. Quicksort saralash algoritmi. III. XULOSA. IV. FOYDALANILGAN ADABIYOTLAR VA TA’LIM SAYTLARI RO’YXATI. 1

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‘

1. Massivlar tushunchasi. Ko’p hollarda, bir necha sonlarni yoki o’zgaruvchilarni bitta nom ostida tizib chiqishga to’g’ri keladi. Buning uchun quyidagicha tartibda ish bajariladi. Bu sonlar bitta to’plamga (massivga) tizib chiqiladi va unga biror nom beriladi. Bu to’plam (massiv)ga kirgan har bir o’zgaruvchi massivning elementi deb yuritiladi. Massivning elementlari massivda tizilgan o’rniga qarab nomerlab chiqiladi va bu nomerlar massiv elementlarining indeksi deb yuritiladi. Massivga murojaat qilinayotganda, massiv nomi ko’rsatiladi va uning yoniga [] qavslar ichiga bu massivning jami elementlar soni ham yozib qo’yiladi. Massivga kirgan har bir o’zgaruvchi ham massiv nomi bilan yuritiladi va nom yoniga uning bu massivdagi tartib raqami ham yozib qo’yiladi. Massivlardan dastur tuzishda f

o’lchovli massivlar qo’llaniladi. Bir o’lchovli massivlarga matematikada vector tushunchasi mos keladi. Massivning int z[3] shaklidagi ta’rifi, int tipiga tegishli z[0], z[1], z[2] elementlaridan iborat massivni aniqlaydi. Massivlar ta’riflanganda inistilizatsiya qilinishi, ya’ni boshlang’ich qiymatlari ko’rsatilishi mumkin. Misol uchun: float C[]={1,-1,2,10,-12.5};Bu misolda massiv chegarasi avtomatik aniqlanadi. Agar massiv inistilizatsiya qilinganda elementlar chegarasi ko’rsatilgan bo’lsa, ro’yhatdagi elementlar soni bu chegaradan kam bo’lishi mumkin emas. C+ + tilida massivlar quyidagicha berilishi mumkin so’zlar massivlari, ko’rsatgichlar massivlari, funksiya va massivlar, simvolli massivlar, satrli massivlar, ko’rsatgich va massivlar.C++ tilida so’zlar massivlari ikki o’lchovda simv

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 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,

oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Ular quyidagilar: 1. Bubble sort saralash algoritmi 2. Selection sort saralash algoritmi 3. Insertion sort saralash algoritmi 4. Quick sort saralash algoritmi 5. Merge sort saralash algoritmi 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 majmuasini tashqi xotirada tashkil qilinayotganda, kutubxonalar, kataloglar, ma’lumotlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki, saralashning turli hil algoritmlari mavjud. Sababi, bitta masalani saralash uchun jud

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 keyin bir hil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, ushbu tartibda qoldirilishi maqsadga muvofiq bo’ladi (Bir hi

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’yinida keng qo’llaniladi. Elementlar (kartlar) hayolan “tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi. Taklif qilinayotgan usulni quyidagi misolda ko’rib chiqamiz. Faraz qilaylik, kalit qiymat

 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 O(n2) . O’rinlashtirishlar soni esa M max =Cmax +3(n−1) ga teng bo’ladi, ya’ni O(n2) . Agar berilgan massiv o’sish tartibida saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi, ya’ni Cmin =n−1 , M min =3(n−1) . To’g’ridan-to’g’ri tanlash usuli bilan saralash Faraz qilaylik, a 1 , a 2 , … , a n elementlar ketma-ketligi berilgan bo’lsin. Mazkur usul quyidagi tamoyillarga asoslangan: 1. Berilgan elementlar

Ushbu usulni g’oyasi quyidagicha: 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. Pufaksimon usulni yaxshilangan usuli bu sheyker saralash usuli bo’lib, har bir o’tishdan keyin sikl ichida yo’nalish o’zgartiriladi . A lgoritm samaradorligi : taqqoslashlar soni M = n 2⋅n 2= n2 4 , almashtirishlar soni C max = 3 n2 4 . Quyida biz ushbu saralash algoritmlaridan bir nechtasini ko`rib o`tamiz, shuningdek quick sort saralash algoritmiga keying rejamizda alohida to`xtalib o`tamiz va tushunishga harakat qilamiz. Bubble sort saralash algoritmi qanday usulda saralash? Ushbu so`z pufakcha usulida saralash degan ma’noni anglatadi. Bu saralash usulida massiv

ular yuqoriga «suzib chiqadi». Massiv bo‘ylab birinchi o‘tishda massivning birinchi yozuvi olinadi va uning kaliti navbatma-navbat keyingi yozuvlarning kalitlari bilan solishtirib boriladi. Agar nisbatan «og‘ir» kalitli yozuvlar uchrasa, u holda bu yozuvlar joyini almashtiradi. Nisbatan «yengil» yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi va keyingi barcha yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit massivning eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi kalit olinadi. Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda topilgan yozuvlarni ko‘rib chiqish shart emas, chunki ular qolgan yozuvlarga qaraganda kichik kal

tasi bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 tasi bilan va hakozo ( n -1) - qadamda n ta element tartiblanganda n - element dastlabki n tasi bilan taqqoslanadi. Bizning maqsad ham shu oxirgi qadamda bajarilgan vazifa ya’ni n ta elementni saralashdan iborat edi. Buni osonroq tushunish uchun quyidagi misolni keltiramiz: Endi esa ushbu saralash algoritmining dasturini keltiramiz: #include <iostream> using namespace std; int main() { int *a, i, n, j, m; 126 7 3 84 6 7 3 84 (1) 6 7 3 84 (2) 3 6 7 84 3 6 7 84 (3) 3 4 6 87 3 4 6 87 (4) 3 4 6 8734 2E 34 2E 2C 2C 34 2E 2C 34 2E 2A 2C 2A 34 2E 2C 2A 34 2D 2E 2C 2A 34 2D 2E

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; } 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 aylana

using namespace std; int main() { int *a, i, j, buf, n, t; cin>>n; a=new int[n]; for(i=0; i<n; i++) 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 ixtiyoriysidan katta bo’lsa u holda bu elementlar urni almashadi. Kiyingi qadamda ikkinchi element bilan undan kiyin turgan elementlarni taqq

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: 3. Quicksort saralash algoritmi 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 15

ommabop algoritm. –––– 169 3 7 5 2 1 4 4 3 7 5 2 1 99 3 7 5 2 1 4 4 3 1 5 2 7 9 4 3 1 2 5 7 9 4 3 1 2 5 7 9 2 3 1 4 2 1 3 4 1 2 3 436 2C 2E 2B 23 1B 2A 2A 2C 2E 2B 23 1B 36 36 2C 2E 2B 23 1B 2A 2A 2C 1B 2B 23 2E 36 2A 2C 1B 23 2B 2E 36 2A 2C 1B 23 2B 2E 36 23 2C 1B 2A 23 1B 2C 2A 1B 23 2C 2A

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++; 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; } Dastur natijasi quyidagicha bo’ladi: 18

X ulosa. 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. 19

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 saralsh algoritmlarining turlari va ularning bir - biridan farqi haqida kengroq tushunchalar keltirib o`tdim. Va nihoyat uchinchi bo`limda kurs ishining asosiy qismini, quick sort saralash algoritmi va uning dasturini yozdim. Foydalaniladigan adabiyotlar rо‘yxati : 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. Cour

6. Bjarne Stroustrup . The C++ Programming Language (4th Edition). Addison- Wesley, 2013. 1363 page. 7. Bjarne Stroustrup . Programming: Principles and Practice using C++ (Second Edition)" Addison-Wesley , 2014, 1305 page. 8. Pavlovskaya T.A. C++. Programmirovaniye na yazike visokogo urovnya – SPb.: Piter. 2005.- 461 s. 9. Xorstmann K.S., Kornell G. - Java 2. Tom 1. Osnovi Java. M.: Vilyams, 2007. - 896 s. (7 izdaniye) . Biblioteka professionala. Per. s angl. 10. Xorstmann K.S., Kornell G. - Java 2. Tom 2. Tonkosti programmirovaniya, M.: Vilyams, 2014. -1874s. - 9-ye izd. 11. P.J. Deitel, H.M. Deitel. Java: how to program. NJ:Prentice Hall, --9th edition. 2012 12. Pavlovskaya T.S. Shupak Y.S. S/C++. Strukturnoye programmirovaniye. Praktikum.-SPb.: Piter,2002-240s 13. Glushakov S.V., Ko

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. 22

Купить

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