49
Mustaqil ishlash uchun masalalar:
1.
10 ta elementdan iborat stek hosil qiling. Stekning yuqori elementini
oʻchirish metodidan
foydalaning
2.
100 ta elementdan iborat stek hosil qiling. Ushbu stekka yana 100 ta
element qoʻshing
3.
100 ta elementdan iborat stek hosil qiling. Stek metodlaridan
foydalanib amallar bajaring
4.
20 ta elementdan iborat Navbat hosil qiling. Uning 10
ta elementini
oʻchiring. Uning oxirgi va birinchi elementlarni qoʻshing
5.
50 ta elementdan iborat Navbat hosil qiling. Uning birinchi elementini
olib tashlash metodidan foydalaning
6.
20 ta elementdan iborat Navbat hosil qiling. Uning 10 ta elementini
oʻchiring. Uning oxirgi va birinchi elementlarni qoʻshing
50
3-§. Saralash algoritmlari. Eng oddiy algoritmlar. Past baho
Mazkur
mavzuda
algoritmlarning
yangi
sinfi
-
saralash
algoritmlarini oʻrganamiz. Ma‘lumotlarni qayta ishlashda ma‘lumotning
axborot (
info
) maydonini bilish va uni mashinada joylashishini tasavvur
qilish juda muhimdir.
Saralashning ichki va tashqi saralash turi mavjud:
1.ichki saralash - bu tezkor xotiradagi ma‘lumotlarni saralash;
2. tashqi saralash - tashqi xotira (fayllar)dagi ma‘lumotlarni
saralash.
Saralash deganda ma‘lumotlarni xotirada muayyan tartibda uning
kalitlari boʻyicha joylashtirish, muayyan tartib deganda esa kalit qiymati
boʻyicha oʻsish (yoki kamayish) tartibida roʻyxatning boshidan
oxirigacha joylashtirish tushuniladi.
Saralash algoritmlarining samaradorligini
bir necha parametrlari
boʻyicha farqlash mumkin. Bu parametrlarning asosiylari quyidagilar
hisoblanadi:
-
saralash uchun sarflanadigan vaqt;
-
saralash uchun talab qilinadigan tezkor xotira hajmi.
Saralash algoritmlarini baholashda faqat ―joyida‖ saralash usullarini
qarab
chiqamiz, ya‘ni saralash jarayoni uchun qoʻshimcha xotira
zahirasi talab qilinmaydi. Saralash uchun sarf qilinadigan vaqtni esa,
saralash bajarilishi jarayonida amalga oshiriladigan taqqoslashlar va
oʻrin almashtirishlar soni orqali hisoblash mumkin.
Ixtiyoriy saralash
usulida taqqoslashlar soni O(nlog
2
n) dan O(n
2
) gacha boʻlgan oraliqda
yotadi.
Ma‘lumotlarni saralashning