Saralash algoritmi nima

Saralash algoritmi — bu algoritm ro‘yxatdagi elementlarni muayyan tartibga keltirish uchun qo‘llanadi. Agar ro‘yxatdagi element bir nechta maydondan iborat bo‘lsa, tartib mezoni vazifasini bajaradigan maydon saralash kaliti deb ataladi. Amaliyotda kalit ko‘pincha son bo‘ladi, qolgan maydonlarda esa algoritm ishiga ta’sir qilmaydigan ma’lumotlar saqlanadi.

Tarixi

Tabulyator Golleritning «saralash qutisi» bilan

Zamonaviy saralash usullarining dastlabki namunalari XIX asrdayoq paydo bo‘lgan. 1890-yilga kelib, ma’lumotlarni qayta ishlashni tezlashtirish maqsadida aholini ro‘yxatga olish vaqtida AQSh fuqarosi German Gollerit birinchi statistik tabulyatorni — ma’lumotlarni avtomatik qayta ishlashga mo‘ljallangan elektromexanik mashina bo‘lib, undagi axborot perforatsion kartalarda yozilgan. Gollerit mashinasida 26 ta ichki bo‘limdan iborat maxsus «saralash qutisi» bo‘lgan. Mashina bilan ishlashda operator perforatsion kartani kiritib, dastakni tushirishi kerak edi. Kartadagi teshiklar tufayli muayyan elektr zanjiri tutashar va unga ulangan hisoblagich ko‘rsatkichi bir birlikka ortardi. Shu bilan bir vaqtda saralash qutisidagi 26 ta qopqoqdan biri ochilib, perforatsion karta tegishli bo‘limga o‘tkazilar, so‘ng qopqoq yopilardi. Bu mashina daqiqasiga qariyb 50 ta kartani qayta ishlash imkonini berib, ma’lumotlarni qayta ishlashni 3 baravar tezlashtirdi. 1900-yilgi aholini ro‘yxatga olishga kelib, Gollerit kartalarni uzatishni avtomatlashtirib, mashinani takomillashtirdi. Gollerit saralash mashinasining ishlashi razryadlar bo‘yicha saralash usullariga asoslangan edi. Mashina patentida saralash «har bir ustun bo‘yicha alohida» bajarilishi ko‘rsatilgan, biroq uning tartibi belgilanmagan. 1894-yilda Jon Gor patentlagan boshqa shunga o‘xshash mashinada o‘nliklar ustunidan boshlab saralash tilga olingan. Birliklar ustunidan boshlab saralash usuli adabiyotda ilk bor 1930-yillarning oxirida uchraydi. Bu vaqtga kelib saralash mashinalari daqiqasiga 400 tagacha kartani qayta ishlay olardi.

EDVAC

Keyinchalik saralash algoritmlari tarixi elektron hisoblash mashinalari rivojlanishi bilan chambarchas bog‘liq bo‘lib qoldi. Ayrim manbalarga ko‘ra, aynan saralash dasturi hisoblash mashinalari uchun yaratilgan ilk dastur bo‘lgan. EHM konstruktorlarining ayrimlari, jumladan, EDVAC ishlab chiquvchilari saralash masalasini hisoblash mashinalari uchun eng xos sonli bo‘lmagan masala deb atashgan. 1945-yilda Jon fon Neyman EDVAC uchun bir qator buyruqlarni sinash maqsadida birlashtirish usuli bilan saralash dasturlarini ishlab chiqdi. O‘sha yili nemis muhandisi Konrad Suze oddiy kiritish usuli bilan saralash dasturini yaratdi. Bu vaqtga kelib tezkor, ixtisoslashgan saralash mashinalari allaqachon paydo bo‘lgan edi; ishlab chiqilayotgan EHM samaradorligi ular bilan taqqoslab baholanardi. Hisoblash mashinalari yordamida saralash muhokama qilingan ilk nashr 1946-yilda Jon Mokli o‘qigan ma’ruza bo‘ldi. Mokli saralash sonli hisob-kitoblar uchun ham foydali bo‘lishi mumkinligini ko‘rsatdi, oddiy kiritish va ikkilik kiritish usullarini, shuningdek, qisman o‘tishlardan foydalanadigan razryadlar bo‘yicha saralash usulini tasvirlab berdi. Keyinchalik u muhandis Jon Ekkert bilan birgalikda asos solgan «Eckert–Mauchly Computer Corporation» kompaniyasi ilk elektron hisoblash mashinalarining ayrimlarini — BINAC va UNIVAC ni chiqardi. Qayd etilgan ichki saralash algoritmlari bilan bir qatorda tashqi saralash algoritmlari ham paydo bo‘ldi. Ularning rivojlanishiga dastlabki hisoblash mashinalari xotirasining cheklangan hajmi turtki berdi. Xususan, muvozanatlangan ikki yo‘lli razryadli saralash va muvozanatlangan ikki yo‘lli qo‘shish usullari taklif qilindi.

