Raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

view rawinsertion-sort.js 
hosted with ❤ by 
GitHub
 
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni 
tartiblash uchun «<» dan boshqa amalni ishlatish kerak. Masalan, ES6 
uchun 
String.prototype.localeCompare()
 ni ishlatib ko’ring. 

---

Saralash algoritmi - Sorting algorithm 
Ushbu bo'lim emas keltirish har qanday manbalar. Iltimos yordam bering ushbu 
bo'limni yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega 
bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. (2019 yil may) (Ushbu 
shablon xabarini qanday va qachon olib tashlashni bilib oling) 
Yilda Kompyuter fanlari, a saralash algoritmi bu algoritm a elementlarini 
qo'yadigan ro'yxat ma'lum birida buyurtma. Eng ko'p ishlatiladigan buyurtmalar raqamli 
tartib va leksikografik tartib. Samarali tartiblash optimallashtirish uchun muhimdir 
samaradorlik boshqa algoritmlarning (masalan qidirmoq va birlashtirish algoritmlar) 
kirish ma'lumotlarini saralangan ro'yxatlarda bo'lishini talab qiladi. Saralash ham 
ko'pincha foydalidir kanonizatsiya qilish ma'lumotlar va inson tomonidan o'qiladigan 
mahsulotni ishlab chiqarish uchun. Rasmiy ravishda har qanday saralash algoritmining 
chiqishi ikkita shartni qondirishi kerak: 
Chiqish kamaytirilmaydigan tartibda (har bir element kerakli darajada oldingi 
elementdan kam emas umumiy buyurtma); 
Chiqish a almashtirish (qayta tartibga solish, ammo barcha asl elementlarni saqlab qolish) 
kirishning. 
Bundan tashqari, kirish ma'lumotlari ko'pincha an-da saqlanadi qatorbu imkon 
beradi tasodifiy kirish, ro'yxat o'rniga, faqat ruxsat beradi ketma-ket kirish; mos 
algoritmlardan so'ng har qanday ma'lumot turiga ko'plab algoritmlarni qo'llash mumkin. 
Tartiblash algoritmlari ko'pincha "sort" so'zidan keyin so'z deb nomlanadi va 
grammatik jihatdan ingliz tilida ism iboralari sifatida ishlatiladi, masalan, "katta 
ro'yxatlarga qo'shish tartibini ishlatish samarasiz" iborasi qo'shish tartibi ga ishora qiladi 
qo'shish tartibi saralash algoritmi.Entsiklopediya site:uz.wikisko.ru 
Ro'yxatdagi narsalarni tartiblash oddiy ish bo'lib, ko'p vaqt talab etadi. Saralash 
atamasi odatda ro'yxatdagi narsalarni oldindan belgilangan buyurtma munosabatlariga 
qarab ko'tarilish yoki kamayish tartibida tartibga solishni anglatadi. Saralash ko'pincha 
ma'lumotni qayta ishlashda yana bir asosiy faoliyat bo'lgan qidirish uchun mo'ljallangan. 
Agar undagi so'zlar tartiblanmagan yoki saralanmagan bo'lsa, lug'atdan biron bir so'zni 
izlash qanchalik qiyin bo'lganini tasavvur qiling. Lug'atdagi yozuvlar standart alifbo 

---

tartibida saqlanishining sababi shu. Ko'p sonli vazifalar va hisoblashlar shunchaki 
saralash orqali oson emas. Va tartiblash algoritmlari rasmga tushadigan joy. 
Tez saralash nima? 
Quick Sort - bo'linish va zabt etish yondashuviga asoslangan yuqori samarali, 
ammo samarali tartiblash algoritmi, bu muammoni ikki yoki undan ortiq kichik 
masalalarga ajratib, so'ngra rekursiv ravishda hal qilinadigan dinamik yondashuvga juda 
o'xshaydi. Agar sub-muammolarning hajmi etarlicha kichik bo'lsa, ular hech qanday 
muammosiz oddiygina hal qilinadi. Tezlik bilan taqsimlash algoritmi bo'limlar 
almashinuvi turi deb ham ataladi. Saralash uchun ro'yxatni uchta asosiy qismga ajratadi: 
1) Umumiy element (markaziy elementlar), 2) aylanadan kichik elementlar va 3) pivotdan 
kattaroq elementlar. O'chirishning o'zi ikki guruh o'rtasida oxirgi holatiga o'tkaziladi va 
QUICK SORT rezursiv ravishda qo'llaniladi. 
Birlashtirish Sort nima? 
Merge Sort - bu bo'linish va zabt etish texnikasiga asoslangan yana bir umumiy 
maqsadli saralash algoritmi. Tashqi ko'rinishda faylda saqlanadigan ma'lumotlarni 
saralash uchun samarali foydalanish uchun yaratilgan eng taniqli va mashhur tartiblash 
algoritmlaridan biridir. O (n) qo'shimcha joydan foydalanganda eng yomon holatlarda O 
(n log n) xatti-harakatlarni taklif qiladi. U 'A' to'plamini ikkita kichik to'plamga ajratadi, 
ularning har biri keyin saralanadi. Oxirgi bosqichda ushbu ikkita saralangan to'plamlar n 
o'lchamdagi bitta to'plamga birlashtiriladi. Bu tartiblangan ro'yxat bo'ladi. Algoritm juda 
tez va barqaror turga kiradi va bog'langan ro'yxatlar uchun juda ma'qul. 
Tez Saralash va Birlashtirish Saralash o'rtasidagi farq 
Asoslar 
- Tez Sortlash va Merge Sort ikkisi ham bo'linish va zabt etish asosida saralash 
algoritmlari bir xil asosiy printsipga ega - muammoni ikki yoki undan ortiq kichik 
muammolarga bo'lish va keyin ularni rekursiv ravishda echish. Biroq, ular birlashtirish 
tartiblari va ishlash jihatidan farq qiladi. Tez tartiblash odatda boshqa saralash 
algoritmlariga qaraganda yaxshiroq va tezroq, shu jumladan kichik ma'lumotlar 
to'plamiga kelganda, Sort birlashtirish, ma'lumotlar to'plamining turidan qat'i nazar, 
muvofiqlikni saqlaydi. Tez tartiblashtirish massivlar uchun, afzal bog'langan ro'yxatlar 
uchun birlashtirish tartibiga esa eng mos keladi. 

