tez saralash algoritmlari

DOCX 12 sahifa 98,7 KB Bepul yuklash

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇
1 / 12
tez saralash algoritmlari reja: 1. qo’llanilishi 2. dasturi 3. blok sxemasi informatika yoki matematikada algoritmlar aniq va aniq muammoni hal qilishning bosqichma-bosqich jarayonini ta'minlaydi. ular odatda raqamlarni saralash, mashinani o'rganish yoki ma'lumotlarni ekranda ko'rsatish kabi turli xil vazifalar uchun ishlatiladi. vaziyatni istiqbolga qaratish uchun, yeryong'oqli sendvich tayyorlash uchun barcha qadamlaringizni o'ylab ko'ring, agar biz bu jarayonni avtomatlashtirsak, yeryong'oqli sendvich tayyorlamoqchi bo'lganingizda, xuddi shu jarayonni ongsiz ravishda bajarayotganingizni sezasiz. , biz bir xil qadamlardan foydalanamiz. bu algoritmlar ortidagi umumiy fikr. tezkor saralash quicksort - bu joy-joyida saralashning samarali algoritmi bo'lib, u yaxshi amalga oshirilganda birlashtirish va yig'indili saralashdan ikki-uch baravar tezroq ishlaydi. tezkor saralash - bu taqqoslash turi bo'lib, u kamroq munosabat aniqlangan har qanday turdagi elementlarni saralash imkonini beradi. samarali ilovalarda odatda barqaror tur emas. quicksort, o'rtacha, n ta elementni saralash uchun o(n.log(n)) taqqoslashlarini amalga oshiradi. eng yomon holatda, u o (n2) taqqoslashni amalga oshiradi, garchi bu xatti-harakatlar juda kam …
2 / 12
ni aylanmadan kichikroq qiymatlarga ega bo'lgan elementlarning pastki qatoriga va pivotdan kattaroq qiymatlarga ega bo'lgan elementlarning pastki qatoriga alohida qo'llang. rekursiyaning asosiy holati 1 o'lchamdagi massivlar bo'lib, ularni hech qachon tartiblash kerak emas. quyidagi diagrammada biz quicksort algoritmining har bir bosqichida eng chap elementni pivot sifatida qanday tanlashimiz, massivni pivot bo‘ylab taqsimlash va bo‘lish jarayonidan so‘ng olingan ikkita kichik massivda takrorlash ko‘rsatilgan: tezkor saralash ishlashi quicksort ning eng yomon vaqt murakkabligi o(n2), bu erda n - kirish hajmi. eng yomon holat, pivot ro'yxatdagi eng kichik yoki eng katta element bo'lganda yoki barcha massiv elementlari teng bo'lganda sodir bo'ladi. bu eng muvozanatsiz bo'limga olib keladi, chunki pivot massivni 0 va n-1 o'lchamdagi ikkita pastki qatorga ajratadi. agar bu har bir bo'limda qayta-qayta sodir bo'lsa (aytaylik, biz massivni tartibladik), u holda har bir rekursiv qo'ng'iroq avvalgi ro'yxatdan bir kichikroq o'lchamdagi ro'yxatni qayta ishlaydi, natijada o(n2) vaqt. tezkor saralash algoritmi britaniyalik kompyuter olimi …
3 / 12
kin, bu ularga quicksort samaradorligidan o'z loyihalari va ilovalarida foydalanish imkonini beradi. massivni saralash informatika fanining klassik "algoritmlar va ma'lumotlar tuzilmalari" kursida o'rganilgan birinchi jiddiy muammolardan biridir. shu munosabat bilan, yozish turlari va tegishli savollar ko'pincha stajyor yoki kichik ishlab chiquvchi lavozimiga intervyu paytida topiladi. muammoni shakllantirish an'anaga ko'ra, muammoni hal qilish usullarini taqdim etishni uning bayonoti bilan boshlash kerak. odatda, saralash vazifasi ba'zi bir butun sonlar massivlarini o'sish tartibida tartiblashni o'z ichiga oladi. lekin, aslida, bu biroz soddalashtirilgan. ushbu bo'limda keltirilgan algoritmlar o'rtasida tartib munosabatlari o'rnatiladigan har qanday ob'ektlar massivini tartibga solish uchun ishlatilishi mumkin (ya'ni har qanday ikkita element haqida biz aytishimiz mumkin: birinchisi ikkinchisidan, ikkinchisi birinchisidan kattaroq). , yoki ular teng). siz o'sish yoki kamayish tartibida saralashingiz mumkin. biz standart soddalashtirishdan foydalanamiz. tez tartiblash oxirgi marta biz biroz murakkabroq tur - qo'shish turi haqida gapirgan edik. bugun biz ancha murakkab algoritm - tez tartiblash (hoare sort deb …
4 / 12
uvchi” elementni tanlaydigan va qolgan elementlarni ikkita pastki qatorga bo‘luvchi o‘z joyida tartiblash algoritmi. pivotdan kichik elementlar chap pastki qatorga o'tkaziladi va pivotdan kattaroq elementlar o'ng pastki qatorga o'tkaziladi. algoritm ushbu pastki qatorlarni rekursiv tarzda tartiblaydi. o'rtacha, tezkor saralash o(nlog(n)) vaqtida ishlaydi. tez tartiblash algoritmi nima? quicksort algoritmi toni hoare tomonidan yaratilgan va 1961 yilda nashr etilgan bo‘lish va zabt etish algoritmidir. u asosiy elementni (ro‘yxatni bo‘lish uchun boshqa elementlarni solishtirish uchun foydalaniladigan ro‘yxatdagi element) tanlash orqali ishlaydi. birinchi, oxirgi, tasodifiy yoki median element bo'lib, barcha kichikroq elementlarni pivotning chap tomoniga va barcha kattaroq elementlarning o'ng tomoniga joylashtiring. bu har bir iteratsiya kirish ro'yxatini ikkita ro'yxatga bo'lish (bo'lish) ma'nosida bo'ladi, ulardan biri pivotning chap tomonidagi qiymati kichikroq barcha elementlarni, ikkinchisi esa o'ng tomonidagi barcha kattaroq elementlarni o'z ichiga oladi. aylanish. keyin ikkala ro'yxat yoki massivni qayta birlashtirishdan oldin ularni rekursiv saralaydi va shu bilan ro'yxatni samarali saralaydi. bu hali ham …
5 / 12
larga ega. amaldagi bo'lim usuli ushbu ilovalarni aniqlaydi va ular pivot elementi qanday tanlanganligi jihatidan farq qiladi. bo'lish algoritmi tezkor saralash algoritmining muhim qismidir, shuning uchun tezkor saralashni o'rganish uchun bo'lish algoritmlarini tushunish muhimdir. uch xil bo'lish algoritmlari mavjud, keling, ularni ko'rib chiqamiz: sodda bo'lim: biz sodda bo'limda vaqtinchalik massiv yaratamiz va avval pivotdan kichik bo'lgan elementlarni, keyin esa pivotdan kattaroq elementlarni saqlaymiz. vaqtinchalik massivni yaratganimizdan so'ng, biz uni asl massivimizga nusxalaymiz. lomuto bo'limi: lomutoning bo'lish usulidagi pivot oxirgi element hisoblanadi. taqqoslash uchun ikkita ko'rsatkich saqlanadi: i ko'rsatgich saqlanadi va j ko'rsatkichi massivni boshidan oxirigacha skanerlash uchun ishlatiladi. skanerlash massiv boshidan (i-1) indeksigacha bo‘lgan har qanday element pivot elementidan pastroq qiymatga ega bo‘lishini va i va j oralig‘idagi har qanday indeksdagi har qanday element quyidagi qiymatga teng yoki undan kattaroq qiymatga ega bo‘lishini ta’minlaydi. aylanish elementi. ushbu usul ko'proq taqqoslash imkonini beradi. hoare bo'limi: birinchi element hoarening bo'linish usulida pivot …