Hoar usulidagi tezkor saralash

1952-yilga kelib ichki saralashning ko‘plab usullari amaliyotda qo‘llanayotgan bo‘lsa-da, nazariya nisbatan sust rivojlangan edi. 1952-yil oktabrida Daniel Goldenberg beshta saralash usulini keltirib, ularning har biri uchun eng yaxshi va eng yomon holatlarni tahlil qildi. 1954-yilda Garold Syuvord Goldenberg g‘oyalarini rivojlantirdi, shuningdek, tashqi saralash usullarini tahlil qildi. Govard Demut 1956-yilda saralash masalasining uchta abstrakt modelini ko‘rib chiqdi: siklik xotiradan, chiziqli xotiradan va ixtiyoriy murojaatli xotiradan foydalanish. Muallif ushbu masalalarning har biri uchun optimal yoki deyarli optimal saralash usullarini taklif qildi; bu nazariyani amaliyot bilan bog‘lashga yordam berdi. Hisoblash texnikasi bilan shug‘ullanuvchilar soni kam bo‘lgani sababli, bu ma’ruzalar «ochiq adabiyot»da e’lon qilinmagan. 1955-yilda matbuotda chop etilgan saralash haqidagi ilk yirik sharh maqola J. Hoskenning ishi bo‘ldi. Unda ishlab chiqaruvchi firmalarning risolalariga asoslanib, o‘sha paytda mavjud bo‘lgan barcha maxsus qurilmalar va EHM uchun saralash usullari tasvirlangan. 1956-yilda E. Frend o‘z ishida ko‘plab ichki va tashqi saralash algoritmlarining matematik xususiyatlarini tahlil qilib, bir nechta yangi usulni taklif qildi.

Shundan keyin ko‘plab turli saralash algoritmlari taklif qilindi. Masalan, 1956-yilda manzilni hisoblash; kiritish va birlashtirish, almashuvli razryadli saralash, kaskadli birlashtirish va Shell usuli 1959-yilda, ko‘p fazali birlashtirish va daraxtga kiritish 1960-yilda, tebranuvchi saralash va Hoar usulidagi tezkor saralash 1962-yilda, Uilyamsning uyumli saralashi va Betcherning almashuvli birlashtirish saralashi 1964-yilda. 60-yillarning oxirida saralash nazariyasi ham jadal rivojlandi. Keyinroq paydo bo‘lgan algoritmlar ko‘p jihatdan avvaldan ma’lum usullarning variantlari edi. Kirish ketma-ketligi oldindan belgilangan mezonlarga javob bergan hollarda tezroq ishlashga mo‘ljallangan adaptiv saralash usullari keng tarqaldi.

Masalaning qo‘yilishi

Faraz qilaylik, N ta elementni saralash kerak: R1,R2,…,Rn. Har bir element yozuvdan iboratRj, unda muayyan ma’lumot va kalitKj saralash jarayonini boshqaradi. Kalitlar to‘plamida tartib munosabati «<» aniqlangan bo‘lib, har qanday uchta kalit qiymati a,b,c uchun quyidagi shartlar bajariladi:

Ushbu shartlar chiziqli yoki mukammal tartibning matematik tushunchasini belgilaydi; ularga javob beradigan to‘plamlarni ko‘pchilik usullar bilan saralash mumkin.

