|
Mavzu: MURAKKAB SARALASH ALGORTMLARI JUDA HAM KATTA SONLAR BILAN ISHLASH.
Reja.
1. Bubble sort (Pufakchali saralash)
2. Selection sort (Tanlab saralash)
3. Insertion sort (Qo’shib saralash
4. Quick sort (Tez saralash)
5. Merge sort (Birlashtirib saralash)
6. Shell sort (Qobiqsimon saralash)
7. Heap sort(To’plab saralash)
8. Large number sort(Katta sonlarni saralash)
1. Saralash nima?
Saralash ba'zi bir aniqlangan mulkni ko'paytirish yoki pasayish tartibida yig'ish yoki ro'yxatdagi elementlarning joylashishi sifatida belgilanishi mumkin. Ma'lumotni saralashni yoki narsalarni ma'lum bir tartibda tartibga solishni istashimiz mumkin bo'lgan sabablar bor, bitta sabab ma'lumotlarning yaxshiroq o'qilishi va boshqa sabab shunchaki ma'lumotlar yoki to'plamdan ma'lumotlarni qidirish yoki olish. Masalan, agar biz Amazon-dagi bugungi narxlar sahifasiga kirsak, sahifadagi mahsulotlarni turli xil mezonlar bo'yicha saralash uchun pastga tushirish shaklida tanlov mavjud. Saralash mezonlari quyidagilarni o'z ichiga oladi; xususiyatli, narx pastdan pastga, narx pastdan pastga, chegirma - pastdan pastga, pastdan pastga. Ushbu variantlardan birini tanlash mahsulotlarni tanlangan parametr bo'yicha qayta tartibga soladi. Bunday holda, sahifadagi mahsulotlarni qanday ko'rishni xohlayotganimizni qayta tartibga solish uchun biz saralashdan foydalandik. Ma'lumotlarimizni saralashni xohlashimiz mumkin bo'lgan yana bir misol - bu Til lug'ati, bu erda so'zlarni lug'atda qidirish oson bo'lishi uchun tartiblash kerak. Kompyuterda fayllarni qidirish, ma'lumotlarni siqish va belgilangan joyga boradigan eng qisqa yo'lni topish kabi murakkab kompyuter dasturlari saralash algoritmining qandaydir shakliga asoslanadi.
2.Saralash algoritmi nima?
Saralash nima ekanligini va uni amalga oshirish usullarini tushunganimiz uchun endi saralashni amalga oshiruvchi algoritmlarga o'tamiz. Ro'yxat yoki to'plamni saralash uchun ro'yxat homolog bo'lishi kerak, ya'ni ro'yxatdagi barcha elementlar bir xil bo'lishi kerak. Ko'pincha biz butun sonlar ro'yxatidan foydalanamiz va odatda qiymatlarni ko'paytirish yoki kamaytirish tartibida butun sonlarni ro'yxatlashimiz mumkin. Masalan, quyidagi sonlarning ro'yxati berilgan: 2, 3, 9, 4, 6, biz ushbu ro'yxatni ba'zi xususiyatlarga ko'ra saralashimiz mumkin:
Kirish: 2, 3, 9, 4, 6
A. Chiqish: 2, 3, 4, 6, 9 =>
B. qiymatning ortib boruvchi tartibiga ko'ra tartiblangan . Chiqish natijasi: 9, 6, 4, 3, 2 => qiymatning pasayishi tartibiga ko'ra tartiblangan
C. Chiqish: 2, 3, 9, 4, 6 => omillar sonining ortib borishi tartibida saralanadi
Yuqoridagi birinchi holatda, biz ro'yxatdagi narsalarning tobora ortib borayotgan tartibiga qarab tartiblashtirdik.
Ikkinchi holda, biz ro'yxatdagi narsalarning kamayish tartibiga qarab tartibni tartiblashtirdik.
Uchinchi holatda, biz har bir butun son mavjud bo'lgan omillar sonining ortib borayotgan tartibiga qarab ro'yxatni tartibladik. Shuningdek, biz satrlar yoki so'zlarning ro'yxatini leksikografik tartibda saralashimiz mumkin va juda murakkab ma'lumot turlarini saralashimiz kerak bo'lishi mumkin.
Tartiblash algoritmi bu qatorni kirish sifatida qabul qiladigan, ketma-ketlikda belgilangan operatsiyalarni bajaradigan, ba'zan ro'yxat deb nomlanadigan va tartiblangan massivni chiqaradigan bir qator ko'rsatmalardan iborat algoritm. - brilliant.org
Nima uchun ma'lumotlarni saralashdan tashvishlanishimiz kerak va nima uchun tez va samarali saralash algoritmlarini topishga ko'p yillik tadqiqotlar va tadqiqotlar sarflandi? Saralash algoritmlarini o'qitish va tushunish Big-O notation, bo'linish va yutish usullari va ikkilik daraxtlar va uyumlar kabi ma'lumotlar tuzilmalari kabi boshqa kompyuter fanlari tushunchalarini joriy etishga yordam beradi. Saralangan ma'lumotlar mashinalarning hisoblash kuchi uchun juda foydali.
Agar biz ro'yxatni kompyuter xotirasida saralanmagan deb saqlasak va biz ushbu ro'yxatdagi elementni qidirishni xohlasak, biz qidirayotgan narsani topgunimizcha chiziqli qidirishni amalga oshirishimiz kerak va biz qidirayotgan narsani topgunimizcha skanerlashni davom ettirishimiz kerak. uchun. Agar biz ro'yxatdagi elementni topa olmagan bo'lsak (eng yomon stsenariyimiz), biz qidirayotgan element bilan taqqoslagan holda, butun ro'yxatni ko'rib chiqdik. Shunday qilib, agar ro'yxatda n ta element bo'lsa, eng yomon holatda, biz n ta taqqoslashni amalga oshiramiz. Zamonaviy kompyuter tomonidan ishlov beriladigan ma'lumotlarning hajmini tasavvur qiling, agar n = 2⁶⁴ ni olsak va bitta taqqoslashni hisoblash uchun 1 millisekund kerak bo'lsa, yomonroq stsenariyda taqqoslash uchun hisoblash vaqti 2⁶⁴ ga teng bo'ladi.millisekundlarda. Men buni soatlab, kunlar va hatto yillarga aylantirmoqchi emasman, ammo barchamizning fikrimizcha, bu hisoblash to'liq bo'lishi uchun bir necha yil kerak bo'ladi. Hech kim biron bir hisoblash tugashini kutib o'tirishni xohlamaydi, chunki biz bilamiz, vaqt qimmatlidir. Ammo, agar biz ro'yxatimizni saralangan ro'yxat sifatida kompyuter xotirasida saqlasak, biz elementimizni topish uchun ikkilik qidiruvdan foydalanishimiz mumkin. Bunday holda, n o'lchovli ro'yxatimiz uchun, hisoblashni yakunlash uchun kirish millisekundlarga to'g'ri keladi.
If we take n = 2⁶⁴;
log₂n => log₂2⁶⁴
=> 64log₂2
=> 64 * 1 => 64
(Izoh: log₂2 1 ga teng).
Shuning uchun taqqoslashni hisoblashni yakunlash uchun 64 millisekund davom etadi. Qoyil! Qanday farq, to'g'rimi ?! Tartiblangan ro'yxat bilan biz ko'p vaqtni tejashga va boshqa muhim narsalarga o'tishga muvaffaq bo'ldik.
Tartiblashning muammo sifatida muhimligi bugungi kunda bizda mavjud bo'lgan turli xil algoritmlarni loyihalashga olib keldi. Ushbu saralash algoritmlarining ba'zilari quyidagilarni o'z ichiga oladi;
. Bubble sort.
. Selection sort.
. Insertion sort.
. Quick sort.
. Merge sort.
. Shell sort.
. Heap Sort.
. Large number sort.
Saralash algoritmlarini tasniflash
Saralash algoritmlari ko'pincha turli xil parametrlarga ko'ra tasniflanadi, ularning ba'zilari quyida keltirilgan;
Do'stlaringiz bilan baham: |
