Amaliy matematika va informatika fakulteti Tabiy va aniqfanlar kafedrasi Algoritim fanidan kurs ishi mavzu: Pufakchali saralash algoritimi, “ Bubble sort ”algoritimi. Bajardi
Download 1.59 Mb.
|
Pardayev dilmuroning algoritimdan kurs ishi.
|
Denov tadbirkorlik va pedigokika instituti. 
O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TALIM VAZIRLIGI Denov tadbirkorlik va pedigokika instituti Amaliy matematika va informatika va informatika fakulteti Tabiy va aniqfanlar kafedrasi Algoritim fanidan KURS ISHI Mavzu: Pufakchali saralash algoritimi , “ Bubble sort ”algoritimi. BAJARDI: PARDAYEV D. TEKSHIRDI: XOLBEKOV A . Mavzu: Pufakchali saralash algoritimi , “ Bubble sort ”algoritimi. Reja: I. Kirish II. Asosiy qisim 2.1) Saralash haqida tushuncha. 2.2) Saralash xossalari va ularning sinflari. 2.3)Pufakchali saralash (Bubble sort) algoritimi. III. amaliy qisim IV. Xulosa V. Foydalanilgan adabiyotlar I. Kirish Saralashdan biz kundalik hayotmizda ko’p foydalanamiz. Masalan bazordan biror narsa harid qilishimizda, uning ko’proq narxi bilan qiziqamiz yoki ularni taqqoslaymiz. Bu narsalar bizga oddiy hodisa bo’lib qolgan, lekin biz siz bilan bu jarayon qanaqa miyamizda xosil bo’layotganligini bir o’ylab ko’raylikchi. Demak oddiygina biz kunda faydalnayotgan xarakatlarimizni dasturini tuzish uchun ko’p narsalarni bilishimiz va aniq bir maqsadga yo’naltirgan tartiblangan qoidalar yig’indisi zarur bo’ladi. Agar ma’lumotlar kampyuter xotirasida muayyan tartibda saqlanadigan bo’lsa, axborotga ishlov berish va uni izlash bilan bog’liq ko’p masalalar oddiyroq, tezroq va samaraliroq xal qilinadi. Bir qator xollarda ma’lumotlarning tartibga solinganligidan foyda aniq bo’lib, maxsus isbotlashlarni talab etmaydi. Agar lug’at yoki telefon ma’lumotnomasida so’zlar va familiyalar alifbo tartibida joylashtirilmaganda ulardan foydalanish qanchalik qiyin bo’lishini tasavvur etish mumkin. lekin ma’lumotlarni saralash zaruriyati masalasi xar safar muoyyan vazifasiga nisbatan xal qilishi zarur. Bunda tashqi xotira qurulmalari imkoniyatlari, opetativ xotira xajmi, ma’lumotlarga murojaat qilish tezligi, ularni yangilab turish tezligi va ishlov berish xarekteri kabilarni taxlil qilish zarur. Turli ilovalarda tartibga solishning turli mezonlaridan foydalaniladi. Ma’lumotlarularga murojat qilish extimolining qiymati, qancha tez-tez murojat etib turishiga ko’ra tartibga solishi mumkin. Odatda, tartibga solish yozuv bo’yicha amalga oshiriladi.Axbotot tizimlari bilan ishlov beriladigan ma’lumotlar birligi bir qator axborot maydonidan iborat bo’lgan yozuv xisoblanadi. Yozuv faqat bittagina maydondan iborat bo’lishi mumkin va bu xolda u kalitli hisoblanadi. Tartibga solish natijasida yozuvlar kalitlarning qiymati ortib borishi yoki kamayib borish tartibida joylashadi. Bunday tartibga solish jarayoni saralash deb ataladi. Masalan fakultet talabalaridan to’g’risidagi ma’lumotlardan iborat bo’lgan yozuvlar talabalarning reyting daftarchalari nomerlari bo’yicha tartibga solingan bo’lishi mumkin. Yozuvlar dastlabki ketma-ketligi turli darajada tartibga solingan bo’lishi mumkin. Balki yozuv elementlari belgilangan tartibda joylashgan bo’lishi mumkin.Boshqa bir xolatda elementlarga teskari, yani yozuvlarning dastlabki ketmeketligi teskari tartibda joylashgan bo’lishi mumkin. Yozuvlarning dastlabki ketma-ketligining qanday tartibda joylashganlik darajasiga ko’ra, solishtirishlar va joyini o’zgartirishlarning u yoki bu soni talab etiladi. Saralash usulini boxolashda solishtirishlar va o’rnini o’zgartirishlarning eng ko’p va kam sonlarini topish juda oson. Bu operatsiyalarning o’rtacha sonini aniqlash uchun kombinatorikaning tegishli bo’limlarini jalb etish zarur. Odatda, saralash jarayonida bajariladigan solishtirish operatsiyalarining o’rtacha soni va elementlarining o’rnini almashtirish yoki o’zgartirishning o’rtacha soni turli usullarni baxolash mezonlari xisoblanadi. Saralash samaradorligi solishtirishning o’rtacha soniga bo’linmasi sifatida aniqlanadi. EXM larning operatsiyon tizimlari, xech bo’lmaganda, bitta dastur – saralash utilitasidan iborat bo’ladi. Lekin ma’lumotlarga ishlov berishning muayyan vazifalarini xal qilishda utilita taklif etilayotgan usil yoroqsiz bo’lishi va boshqa usilni ishlab chiqish yoki foydalanishga to’g’ri kelishi mumkin. Shu munasabat bilan saralashning asasiy usillarini bilish va muayyan vazifa uchun yoroqli bo’lgan u yoki bu usilni baxolay olish muximdir. 2.Saralash haqida tusuncha Saralash va izlash amalda juda ko’p qo’llaniladi, fayldagi so’zlarnini izlash-dan tortib, internetda ma’lumot izlashgacha. 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 maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2ta saralashdan foydalanilyapti. Biri, bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalidagi o`rinlar bo`ycha saralash jarayoni qanday kechadi? 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; 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 turipti) Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54; (23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54; (22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54; (1 eng kichigi) Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma`lumki, bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ldi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralshdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Saralash va izlash amalda juda ko’p qo’llaniladi, fayldagi so’zlarnini izlashdan tortib, internetda_ma’lumot izlashgacha. Saralash. a[0], a[1], a[2] .. a[n-1] massiv elementlari berilgan. Ularni shunday joylashtirish kerakki, ular kamaymaslik tartibida bo’lib qolsin. Masalan: 5 8 9 1 5 2 3 9 Saralangandan so’ng 1 2 3 5 5 8 9 9 Saralash algoritmlari ikki tipga bo’linadi. 1.O(N) vaqtda saralovchi algortimlar. 2.O(n•log(n)) vaqtda saralovchi algoritmlar. Algoritmlarda log(n) bu. n= bo’lganda taqqoslang: O() =, O(n•log(n)) = 1660964. Vaqt – bu algoritmni tezligini xarakterlovchi asosiy parametr. Bu albatta hisoblash murakkabligi bilan bog’liq.
Bo’lishi mumkin. O(n log n)– baho algoritmni o’rta xulqi hisoblanadi. O(n2) – baho algoritmni yomon xulqini aks ettiradi. O(n)– baho algoritmni yaxshi xulqini aks ettiradi. Algoritmlar quyidagilar bilan farq qiladi. Ishlash vatqi 0 ( Taqqoshlashlar soni 0 ( Almashtirishlar soni. 0(N) Qo’shimcha xotira. 0(1) 2.1 Saralash xossalari va ularning sinflari Turg’unlilik (stability) Tabiy xulqlilik– algoritm o’zini tabiy holdagidek tutadi. Agar kiritiladigan ketma-ketlikdagi bu xarakteristikani xisobga olsa va yaxshi ishlasa u tabiiy xulqli deyiladi. Turg’un saralash algoritmlari. 1. Tanlashni saralash (Selection sort) – algoritm murakkabligi O(n2) 2. Ko’pikli saralash (Bubble sort) – algoritm murakkabligi O(n2). 3. Aralashtirish saralashi (SHeyker, Cocktail sort, bidirectional bubble sort) - algoritm murakkabligi O(n2) 4. O’rniga qo’yish saralashi (Insertion sort) – algoritm murakkabligi O(n2) 5. Qo’shilish saralashi (Merge sort) – algoritm murakkabligi O(n logn) 6. Ikkilik daraxti yordamida saralash (Tree sort) – algoritm murakkabligi
7. Timsort saralashi (Timsort) – algoritm murakkabligi O(n log n) qo’shimcha O(n) xotira talab etadi. 8. Sanash orqali saralash (Counting sort) – algoritm murakkabligi O(n+k) Qo’shimcha O(n) xotiratalabetadi. 9. Blokli saralash (Savatli saralash, Bucket sort) – algoritm murakkabligi O(n) Qo’shimcha O(k) xotira talab etadi.
1.Tanlash orqali saralash (Selection sort) algoritm murakkabligi O(n2) 2. Shell saralash (Shell sort) algoritm murakkabligi O(n log2n). 3. Tarash orqali saralash (Comb sort) algoritm murakkabligi O(nlogn) 4. Suzuvchi saralash (Smooth sort) algoritm murakkabligi O(n logn) 5. Tez saralash (Quick sort) algoritm murakkabligi O(nlogn) 6. Intro sort – algoritm murakkabligi O(nlogn) 7. Patience sorting – algoritm murakkabligi O(nlogn) 8. Stooge sort – algoritm murakkabligi O(n2.71) 9. Razryadli saralash. Algoritm murakkabligi O(n+k). O(k) qo’shimcha xotira talab etiladi. Amaliy bo’lmagan saralash 1. Bogosort – algoritm murakkabligi O(n n!). 2. O’rinlashtirish saralash – algoritm murakkabligi O(n n!). 3. Ma’nosiz saralash (Stupid sort) – algoritm murakkabligi O(n3). 4. Bead asort – Algoritm murakkabligi O(n) yoki O(sqrt(n)). Maxsus apparat taminoti talab etiladi. 5.Quymoqli saralash (Pancake sorting) – Algoritm murakkabligi O(n). Maxsus apparat taminoti talab etiladi. Ko’rib turubsiz saralash algaritimlari juda ko’p turlari mavjud. Shulardan bazi birlari birlari bilan tanishib chiqamiz. Qiyin, lekin samarali usullar «tezsaralash» (Quick Sort) «to’p-to’p» saralash (Heap Sort) Qo’shilib saralash Piramidali saralash Algaritm murakkabligi O(N*logN) Birlashmali saralash (Merge Sort) Bu algoritm Jon Fon Neyman tamonidan 1946 yilda taklif qilingan. Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz,to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan. Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi. Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta yutuq qilish imkonini beradi.Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi. Keling ushbu massivni qaraylik: Uni teng ikkiga ajratamiz Va yana har bir qismni ikkiga ajratamiz, toki 1 elementli qismlar qolmagunicha:Massivni maksimal qisqa qismlarga ajratgandan so`ng, ularni to`g`ri tartibda birlashtiramiz, ya'ni:Dastlab, 2 elementli saralangan guruhlarni olamiz va ularni 4 elementli guruhlarga birlashtiramiz va yakunida hammasini birlashtirgan holda saralangan massivni hosil qilamiz. Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak: Massivni guruhlarga rekursiv ajratish amali ( sort). To`g`ri tartibda birlashtirish amali (merge). Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi. #include #include #include using namespace std; int a[100000], b[100000]; void mergesort(int L, int R) { if (L >= R) return; else { int m = (L+R) / 2; mergesort(L, m); mergesort(m+1, R); //Birlashtirish yoziladi } } int main() { int n; cin>>n; for (int i = 0; i < n; i++) cin>>a[i]; mergesort(0, n-1); for (int i = 0; i < n; i++) cout< return 0; } Tez saralash (quicksort) Tez saralash (quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzog’i bilan O(n2) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi. Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o’rtacha N*log2N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo’lib oladi. Bo’lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi. Lekin o’rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma’qul. Tanlangan kalit elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o’ng tomonga o’tkaziladi (6.3-rasm). Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya’ni bu oraliqlarning o’rtasidagi elementlar kalit sifatida olinadi va h.k. Misol uchun rasmdagi massivni saralash algoritmini ko’rib chiqamiz. 1. Oraliq sifatida 0 dan n-1 gacha bo’lgan massivning barcha elementlarini olamiz. 2.Oraliq o’rtasidagi kalit elementni tanlaymiz, ya’ni key = ( < oraliq_boshi > + < oraliq_oxiri > ) / 2, i=, j=. Quicksort algoritimida o’rinlashtrish. 3. Chapdagi i-elementni key bilan solishtiramiz. Agar key kichik bo’lsa, keyingi qadamga o’tamiz. Aks holda i++ va shu qadamni takrorlaymiz. 4. O’ngdagi j-element bilan key solishtiriladi. Agar key katta bo’lsa, keyingi qadamga o’tamiz, aks holda j-- va shu qadamni takrorlaymiz. 5. i- va j-elementlarning o’rni almashtiriladi. Agar i<=j bo’lsa, 3-qadamga o’tiladi. Birinchi o’tishdan keyin tanlangan element o’zining joyiga kelib joylashadi. 6. Endi shu ko’rilayotgan oraliqda key kalitning chap tomonida elementlar mavjud bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan oraliq 0 dan key-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda keyingi qadamga o’tiladi. 7. Endi shu ko’rilayotgan oraliqda key kalitning o’ng tomonida elementlar mavjud bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan oraliq key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda algoritm tugaydi. Shu algoritmga misol ko’rib chiqamiz. Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algritmi bilan saralang va nechta o’rinlashtirish amalga oshirilganini aniqlang. Dastur kodi #include #include using namespace std; struct table{ int t;
string FIO; }; int q=0; void qs(table *a,int first,int last){ int i = first, j = last;table x =a[(first + last) / 2]; do {
while (a[i].FIO < x.FIO) i++; while (a[j].FIO > x.FIO) j--; if(i <= j) { if (i < j){ swap(a[i], a[j]);q++;} i++;
j--;
} } while (i <= j); if (i < last) qs(a,i,last); if (first < j) qs(a,first,j); } int main(int args, char *argv[]) { int n;cout<<"n=";cin>>n; table talaba[n]; for(int i=0;i talaba[i].t=i+1; cin>>talaba[i].FIO; } qs(talaba,0,n-1); for(int i=0;i cout< cout<<"quicksort algoritmi "< saraladi\n"; system("PAUSE"); }
Dastur natijasi: 5 ta talabalar FIO sini kiriting Farhod , Asror, Sobir, Bobur ,Vali | 2 | Asror |
| 4 | Bobur | | 1 | Farhod |
| 3 | Sobir | | 5 | Vali | bu algoritm jadvalni 3 ta o‘rinlashtirishda saraladi
1. Jadvalga talabalar ism-sharifini kiritamiz. 2. Jadvaldagi 1-elementni olamiz, i=0.
3. Jadvaldagi n-1 oxirgi elementdan to i-elementgacha barcha elementni FIO maydonini o’zidan oldin turgan element FIO maydoni bilan solishtiramiz. Agar zarur bo’lsa, o’rin almashtiramiz va o’rin almashtirishlar hisoblagichi l ning qiymatini bittaga oshiramiz, ya’ni l++. 4. Agar i
5. Natijaviy saralangan massivni ekranga chiqaramiz. #include #include using namespace std; int main(int args, char *argv[])
{
struct table{
int t;
} talaba[n]; cout< for(int i=0;i talaba[i].t=i+1;
cin>>talaba[i].FIO; }
int l=0; for(int i=0;i
for(int j=n-1;j>i;j--){ if (strcmp(talaba[j-1].FIO,talaba[j].FIO)==1){
l++;
talaba[j]=talaba[j-1]; talaba[j-1]=k;
}
}
cout<<"| "< cout<<"bu algoritm jadvalni "< saraladi\n"; system("PAUSE"); }
Dastur natijasi: talabalar sonini kiriting=5
5 ta talabalar FIO sini kiriting Farhod
Asror
Bobur
| 4 | Bobur | | 1 | Farhod |
| 3 | Sobir | | 5 | Vali |
Bu algoritm jadvalni 10 ta solishtirishda saraladi Shel saralashi ( qisqarib boruvchi qadamlar orqali saralash ) to’g’ri qo’shish usulini 1959-yilda D. Shell tomonidan mukammallashtirish taklif qilingan: quyidagi chizmada ushbu usul tasvirlangan.Boshida bir biridan 4 qaddam joylashgan elementlar o’zaro guruhlanib saralash amalga oshiriladi. Bunday jarayon to’rtlik saralash deb ataladi. Birinchi o’tishdan keyin elementlar qayta guruhlanib endi har ikki qadamdagi elementlar taqqoslanadi. Bu esa ikkilik saralash deb nomlanadi va nihoyat uchinchi o’tishda oddiy yoki yakkalik saralash amalga oshiriladi Birqarashda mazkur usul bilan saralash amalga oshirilganda saralash jarayoni kamayish o’rniga ortib boradigandek tuyulsada elementlarini o’rin almashtirishlar nisbatan kam amalga oshiriladi .Ko’rinib turibdiki bu usul natijasida tartiblangan massiv hosil bo’lib har bir o’tishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi. Misol : massiv - 4, 3, 7, 2, 1, 6 Pufaksimon saralash usulida massiv elementlarining o’rnini almashtirish Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin. “Pufaksimon” saralash usulini hisoblashga misol Massivni pufaksimon saralashga misol berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o’tishlar soni 5-1=4 marta bo’ladi. Misoldan ko’rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta ishlaydi,
4-qadamni bajarmasa ham bo’ladi. Berilgan usullarning afzalligi:
1) Eng sodda algoritm; 2) Amalga oshirish sodda;
3) Qo’shimcha o’zgaruvchilar shart emas. Kamchiliklari:
1) Katta massivlarni uzoq qayta ishlaydi; 2) Har qanday holatda ham o’tishlar soni kamaymaydi.
“Pufaksimon” usulni yaxshilash for (int i=0;i for (int j=n-1;j>i;j--)
if (a[j] < a[j - 1]) { int x= a[j - 1];
a[j - 1] = a[j]; a[j] = x; }
O’rinlashtirish va taqqoslashlar soni: (n* log( n )). |
). 