Saralashning vazifasi — shunday o‘rin almashtirish yordamida yozuvlarni p(1)p(2)…p(n) indekslari {1,2,…,N} bo‘yicha joylashtirishki, natijada kalitlar kamaymaydigan tartibda joylashsin:

Kp(1)⩽Kp(2)⩽…⩽Kp(n)

Saralash barqaror deb ataladi, agar u kalitlari bir xil bo‘lgan elementlarning o‘zaro joylashuvini o‘zgartirmasa:

p(i)<p(j) har qanday Kp(i)=Kp(j) va i<j.

Saralash usullarini ichki va tashqi turlarga ajratish mumkin. Ichki saralash operativ xotiraga sig‘adigan ma’lumotlar uchun qo‘llanadi, shu sababli ma’lumotlar tuzilmalari jihatidan moslashuvchanroqdir. Tashqi saralashda ma’lumotlar operativ xotiraga sig‘maydi va u cheklangan resurslar sharoitida natijaga erishishga yo‘naltirilgan.

Saralash algoritmini baholash

Saralash algoritmlari bajarilish tezligi va xotiradan foydalanish samaradorligi bo‘yicha baholanadi:

  • Vaqt — algoritm tezkorligini tavsiflovchi asosiy parametr. U hisoblash murakkabligi deb ham ataladi. Saralashda eng yomon, o‘rtacha va eng yaxshi holatlardagi algoritm ishlashi kirish to‘plamining quvvati A. Agar algoritmga kirishda A, u holda belgilaymiz: n = |A|. Odatdagi algoritm uchun yaxshi ishlash ko‘rsatkichi — O(n log n) va yomon ishlash ko‘rsatkichi — bu O(n2). Saralash uchun ideal ishlash ko‘rsatkichi — O(n). Kalitlarni taqqoslashning abstrakt amalidan foydalanadigan saralash algoritmlari uchun har doim kamida ma’lum miqdordagi taqqoslash amallari zarur. Shunga qaramay, Han (Yijie Han) saralash algoritmining hisoblash murakkabligi O(n log log n), kalitlar fazosining cheklanganligidan foydalanadi (algoritm nihoyatda murakkab, О-belgilash ortida esa juda katta koeffitsiyent yashiringan, shu bois uni kundalik amaliyotda qo‘llash mumkin emas). Shuningdek, saralash tarmoqlari tushunchasi ham mavjud. Agar bir vaqtning o‘zida bir nechta taqqoslashni (masalan, parallel hisoblash jarayonida) bajarish mumkin deb faraz qilsak, n ta sonni O(log2 n) ta amalda saralash mumkin. Bunda elementlar soni n qiymati oldindan ma’lum bo‘lishi kerak;
  • Xotira — ayrim algoritmlar ma’lumotlarni vaqtincha saqlash uchun qo‘shimcha xotira ajratishni talab qiladi. Odatda bunday algoritmlar O(log n) xotirani talab qiladi. Baholashda dastlabki massiv egallagan joy hamda kirish ketma-ketligiga bog‘liq bo‘lmagan xarajatlar, masalan, dastur kodini saqlash uchun zarur xotira hisobga olinmaydi (chunki bularning barchasi O(1)). Qo‘shimcha xotira talab qilmaydigan saralash algoritmlari joyida saralash usullariga kiritiladi.

Optimallik O(n log n) umumiy holatda

Umumiy holatda saralash masalasida elementlar ustida bajarish mumkin bo‘lgan yagona majburiy amal taqqoslash deb olinadi. Elementlar a va b ni taqqoslash natijasi quyidagi ikki variantdan biri bo‘lishi mumkin: a≤b yoki a>b. Shuning uchun algoritm ishlash davomida k ta taqqoslash bajarsa, javoblar kombinatsiyasining jami 2k ta varianti bo‘lishi mumkin.

