“Fizika – Matematika” fakulteti “Informatika o‟qitish metodikasi”yo‟nalishi
Download 1.68 Mb. Pdf ko'rish
|
c da massiv malumotlarini tartiblash usillari va ularning samaradorligini baxolash
|
O‟zbekiston Respublikasi oliy vao‟rta maxsus ta‟lim vazirligi Jizzax davlat pedagogigika instituti “Fizika – Matematika” fakulteti “Informatika o‟qitish metodikasi”yo‟nalishi “ Dasturlash asoslari ” fanidan KURS ISHI Bajardi: Shayzoqov T. Qabul qildi: Sattarov A. Кamissiya rayisi: ________________ A‟zolari: ________________ ________________ Jizzax -2015yil. Mavzu: C++ dа massiv ma‟lumotlarini tartiblash usillari va ularning samaradorligini baxolash.
I. Kirish
Saralash haqida ma‟lumot va ularning qo‟llanishini. II.Asosiy qism Nazariy qism
1. Saralashxossalarivaularningsinflari 2.Saralashalgoritmlaribajarilishtezligidaxotiranieffektivishlatilishibo„yichabahola sh.
3. Ichki va tashqi saralash.
Amaliy qism 1.Saralash bo‟yicha algaritmlar. 2. Saralashga oid misollar. 3.Sanash orqali saralash. 4.Razryadli saralash(Raqamli saralash).
III.Xulosa: Saralashning axamiyati.
Kirish:
Saralashdan biz kundalik hayotmizda ko‟p foydalanamiz.Masalan bazordan biror narsa harid qilishimizda, uning ko‟piroq 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 qo‟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 muayyantartibda saqlanadigan bo‟lsa, axlorotga 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 familalar 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 e‟xtimolining 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. Tartibliga solish natiyjasida yozuvlar kalitlarning qiymati ortib boorishi yoki kamayib boorish 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 ketme- ketligi 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 sonilarini toppish juda onson. 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 muoyyan 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.
II.Asosiy qism Saralash– bu massiv elementlarin biror qonuniyat (o‟sish,kamayish, oxirgi raqami,bo‟luvchilar,juftlari toqlari …)ga asoslangan holda tartiblashga aytiladi.
Umumanolgandasaralashningmaqsadiberilganob‟ektlarto„plamini aniqbirtartibdaguruxlabchiqishjarayonitushuniladi.
Saralashningmaqsadikeyinchalik, saralashganto„plamniqidirilayotganelementinitopishdaniborat. Bu
qariyib universal, fundamental jarayon. Biz bu jarayon bilan har kuni uchrashamiz – telefon daftaridagi saralash, kitoblar sarlavhasida, kutubxonalarda, lug„atlarda, pochtada savdoda va x.k.
Xar qanday saralash bu dastur demakdir va saralash presedurasining tavsivlarining baxosi dastur qanchalik yaxshi tuzilganiga bog‟liq bo‟ladi.Ikkita turli usillarning ish unimidagi farq “ yaxshi ” va “ yoman ” dasturlashtirilgan aynan bitta usil o‟rtasidagilarga nisbatan bir necha kam bo‟lishi mumkin.
Saralash presedurasi uchun sarflanadigan xaqiqiy mashina vaqti massivlardan ko‟rib chiqish, qiyoslash va sikllarni tashkil etish, ma‟lumotlarni boshqa joyga ko‟chirish kichik dasturlari, kichik dasturlarning aloqasi uchun bog‟liq bo‟ladi.
Bugun biz siz
bilan massiv
elementlarini saralashni ko‟rib chiqamiz.Saralashningjudako„pusullarimavjud. Ular turli to„plamlar uchun turlicha bo„lishi mumkin.
Massivni saralash uchun ishlatiladigan usul unga berilgan xotirani ixcham holda ishlatish lozim.Boshqacha qilib aytganda,saralanayotgan massiv xuddi shu massivni o„zida amalga oshirilishi lozim. Saralashusullarikammashinavaqtinitalabqilishilozim. Engyaxshitezalgoritmlartartibidagisaralashlarnitalabetadi.
Ichki va tashqi saralash.
Ichki saralash deganda, massivlarni saralashni, Tashqi saralash deganda esa, fayl elementlarini saralashni tushunamiz.
Algoritmning asosiy xossalaridan biri unga qo„llanish sferasi(sohasi) bilan bog„liq.
Asosanikkitatursaralashimavjud: • Ichkisaralash. Boshqachaqilibaytganda, bunday saralashmassivlardasaralashniamalgaoshiradi. Bunda keltirilag n ketma – ketli koperativ xotirada joylashda va bunda ixtiyoriy yacheykaga ruxsatlikirish mavjud. Asosan bu erda o„z joyida saralash amalga oshiriladi. • Tashqisaralash. Buerdafayllarustidasaralash amalgaoshiriladi. Albatta, bunday saralashda vaqt ko„p ketadi, lekin, o„lcham jixattan katta ketma-ketliklarni saralash mumkin.
Faraz qilaylik, bizga
* log n n 1 2 , , ...,
n a a a elementlar berilgan bo„lsin, u holda
massivnisaralashdeganda, unielementlarinio„rinlarigaalmashtirishtushuniladi.
Bu erda, quyidagi tartiblashtirilgan funksiyabajariladi.
Saralashalgoritmlaribajarilishtezligidaxotiranieffektivishlatilishibo„yichabah olash.
Vaqt – bu algoritmni tezligini xarakterlovchi asosiy parametr.Bu albatta hisoblash murakkabligi bilan bog„liq. Algoritmning uchta asosiy xulqi ya‟ni o„zini tutishi
yomon o„rta yaxshi
bo‟lishi mumkin.
O(n2) – bahoalgoritmniyomonxulqiniaksettiradi. O(n)– bahoalgoritmniyaxshixulqiaksettiradi.
Bu yerda n saralanadiganelementlarsonibo„lib, uavvaldanberilganbo„lishikerak. Xotira
– ba‟zi
biralgoritmlarsaralashdaqo„shimchaxotiratalabetiladi.Odatdabundayalgoritmlar O(log n) xotiranitalabetiladi. Ba‟zi birlari saralashda qo„shimcha xotira talab etmaydi. Bundayalgoritmlaro„zo„rnida (joyida) saralashdebataladi. 1 2 , , ...,
n k k k a a a 1 2 ... n k k k f a f a f a Saralash jarayonida dastlabki massivning bir qismi operativ xotirada o‟qiladi.u yerda ichki saralash usillaridan biri bilan saralanadi.so‟ngra tashqi xotira qurilmasiga yozib olinadi. Bu jarayon bir necha bor takrorlanadi. Shu tariqa saralangan yozuvlar ketma-ketligi keyinchalik birlashtiriladi. Tashqi xotira qurilmasidagi tartibga solingan ma‟lumotlar ketma-ketligini birlashtirish operatsiyasi qo‟shilish deb ataladi.
Saralashxossalarivaularningsinflari
Tabiiyxulqlilik– algoritmo„zinitabiiyholdagidektutadi. Agar kiritiladigan ketma- ketlikdagi bu xarakteristikani xisobga olsa va yaxshi ishlasa u tabiiy xulqli deyiladi.
1. Tanlashni saralash (Selection sort) – algoritm murakkabligi O(n 2 )
2. Ko„pikli saralash (Bubble sort) – algoritm murakkabligi O(n 2 ). 3. Aralashtirish saralashi (SHeyker, Cocktail sort, bidirectional bubble sort) - algoritm murakkabligi O(n2)
4. O„rniga qo„yish saralashi (Insertion sort) – algoritmmurakkabligi O(n 2 )
5. Qo„shilishsaralashi (Merge sort) – algoritmmurakkabligi O(n logn)
6. Ikkilikdaraxtiyordamidasaralash (Tree sort) – algoritmmurakkabligi O(n log n) qo„shimcha O(n) xotiratalabetadi.
7. Timsortsaralashi (Timsort) – algoritmmurakkabligi O(n log n) qo„shimcha O(n) xotiratalabetadi.
8. Sanashorqalisaralash (Counting sort) – algoritmmurakkabligi O(n+k) qo„shimcha O(n) xotiratalabetadi.
9. Bloklisaralash (Savatlisaralash, Bucket sort) – algoritmmurakkabligi O(n) qo„shimcha O(k) xotiratalabetadi Turg„unmas saralash algoritmlari.
1.Tanlash orqali saralash(Selection sort) algoritmmurakkabligiO(n 2 )
2. Shell saralash (Shell sort) algoritm murakkabligi O(n log 2 n). 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(n 2.71 )
9. Razryadli saralash. Algoritm murakkabligi O(n+k). O(k)qo„shimcha xotira talab etiladi. Amaliy bo„lmagan saralash
1. Bogosort – algoritmmurakkabligi O(n n!). 2. O„rinlashtirishsaralash – algoritmmurakkabligi O(n n!).
3. Ma‟nosizsaralash (Stupid sort) – algoritmmurakkabligi O(n 3 ).
4.
Bead asort
– Algoritmmurakkabligi O(n) yoki
O(sqrt(n)). Maxsusapparatta‟minotitalabetiladi.
5. Quymoqli saralash (Pancake sorting) – Algoritm murakkabligi O(n).Maxsus apparat ta‟minoti talab etiladi. Ko‟rib turubsiz saralash algaritimlari juda ko‟p turlari mavjud. Shulardan ba‟zi birlari birlari bilan tanishib chi qamiz.
Algoritmlar:
• Oddiy va tushunarli, lekin katta massivlar uchun, samarali emas Pufakchausuli Tanlashusuli Algarirm murakkabligiO(N2) • Qiyin, lekinsamaraliusullar «tezsaralash» (Quick Sort) «to„p-to„p» saralash (Heap Sort) Qo„shilibsaralash Piramidalisaralash Algarirm murakkabligi O(N*logN)
ko„tariladi»). • Pastdan boshlab ikkita qo„shni elementni solishtiramiz; agarda ular «noto„g„ri» turgan bo„lsa, ularni o„rnini almashtiramiz • Birinchi o„tishda bitta element (eng kichik) o„z joyiga o„tadi • N ta elementli massivnisaralashuchun N-1 o„tishni bajarish lozim (N-1 elementnio„z joyiga qo„yish uchun etarli).
Xar bir o‟tishdan so‟ng ushbu o‟tish davomida joy almashtirishlar bo‟lgan- bo‟lmaganligini tekshirib qo‟yish mumkin.
Masalan: 5; 2; 1; 3. sonlari uchun 3 ta o‟tish bajariladi. 1- o‟tish 2-o‟tish 3-o‟tish
5
5 1 2 2 1 5 1 1 2 2 3 3 3 3
Xar ikkita juftlik solishtiriladi.
A[N-1] ва A[N], A[N-2] ва A[N-1] … A[2] ва A[1]
Bu solishtirishlarda qaysi massivning elementi kichik bo‟lsa o‟sha element bilan joyini almashtiradi.buning uchun bizga almashtiradigan qiymat kerak. Masalan ikkita stakandagi ikki xil suyuqlik bor ularning o‟rnini almashtirish uchun bizga allbatta bitta bo‟sh stakan kerak bo‟ladi. Shuning uchun biz yangi bir c degan o‟zgaruvchi tanlab olamiz. 1 1
2 5 3 3 5 1 1 1 5 2 2 2 5 5 3 3 3
m[i]=m[i+1]; c=m[i+1]; Masala: massiv elementlarini o„sish tartibida chiqarish. Bu masalani hal qilish uchun quyidagi algaritmlardan foydalanamiz. Natiyja: Dasturini ko‟ramiz. #include using namespace std; int main() { int N, i , j, c; int A[100]; cout<<"Massivning nechta elementi bor? "; cin>>N; cout<<"Massivning elementlarini PROBEL bilan kiriting "< for (i=1; i<=N; i++)
cin>>A[i]; for (i = 1; i <= N; i ++)
{
for (j = N-1; j >= i ; j --) { c = A[j]; A[j] = A[j+1]; A[j+1] = c; } }
cout< return 0; }
TANLASH USULI G‟OYA: • Eng kichik elementni toping va uni birinchi o‟ringa qo‟ying.a[1] element bilan joyini almashtiring. • Qolganlaridan eng kichigini toping va uni ikkinchi o‟ringa qo‟ying a[2] binan o‟rnini almashtirng,va shunday davom etadi.
Ushbu usil bilan saralashda yozuvlarning tartibga solingan ketma-ketligi xotiraning dastlabki ketma-ketlik joylashgan uchastkasining o‟zida tashkil etiladi. Birinchi o‟tish davomida eng kichik element izlanadi. Bu element topilganidan so‟ng uni dastlabki ketme-ketlikdagi birinchi element bilan joyi almashtililadi, natiyjada eng kichik element tulayotgan tartiga solingan ketme- ketlikda birinchi element xolatini egalaydi.
So‟ngra qolgan elementlari ichidan keyingi eng kichik element izlanadi. Topilgan bu element xam dastlabki ketma-ketlikning ikkinchi element bilan joyi almashtiriladi. Bu jarayon barcha elementlar oshib boruvchi tartibda saralanib bo‟lgunga qadar davom etadi.
I 1 2 3 4 5 6 A(i) 10
4 11
9 7 2 1-o‟tish 2 4 11 9 7 10 2-o‟tish 2 4
9 7 10 3-o‟tish 2 4 7 9 11 10 4-o‟tish 2 4
9 11
10 5-o‟tish 2 4
9 10
11
Yuqorida ko‟rib chiqilgan usil bilan saralashda solishtirishlar soni dastlabki ketma-ketlikning tartibga solinganlik darajasiga bog‟liq bo‟lmaydi. Shuning uchun olingan ifoda solishtirishlarning eng kam ,eng ko‟p va o‟rtacha sonini 4 3
2
1
4
1 2 4 3 1 2 3 4
aniqlaydi. Solishtirishlarning o‟rtacha sonini baxolash uchun ifodaning quyidagi operatsiyasidan foydalanish mumkin. 0.5*N*N Elementlarining joyini almashtirishlar miqdori dastlabki ketma-ketlik elementlari joylashuviga bog‟liq. Lekin istalgan xolda xam bitta o‟tish davomida bittadan ortiq bo‟lmagan joy almashtirish talab etiladi, demak joy almashtirishlar eng ko‟p soni N – 1 ga teng . Eng yaxshi xolda, ya‟ni dastlabki ketma- ketlik tartibga solingan bo‟lsa bitta xam joy almashtirishlar talab etimaydi. Demak, joy almashtirish talab etmaydi.
Natiyja:
for( i = 1; i <= N ; i ++ ) { nMin = i ; for ( j = i+1; j <= N; j ++) if( A[j] < A[nMin] ) nMin = j; if( nMin != i ) { c = A[i]; A[i] = A[nMin]; A[nMin] = c; } } Sanash orqali saralash Sanash orqali saralash faqat chekli qiymatli sonlarni saralash mumkin. Masalan, massivning barcha elementlari qiymatlari 0..10 5 intervalga tegishli bo‟lsa. Sanash orqali saralash uchun yordamchi massiv ochamiz, bu massiv har bir sondan qancha borligini saqlab turadi. Har bir songa kelganda uning sonini oshirish uchun yordamchi massivdan shu indeksning qiymatini 1 ga oshiramiz. Keyin har bir 0..10 5 indekslarni birma-bir ko‟rib busondan necha marta uchragan bo‟lsa shuncha martachiqaramiz. Bunday saralash usuli massiv elementlariningmaksimal qiymati massiv o‟lchamiga nisbatan kichik bo‟lganda ancha evvektiv bo‟ladi. Ishlash vaqti O(n+Max); Qo‟shimcha xotira O(Max Max massiv ementlari maksimali.
using namespace std; int maxn = 100001; int cnt[100001]; int main() {int n;cin>>n; int a[n+1]; for (int i = 0; i < maxn; i++)cnt[i] = 0; for (int i = 1; i <= n; i++)cin>>a[i]; for (int i = 1; i <= n; i++)cnt[a[i]]++; int ind = 0; for (int i = 0; i < maxn; i++) { for (int j = 1; j <= cnt[i]; j++) { a[++ind] = i; }} for (int i = 1; i <= n; i++) { cout< return 0; }
Natiyja: Quyidagicha chiqadi. Natija:
Xulosa: Saralash orqali ko‟p masalalarni xal qilsa bo‟ladi. Katta-katta masalalarni oddiy va sodda qilib ishlab chiqsa bo‟lar ekan. Bu kurs ishi orqali saralashning qanchlik qiziqarli va samarali mavzu ekanligini bildik. Bundan tashqari juda ko‟p yangi usillar orqali saralash yoki maxsimum va minumum qiymatlarini topish,massivlar ustida turli xil chiroyli va qiziqarli masalarni xal qilish, va shu kabi misollarni tez bojara olish qobilyatini xosil qildim. Men oldin matematikani bilganim bilan uni dasturda qanday qilib qo‟llashga juda qiynalardim. Bu kurs ishi orqali men mustaqil oddiy saralashlarni xal qiladigan dasturlar tuza olish qobilyatiga ega bo‟ldim. Kundalik hayotimizda juda ko‟p qo‟llaniladigan saralash bilsam xar doim xar bir ishimizda foydalanar ekanmiz. O‟ylaymanki bu masalar dasturlash olamiga kirib borishimga katta fundament vazifasini o‟tab beradi. Foydalngan adabiyatlar ro‟yxati. 1.http:\\acm.tuit.uz 2.”Informatika” fani bo‟yicha maruzalar matini. C/C++ dasturlash tili 2-qism. 3.Sorting Algorithms in 6 Minutes. 4.Merge-sort with Transylvanian-saxon (German) folk dance) 5.http:\\Referat.arxiv.uz 6.http:\\Ziyonet.uz 7.http:\\dastur.uz Download 1.68 Mb. Do'stlaringiz bilan baham: 
|