Ko'proq o'qimoqchimisiz?

Barcha 12 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"tez saralash algoritmlari" haqida

tez saralash algoritmlari reja: 1. qo’llanilishi 2. dasturi 3. blok sxemasi informatika yoki matematikada algoritmlar aniq va aniq muammoni hal qilishning bosqichma-bosqich jarayonini ta'minlaydi. ular odatda raqamlarni saralash, mashinani o'rganish yoki ma'lumotlarni ekranda ko'rsatish kabi turli xil vazifalar uchun ishlatiladi. vaziyatni istiqbolga qaratish uchun, yeryong'oqli sendvich tayyorlash uchun barcha qadamlaringizni o'ylab ko'ring, agar biz bu jarayonni avtomatlashtirsak, yeryong'oqli sendvich tayyorlamoqchi bo'lganingizda, xuddi shu jarayonni ongsiz ravishda bajarayotganingizni sezasiz. , biz bir xil qadamlardan foydalanamiz. bu algoritmlar ortidagi umumiy fikr. tezkor saralash quicksort - bu joy-joyida saralashning samarali algoritmi bo'lib, u yaxshi amalga oshirilganda birlas...

Bu fayl DOCX formatida 12 sahifadan iborat (98,7 KB). "tez saralash algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: tez saralash algoritmlari DOCX 12 sahifa Bepul yuklash Telegram