ta elementning o‘rin almashtirishlari soni n ga teng. Javoblar kombinatsiyalari to‘plamini barcha o‘rin almashtirishlar to‘plamiga n!. Javoblar kombinatsiyalari to‘plamini barcha o‘rin almashtirishlar to‘plamiga syur’yektiv akslantirish mumkin bo‘lishi uchun taqqoslashlar soni kamida log2n! ga teng bo‘lishi kerak (chunki taqqoslash — ruxsat etilgan yagona amal).

Logarifmlashda Stirling formulasini qo‘llab, quyidagini ko‘rish mumkin:log2n!=log2(2πn(ne)n)=nlog⁡n+O(n)=Ω(nlog⁡n)

Xususiyatlari va turlari

  • Barqarorlik — barqaror saralash kalitlari bir xil bo‘lgan elementlarning o‘zaro joylashuvini o‘zgartirmaydi.
  • Tabiiy ishlash xususiyati — avvaldan tartiblangan yoki qisman tartiblangan ma’lumotlarni qayta ishlashda usulning samaradorligi. Agar algoritm kirish ketma-ketligining bu xususiyatini hisobga olib, shunday vaziyatda yaxshiroq ishlasa, uning ishlashi tabiiy hisoblanadi.
  • Taqqoslash amalidan foydalanish. Elementlarni o‘zaro taqqoslash orqali saralaydigan algoritmlar taqqoslashga asoslangan algoritmlar deb ataladi. Bu algoritmlar uchun eng yomon holatdagi minimal mehnat sarfi O(n⋅log⁡n), biroq ular qo‘llanish jihatidan moslashuvchan. Ma’lumotlarning maxsus holatlari (turlari) uchun samaraliroq algoritmlar mavjud.

Algoritmning yana bir muhim xususiyati — uning qo‘llanish sohasi. Bu yerda saralashning ikkita asosiy turi mavjud:

  • Ichki saralash operativ xotiraga to‘liq sig‘adigan va istalgan katagiga ixtiyoriy tartibda murojaat qilish mumkin bo‘lgan massivlar bilan ishlaydi. Ma’lumotlar odatda qo‘shimcha xarajatlarsiz, o‘sha joyning o‘zida saralanadi.
    • Zamonaviy shaxsiy kompyuter arxitekturalarida xotirani sahifalash va keshlash usullari keng qo‘llanadi. Saralash algoritmi ishlatilayotgan keshlash va sahifalash algoritmlari bilan yaxshi uyg‘unlashishi kerak.
  • Tashqi saralash hajmi katta bo‘lgan, biroq ularga ixtiyoriy emas, balki ketma-ket murojaat qilinadigan xotira qurilmalari (fayllarni tartiblash) bilan ishlaydi. Bunda ayni paytda faqat bitta element «ko‘rinib turadi», xotiraga nisbatan orqaga qayta o‘qish xarajatlari esa o‘zini oqlamaydi. Bu algoritmga qo‘shimcha cheklovlar qo‘yadi va odatda qo‘shimcha disk maydonidan foydalanadigan maxsus saralash usullariga olib keladi. Bundan tashqari, tashqi xotiradagi ma’lumotlarga murojaat qilish operativ xotira bilan ishlashga qaraganda ancha sekin.
    • Ma’lumot tashuvchiga ketma-ket murojaat qilinadi: har bir vaqtda faqat joriy elementdan keyin keladigan elementni o‘qish yoki yozish mumkin.
    • Ma’lumotlar hajmi ularni operativ xotiraga joylashtirish imkonini bermaydi.

Shuningdek, algoritmlar quyidagi belgilar bo‘yicha tasniflanadi:

  • qo‘shimcha xotiraga ehtiyoj borligi yoki yo‘qligi
  • taqqoslash amalidan tashqari ma’lumotlar tuzilmasi haqida qo‘shimcha bilim talab qilinishi yoki qilinmasligi

Eng mashhur saralash algoritmlarining qisqacha tavsifi