---

Kosmik murakkablik 
- Tez tartiblash algoritmida tartiblash rekursiv ravishda amalga oshiriladi va har bir 
rekursiv chaqiruv uchun stack joyi kerak. Birlashtirish uchun qo'shimcha joy talab 
qilinmaydi, birlashtirish uchun bitta xotira maydoni bundan mustasno. Bu joyida 
tartiblash algoritmi bo'lganligi sababli, tartiblash uchun qo'shimcha joy kerak emas. 
Aslida, u massivni ajratish va birlashtirish paytida bir xil qatordan foydalanadi. Merge 
Sort-da, boshqa tomondan, faylda yoki massivda ma'lumotlarni taqdim etishning bir 
necha usullari mavjud, shuning uchun qo'shimcha joy talab qiladigan sub-fayllar yoki bir 
xil o'lchamdagi massivlar kabi ish joylari kerak. 
Eng yomon ishning murakkabligi 
- Tez tartiblash uchun eng yomon xatti-harakatlar bo'linish muvozanatlanmagan 
holatlarda yuzaga keladi, bu alimentni ajratish uchun qaysi elementlardan 
foydalanilganligiga bog'liq, bu holda algoritm asimptotik tarzda asta-sekin kiritish 
tartibida ishlaydi. Tez tartiblashtirishning eng yomon holati O (n) dir
2
) va mashq sifatida 
qoldiriladi. Biroq, to'g'ri burilishni tanlash orqali buning oldini olish mumkin. Boshqa 
tomondan, Merge Sortning eng yomon holati, u maksimal taqqoslashni amalga oshirishi 
kerak bo'lgan holatlarda yuzaga keladi. Birlashtirish uchun chiziqli ishlashni hisobga 
olsak, Birlashtirish Saralashining eng yomon holati O (n log)
2
n). 
Ishlash 
- Tez Sortlash va Birlashtirish Saralash algoritmlari ikkiga bo'linish va saralash usullariga 
asoslangan bo'lishiga qaramay, ular bo'linish va birlashtirish protseduralarini bajarish 
uchun ishlatiladigan usullar bilan farqlanadi. Tez tartiblash uchun asosiy ish ro'yxatni 
quyi ro'yxatlarni saralashdan oldin bo'lib o'tadigan ikkita quyi ro'yxatlarga bo'lishdir. 
Birlashtirish Saralash uchun asosiy ish quyi ro'yxatlar tartiblanganidan keyin sodir 
bo'ladigan ikkita pastki ro'yxatlarni birlashtirishdir. Birlashtirish Sort ikkita sub-massivni 
birlashtirish uchun vaqtincha qatorni talab qiladi, shu bilan Tez Saralash uchun 
qo'shimcha bo'sh joy talab qilinmaydi, bu esa Marge Sort-ga nisbatan ko'proq joyni 
tejashga yordam beradi. 
Tez Saralash va Birlashtirish Saralash: Taqqoslash jadvali 
Tez Sortlash va Merge Sort ikkala algoritmlari bo'linish va saralash usullariga 
asoslangan. Biroq, ular bo'linish va birlashtirish protseduralarini bajarish uchun 

---

ishlatiladigan usullar bilan farqlanadi. Ular asosan bitta printsip asosida ishlaydi - 
muammoni ikki yoki undan ortiq kichik muammolarga bo'lish va keyin ularni rekursiv 
ravishda hal qilish. Birlashtirish Sort eng yomon holatda Quick Sortga qaraganda 
samaraliroq, ammo ikkalasi o'rtacha holatda bir xil darajada samaralidir. Ammo Quick 
Sort birlashtirish tartibiga qaraganda tejamkorroq joy. Shunday qilib, "Tez saralash", 
birlashtirishga qaraganda tezroq va yaxshiroq, ammo taqqoslash haqida gap ketganda, 
ba'zi holatlarda samarasiz bo'ladi.