Algoritm Tavsif Bajarilish vaqti Xotira sarfi Izoh
Eng yomon holatda O‘rtacha holatda Eng yaxshi holatda
Barqaror saralash algoritmlari
Pufakchali saralash (ingl. Bubble sort) Massiv bo‘ylab yurib, ketma-ket juft elementlarni taqqoslaydi va ular noto‘g‘ri tartibda joylashgan bo‘lsa, o‘rinlarini almashtiradi. O(n2) O(n2) O(1) Saralash jarayonida eng kichik element massivning yuqori qismiga «qalqib chiqadi» va pufakchani eslatadi
Kokteyl usulida saralash (ingl. Cocktail sort) Ikki yo‘nalishda ishlaydigan, optimallashtirilgan pufakchali saralash O(n2) O(n2) O(1)
Kiritish orqali saralash (ingl. Insertion sort) Kirish ketma-ketligidagi elementlar bittadan ko‘rib chiqiladi va har bir yangi kelgan element avval tartiblangan elementlar orasidagi mos joyga joylashtiriladi O(n2) O(n2) O(1)
Gnomcha saralash (ingl. Gnome sort) Quyidagi saralash usullarining gibridi: kiritish orqali saralash va pufakchali saralash. O(n2) O(n2) O(1) Nomi gul tuvaklari qatorini saralayotgan bog‘ gnomlarining taxminiy xatti-harakatidan kelib chiqqan
Birlashtirish orqali saralash (ingl. Merge sort) Rekursiv ravishda massivning yarmini saralaydi, so‘ng ularni bitta massivga birlashtiradi O(nlog⁡n) O(nlog⁡n) O(n)
Ikkilik qidiruv daraxti yordamida saralash (ingl. Tree sort) Dastlabki ma’lumotlar asosida ikkilik qidiruv daraxti quriladi va unda eng kichik qiymatlar ketma-ket yig‘iladi O(n2) O(nlog⁡n) O(n)
Saralash: Timsort (ingl. Timsort) Quyidagi saralash usullarining gibridi: kiritish orqali saralash va birlashtirish orqali saralash. Amaliy masalalarni yechishda kirish massivi ko‘pincha avvaldan saralangan kichik massivlardan tashkil topadi, degan taxminga asoslanadi O(nlog⁡n) O(nlog⁡n) O(n)
Beqaror saralash algoritmlari
Tanlash orqali saralash (ingl. Selection sort) Kirish massivini tartiblangan va tartiblanmagan qismlarga ajratadi. So‘ng ikkinchi qismdagi eng kichik elementlarni ketma-ket birinchi qismga ko‘chiradi O(n2) O(n2) O(1)
Taroq orqali saralash (ingl. Comb sort)  Quyidagining modifikatsiyasi — pufakchali saralash, unda taqqoslanadigan qiymatlar juftligi orasidagi masofa 1 ga teng emas O(n2) O(n2/2p) O(1) Algoritmik murakkabligi kattaroq bo‘lishiga qaramay, massiv hajmi uncha katta bo‘lmaganda taroq orqali saralash tezkor saralash
Shell usulida saralash (ingl. Shell sort) Quyidagining modifikatsiyasi — kiritish orqali saralash, unda taqqoslanadigan qiymatlar juftligi orasidagi masofa 1 ga teng emas O(n2) O(nlog2n) O(1)
Uyumli saralash (uyum saralashi, Heapsort) Dastlabki ma’lumotlar asosida ikkilik uyum quriladi va unda eng kichik qiymatlar ketma-ket yig‘iladi O(nlog⁡n) O(nlog⁡n) O(1)
Silliq saralash (ingl. Smoothsort) Quyidagining modifikatsiyasi — uyumli saralash, qisman tartiblangan massivni saralashni optimallashtiradi O(nlog⁡n) O(nlog⁡n) O(n)
Tezkor saralash (ingl. Quicksort) Tayanch element p tanlanadi. p dan kichik barcha kalitlar uning chap tomoniga, p dan katta yoki unga teng barcha kalitlar esa o‘ng tomoniga ko‘chiriladi. Keyin algoritm rekursiv ravishda har bir qismga qo‘llanadi O(n2) O(nlog⁡n) O(log⁡n)
Introspektiv saralash (ingl. Introsort)  Ikki saralash usulining birikmasi: tezkor va uyumli saralash. O(nlog⁡n) O(nlog⁡n) O(n)
Stooge saralashi (ingl. Stooge sort) Agar kerak bo‘lsa, massivning birinchi va oxirgi elementlarini o‘rin almashtiradi. So‘ng massivni uch qismga ajratadi va har bir qismda algoritmni rekursiv ravishda ishga tushiradi O(nlog⁡3/log⁡1.5)

=O(n2.709...)

O(n2.709...) O(1) Usul amerikalik «Three stooges» («Uch tentak») komik guruh nomi bilan atalgan. O‘xshashlik shundaki, algoritm massivning allaqachon saralangan uchdan bir qismlari bo‘ylab betartib harakatlanadi.
Amaliyotda qo‘llashga yaroqsiz saralash algoritmlari
Bogosort Massiv saralangan holatga kelguniga qadar tasodifiy aralashtiriladi Cheklanmagan O(n!) O(1) Faqat akademik maqsadlarda qo‘llanadi
O‘rin almashtirish orqali saralash Massivning barcha mumkin bo‘lgan ketma-ketliklari hosil qilinadi va ulardan tartiblangani tanlab olinadi O(n!) O(n!) O(n) Faqat akademik maqsadlarda qo‘llanadi
Gravitatsion saralash (ingl. Bead sort) Sonlar sterjenlardagi munchoqlar ko‘rinishida tasvirlanadi, so‘ng gravitatsiya ta’sirida saralanadi O(n) O(n) O(n2) Maxsus apparat ta’minoti talab etiladi
Taqqoslashga asoslanmaydigan algoritmlar
Chelakli saralash (ingl. Bucket sort) Elementlar qiymatlar diapazoniga muvofiq chelaklarga taqsimlanadi, so‘ng har bir chelak rekursiv ravishda saralanadi O(n2) O(n2+n/k+k) O(n+k) k — oldindan ma’lum bo‘lgan chelaklar soni
Razryadlar bo‘yicha saralash (ingl. Radix sort) Massiv sonlarni razryadlar bo‘yicha taqqoslash asosida saralanadi O(wn) O(wn) O(n) w — har bir kalitni saqlash uchun zarur bo‘lgan bitlar soni.
Sanash orqali saralash (ingl. Counting sort) Massivdagi kalitlar diapazoniga kiruvchi har bir butun sonning uchrash soni hisoblanadi. So‘ng noldan farqli qiymatlarning barchasi chiqariladi O(n+k) O(n+k) O(n+k) k — kalit elementlarining eng katta qiymati

Satrlarni saralash

Saralash algoritmlarining keng tarqalgan qo‘llanish sohalaridan biri — satrlarni saralash. Umumlashtirilgan algoritm quyidagicha bo‘lishi mumkin: avval satrlar to‘plami har bir satrning birinchi belgisi bo‘yicha saralanadi, so‘ng birinchi belgisi bir xil bo‘lgan satrlar to‘plamining har bir qismi ikkinchi belgi bo‘yicha saralanadi va shu tariqa barcha satrlar tartibga kelguncha davom etadi. Bunda mavjud bo‘lmagan belgi (uzunligi N bo‘lgan satr uzunligi N+1 bo‘lgan satr bilan taqqoslanganda) har qanday belgidan kichik deb hisoblanadi.

Sonlarni odatiy yozuv shaklida ifodalovchi satrlarga ushbu usulni qo‘llash kutilmagan natijalar beradi: masalan, «9» «11» dan katta bo‘lib chiqadi, chunki birinchi satrning birinchi belgisi ikkinchi satrning birinchi belgisidan kattaroq qiymatga ega. Bu muammoni bartaraf etish uchun saralash algoritmi saralanayotgan satrlarni sonlarga aylantirib, ularni son sifatida saralashi mumkin. Bunday algoritm «sonli saralash», avval tavsiflangan usul esa «satrli saralash» deb ataladi. Amaliyotda sonlarni o‘z ichiga olgan satrlarni saralash muammosini hal qilishning samarali usullaridan biri — son oldiga ma’lum miqdorda nol qo‘shishdir. Shunda «011» «009» dan katta deb hisoblanadi.

Adabiyotlar

Havolalar