Saralash algoritmlari va ularning hisoblash dasturlari



Download 96,78 Kb.
bet1/3
Sana21.04.2022
Hajmi96,78 Kb.
#568617
  1   2   3
Bog'liq
Saralash algoritmlari va ularning hisoblash dasturlari


Saralash algoritmlari va ularning hisoblash dasturlari
Kirish
I-bob.Asosiy qism

  1. Bubble sort;

  2. Selection sort;

  3. Insertion sort;

  4. Quick sort;

  5. Merge sort.

Xulosa
Adabiyotlar
Kirish
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:

  1. Chiqish kamaytirilmaydigan tartibda (har bir element kerakli darajada oldingi elementdan kam emas umumiy buyurtma);

  2. 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.

Bu holatda Heap, Merge, Quick sort kabi algoritmlar o’z ishini boshidagi 3 ta algoritmdan ko’ra ancha tez yakunlayapti.
Endi esa bu misolga e’tibor bering. Endi saralanishi kerak bo’lgan ma’lumotlar to’liq bo’lmasa ham, deyarli saralangan holatda:
Bu holda e’tibor bergan bo’lsangiz, Insertion sort (birinchi turgani) algoritmi yuqorida aytilgan murakkab algoritmlardan ko’ra bir necha barobar tez ishlashini ko’rishingiz mumkin.
Biz yuqorida faqat ikki xil holatni, ixtiyoriy va deyarli saralangan ma’lumotlarni saralagan holatni ko’rib chiqdik. Bunday holatlar esa ko’plab topiladi, masalan teskari saralangan, bir turdagi ma’lumotlar ko’p yoki kam bo’lgan va h.k ma’lumotlarni saralash. Har bir holat uchun ma’lum bir algoritmlar qolganlaridan ko’ra tezroq yoki sekinroq ishlab qolishi mumkin.

  • Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.

Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi.
Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi.
Yana haqli savol tug’ilishi mumkin, “Bu narsaning kimga keragi bor, baribir natija 1 1 2 3 4 5 bo’ladiku?” degan. Albatta, bu holatda turg’unlik ahamiyati sezilmasligi mumkin. Lekin, aytaylik siz biror korxona ishchilari ma’lumotlarini ularning nomiga ko’ra saralagan paytda turg’unlik kerak bo’lib qolishi mumkin. Ya’ni, birinchi Nodirbek ma’lumotlari, ikkinchi Nodirbek ma’lumotlaridan keyin turishi kerak degan kabi.
Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor).
Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi.
Tasavvur qilaylik sizda telefon raqamlari saqlanadigan daftarchasi bor (hali qo’l telefonlari ommalashmagan vaqtni eslang) va undagi nomlar tartibsiz holda yozilgan. Siz, aytaylik, Nodir ismli do’stingizning raqamini topishingiz uchun bu daftarchani boshidan boshlab axtarib chiqishga majbur bo’lasiz, bu esa ko’p vaqtni oladi. Lekin, agar ular alifbo tartibida saralab qo’yilgan bo’lsa, siz to’g’ri N harfiga o’tib izlashni boshlaysiz va vaqtdan bir necha barobarga yutasiz. (Chiziqli va Ikkilik saralash mavzularini eslang)
Biz bu bo’limda saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni nazarda tutamiz va bu kabi saralash algoritmlarining olti xilini ko’rib chiqamiz:
Selection sort (Tanlab saralash)
Bubble sort (Pufakchali saralash)
Insertion sort (Joylashtirib saralash)
Quick sort (Tezkor saralash)
Merge sort (Qo’shib saralash)
Radix sort
Ularning deyarli hammasi (6-sidan tashqari) ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.
Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:
Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.
Buni tushunish uchun quyidagi misolni keltiramiz. Bu yerda turli xil saralash algoritmlarining ishlashi vizual holda bir biri bilan taqqoslangan. Birinchi holatda kiruvchi ma’lumotlar, ya’ni saralanishi kerak bo’lgan ma’lumotlar ixtiyoriy turda va holatda:
Hisoblashning boshidan boshlab, saralash muammosi juda ko'p tadqiqotlarni jalb qildi, ehtimol bu oddiy, tanish bayonotga qaramay, uni samarali hal qilishning murakkabligi tufayli. Dastlabki saralash algoritmlari mualliflari orasida 1951 yil ham bo'lgan Betti Xolberton (tug'ilgan Snayder), kim ishlagan ENIAC va UNIVAC.[1][2] Bubble sort 1956 yilidayoq tahlil qilingan.[3] Taqqoslash tartiblash algoritmlari asosiy talabga ega Ω (n jurnal n) taqqoslashlar (ba'zi kirish ketma-ketliklari ko'paytmani talab qiladi n jurnal n taqqoslashlar, bu erda n - qatorga ajratiladigan elementlar soni). Kabi taqqoslashga asoslanmagan algoritmlar hisoblash turi, yaxshi ishlashga ega bo'lishi mumkin. Asimptotik optimal algoritmlar 20-asr o'rtalaridan beri ma'lum bo'lgan - foydali yangi algoritmlar hali ham ixtiro qilinmoqda, hozirda keng qo'llanilmoqda Timsort 2002 yilga tegishli va kutubxona birinchi marta 2006 yilda nashr etilgan.
Kirish qismida saralash algoritmlari keng tarqalgan Kompyuter fanlari masalan, algoritmlarning ko'pligi turli xil asosiy algoritm tushunchalari bilan yumshoq tanishishni ta'minlaydigan sinflar. katta O yozuvlari, algoritmlarni ajratish va yutish, ma'lumotlar tuzilmalari kabi uyumlar va ikkilik daraxtlar, tasodifiy algoritmlar, eng yaxshi, eng yomon va o'rtacha ish tahlil, vaqt-makon savdo-sotiqlariva yuqori va pastki chegaralar.
Kichik massivlarni maqbul (hech bo'lmaganda taqqoslash va almashtirish) yoki tez (masalan, mashinaning o'ziga xos tafsilotlarini hisobga olgan holda) saralash hali ham juda kichik massivlar uchun ma'lum bo'lgan echimlarga ega bo'lgan ochiq tadqiqot muammosi (<20 element). Xuddi shunday maqbul (har xil ta'rifga ko'ra) parallel mashinada saralash ham ochiq tadqiqot mavzusi.
Saralash algoritmlari ko'pincha quyidagicha tasniflanadi:
Hisoblashning murakkabligi (eng yomon, o'rtacha va eng yaxshi xatti-harakatlar) ro'yxat kattaligi bo'yicha (n). Odatda ketma-ket tartiblash algoritmlari uchun yaxshi xatti-harakatlar O (n jurnaln), parallel saralash bilan O (log2 n) va yomon xulq O (n2). (Qarang Big O notation.) Ketma-ket tartiblash uchun ideal xatti-harakatlar O (n), ammo bu o'rtacha holatda bu mumkin emas. Optimal parallel saralash O (log)n). Taqqoslashga asoslangan saralash algoritmlari kamida need (kerakn jurnaln) ko'pgina kirishlar uchun taqqoslashlar.
Hisoblashning murakkabligi svoplar ("joyida" algoritmlari uchun).
Xotira foydalanish (va boshqa kompyuter resurslaridan foydalanish). Xususan, ba'zi bir saralash algoritmlari "joyida". To'liq aytganda, joyida tartiblash tartiblangan narsalardan tashqari faqat O (1) xotiraga muhtoj; ba'zan O (log (n)) qo'shimcha xotira "joyida" deb hisoblanadi.
Rekursiya. Ba'zi algoritmlar rekursiv yoki rekursiv bo'lmagan, boshqalari esa ikkalasi ham bo'lishi mumkin (masalan, birlashtirish navi).
Barqarorlik: barqaror saralash algoritmlari yozuvlarning nisbiy tartibini teng tugmachalar (ya'ni, qiymatlar) bilan saqlash.
Ular yo'qmi yoki yo'qmi a taqqoslash. Taqqoslash saralashi ma'lumotlarni faqat taqqoslash operatori bilan taqqoslash orqali tekshiradi.
Umumiy usul: qo'shish, almashtirish, tanlash, birlashtirish, va boshqalar. Birja turlariga pufakchali saralash va tezkor kort kiradi. Tanlash turlariga shaker sort va hepsort kiradi.
Algoritm ketma-ket yoki parallel bo'ladimi. Ushbu munozaraning qolgan qismi deyarli faqat ketma-ket algoritmlarga asoslangan va ketma-ket ishlashni nazarda tutadi.
Moslashuvchanlik: Kirishning oldindan belgilanishi ish vaqtiga ta'sir qiladimi yoki yo'qmi. Buni hisobga oladigan algoritmlar ma'lum moslashuvchan.
Barqaror saralash algoritmlari takrorlangan elementlarni kiritishda paydo bo'ladigan tartibda tartiblaydi. Ma'lumotlarning ayrim turlarini saralashda saralash tartibini aniqlashda ma'lumotlarning faqat bir qismi tekshiriladi. Masalan, o'ng tomonda kartalarni saralash misolida kartalar ularning darajalariga qarab saralanmoqda va ularning kostyumiga e'tibor berilmaydi. Bu asl ro'yxatning turli xil to'g'ri tartiblangan versiyalarini olish imkoniyatini beradi. Barqaror saralash algoritmlari, ulardan birini quyidagi qoidaga binoan tanlaydi: agar ikkita 5 ta karta singari ikkita narsa teng taqqoslansa, unda ularning nisbiy tartibi saqlanib qoladi, shuning uchun agar kiritishda biri ikkinchisidan oldin kelsa, u ham bo'ladi chiqishda bir-biridan oldin keling.
Barqarorlik quyidagi sabablarga ko'ra muhimdir: ism va sinf qismidan iborat bo'lgan talabalar yozuvlari veb-sahifada dinamik ravishda, avval nomi bilan, so'ngra ikkinchi bo'limda sinf bo'limi bo'yicha tartiblanganligini ayting. Agar har ikkala holatda ham tartiblashning barqaror algoritmi ishlatilsa, "sinflar bo'yicha bo'lim" operatsiyasi nom tartibini o'zgartirmaydi; beqaror tartib bilan, bo'lim bo'yicha saralash nom tartibini aralashtirib yuborishi mumkin. Barqaror saralashdan foydalanib, foydalanuvchilar birinchi navbatda ism yordamida saralash orqali, so'ngra bo'lim yordamida yana saralash orqali bo'limlar bo'yicha, so'ngra ismlar bo'yicha saralashni tanlashi mumkin, natijada ismlar tartibi saqlanib qoladi. (Ba'zi bir elektron jadval dasturlari ushbu xatti-harakatga bo'ysunadi: ismlar bo'yicha saralash, keyin bo'lim bo'yicha talabalarning alifbo ro'yxati bo'limlar bo'yicha berilgan.)
Rasmiy ravishda, saralangan ma'lumotlar yozuvlar yoki qiymatlar to'plami sifatida ifodalanishi mumkin, va saralash uchun ishlatiladigan qismning nomi kalit. Karta misolida kartalar yozuv (martaba, kostyum) sifatida aks ettirilgan, asosiysi unvon. Saralash algoritmi barqaror bo'ladi, agar har doim bir xil kalitga ega ikkita R va S yozuvlar bo'lsa va R asl ro'yxatda S dan oldin paydo bo'lsa, u holda R har doim saralangan ro'yxatda S dan oldin paydo bo'ladi.
Agar teng elementlarni ajratib bo'lmaydigan bo'lsa, masalan, butun sonlar bilan yoki umuman olganda, butun element kalit bo'lgan har qanday ma'lumotlar, barqarorlik muammo emas. Barcha kalitlar boshqacha bo'lsa, barqarorlik ham muammo emas.
Barqaror bo'lish uchun beqaror saralash algoritmlari maxsus qo'llanilishi mumkin. Buning bir usuli - bu kaliti taqqoslashni sun'iy ravishda kengaytirishdir, shunda aks holda teng kalitlarga ega bo'lgan ikkita ob'ektni taqqoslash dastlabki kirish ro'yxatidagi yozuvlar tartibini taqiqlovchi sifatida ishlatishga qaror qilinadi. Biroq, ushbu buyurtmani eslab qolish qo'shimcha vaqt va joy talab qilishi mumkin.
B
arqaror saralash algoritmlari uchun bitta dastur - bu asosiy va ikkilamchi kalit yordamida ro'yxatni saralash. Masalan, biz kartochkalarni kostyumlar buyurtma klublarida (♣), olmos (♦), qalblar (♥), belkurak (♠) va har bir kostyum ichida kartalar darajaga qarab tartiblanadi. Buni birinchi navbatda kartalarni tartib bo'yicha saralash (har qanday turdan foydalanib), so'ngra kostyum bo'yicha barqaror tartiblash orqali amalga oshirish mumkin:
Har bir kostyum ichida barqaror tur allaqachon bajarilgan darajaga qarab tartibni saqlaydi. Ushbu fikr har qanday sonli tugmachalarga kengaytirilishi mumkin va ulardan foydalaniladi radiks sort. Leksikografik kalit taqqoslash yordamida, masalan, avval kostyum bilan taqqoslanadigan, so'ngra kostyumlar bir xil bo'lsa, daraja bo'yicha taqqoslanadigan usul yordamida beqaror turga erishish mumkin.
Algoritmlarni taqqoslash
Ushbu jadvalda, n saralanadigan yozuvlar soni. "O'rtacha" va "Eng yomoni" ustunlari quyidagilarni beradi vaqtning murakkabligi har bir holda, har bir tugmachaning uzunligi doimiy va shuning uchun barcha taqqoslashlar, almashtirishlar va boshqa kerakli operatsiyalar doimiy vaqt ichida davom etishi mumkin degan taxmin ostida. "Xotira", xuddi shu taxmin asosida, ro'yxatning o'zi ishlatadigan hajmdan tashqarida zarur bo'lgan qo'shimcha saqlash hajmini bildiradi. Ishlash vaqtlari va quyida keltirilgan xotira talablari uning ichida bo'lishi kerak katta O yozuvlari, shuning uchun logarifmlarning asosi muhim emas; yozuv jurnal2 n degani (log n)2.
Taqqoslanmaydigan turlar
Quyidagi jadvalda tasvirlangan butun sonni saralash bo'lmagan algoritmlar va boshqa saralash algoritmlari taqqoslash turlari. Shunday qilib, ular cheklanib qolmaydi Ω(n jurnal n).[15] Quyidagi murakkabliklar taxmin qilinadi n o'lchamlari tugmachalari bilan saralash kerak bo'lgan narsalar k, raqam kattaligi dva r saralanadigan raqamlar diapazoni. Ularning aksariyati kalit hajmi etarlicha katta, chunki barcha yozuvlar noyob kalit qiymatlarga ega bo'lishi mumkin va shuning uchun n ≪ 2k, bu erda ≪ "nisbatan kamroq" degan ma'noni anglatadi. Birlik tannarxida tasodifiy kirish mashinasi modeli, ishlash vaqti bilan algoritmlar {displaystyle scriptstyle ncdot {frac {k} {d}}}, masalan, radix sort, shunga mutanosib vaqt talab etadi Θ (n jurnal n), chunki n dan oshmasligi bilan cheklangan 2 ^ {frac {k} {d}}va saralash uchun ko'proq sonli elementlar kattaroq qismini talab qiladi k ularni xotirada saqlash uchun.
Boshqalar
Ba'zi algoritmlar yuqorida muhokama qilinganlarga nisbatan sust, masalan bogosort cheklanmagan ish vaqti va stoge sort qaysi bor O(n2.7) ishlash vaqti. Ushbu turlar odatda algoritmlarning ishlash vaqtini qanday baholashini ko'rsatish uchun ta'lim maqsadida tavsiflanadi. An'anaviy dasturiy ta'minot kontekstida real hayotda foydalanish uchun foydasiz bo'lgan ba'zi bir saralash algoritmlari quyidagi jadvalda juda yomon ishlashi yoki ixtisoslashtirilgan apparat talablari tufayli tasvirlangan.
Nazariy kompyuter olimlari, bundan yaxshiroqini ta'minlaydigan boshqa saralash algoritmlarini batafsil bayon qildilar O(n jurnal n) qo'shimcha cheklovlarni o'z ichiga olgan vaqtning murakkabligi, shu jumladan:
Thorup algoritmi, cheklangan kattalikdagi domendan kalitlarni saralash uchun tasodifiy algoritm O(n log log n) vaqt va O(n) bo'sh joy.
Tasodifiy butun sonni saralash algoritmni qabul qilish {displaystyle Oleft (n {sqrt {log log n}} ight)} kutilgan vaqt va O(n) bo'sh joy.
Mashhur saralash algoritmlari
Saralash algoritmlari juda ko'p bo'lsa-da, amaliy dasturlarda bir nechta algoritmlar ustunlik qiladi. Kiritish saralashi kichik ma'lumotlar to'plamlari uchun keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun asimptotik jihatdan samarali saralash, birinchi navbatda, yig'indilarni saralash, birlashtirish tartiblari yoki tezkorlar. Samarali dasturlar odatda a dan foydalanadi gibrid algoritm, umumiy saralash uchun asimptotik jihatdan samarali algoritmni rekursiyaning pastki qismidagi kichik ro'yxatlar uchun qo'shish bilan birlashtirish. Yuqori darajada sozlangan dasturlar kabi murakkab variantlardan foydalaniladi, masalan Timsort (birlashtirish saralash, qo'shish tartibini va qo'shimcha mantiq), Android, Java va Python-da ishlatiladigan va introsort (quicksort va heap sort), ba'zilarida ishlatilgan (variant shaklida) C ++ saralash dasturlari va .NET-da.
Belgilangan oraliqdagi raqamlar kabi cheklangan ma'lumotlar uchun, tarqatish turlari sanash sort yoki radix sort kabi keng qo'llaniladi. Bubble sort va variantlari amalda kamdan kam qo'llaniladi, lekin odatda o'quv va nazariy munozaralarda uchraydi.
Ob'ektlarni jismoniy tartiblashda (masalan, qog'ozlar, testlar yoki kitoblar) alfavit qilishda odamlar intuitiv ravishda odatda kichik to'plamlar uchun qo'shilish turlaridan foydalanadilar. Kattaroq to'plamlar uchun odamlar ko'pincha birinchi chelakni, masalan, boshlang'ich harflar bilan, va bir nechta chelaklar juda katta to'plamlarni amaliy saralashga imkon beradi. Ko'pincha bo'shliq nisbatan arzon, masalan, erga yoki katta maydonga narsalarni yoyish, ammo operatsiyalar qimmatga tushadi, ayniqsa ob'ektni uzoq masofaga ko'chirish - mos yozuvlar joylashuvi muhim ahamiyatga ega. Birlashtirish turlari jismoniy ob'ektlar uchun ham amaliydir, chunki ikkita qo'l ishlatilishi mumkin, har bir ro'yxat birlashtirilishi mumkin, boshqa algoritmlar, masalan, yig'ish tartibida yoki tezkor tartiblash, odam uchun juda mos emas. Kabi boshqa algoritmlar kutubxona, bo'sh joy qoldiradigan qo'shilish tartibining bir varianti ham jismoniy foydalanish uchun amaliydir.
Oddiy navlar
Eng oddiy ikkita turdan biri - qo'shimchalarni saralash va tanlash saralashi, ikkalasi ham kichik ma'lumotlarda samarali bo'ladi, chunki qo'shimcha xarajatlar past, ammo katta ma'lumotlarda samarali emas. Kiritish saralashi amalda tanlov saralashiga qaraganda tezroq bo'ladi, chunki taqqoslashlar kamligi va deyarli saralangan ma'lumotlarda yaxshi ishlashi va shuning uchun amalda afzal ko'rilgan, ammo tanlov saralash kamroq yozishlardan foydalanadi va shu bilan yozish ishlashi cheklovchi omil bo'lganda ishlatiladi.
Kiritish tartibi
Kiritish tartibi kichik saralashlar va asosan saralangan ro'yxatlar uchun nisbatan samarali bo'lgan va ko'pincha murakkab algoritmlarning bir qismi sifatida ishlatiladigan oddiy saralash algoritmidir. Bu ro'yxatdagi elementlarni birma-bir olish va ularni o'zlarining to'g'ri holatiga hamyonimizga qanday pul qo'yishimizga o'xshash yangi tartiblangan ro'yxatga kiritish orqali ishlaydi.[22] Massivda yangi ro'yxat va qolgan elementlar massivning bo'sh joyini bo'lishishi mumkin, ammo kiritish juda qimmat, shuning uchun quyidagi barcha elementlarni birma-bir almashtirish kerak. Shellsort (quyida ko'rib chiqing) - bu katta ro'yxatlar uchun samaraliroq bo'lgan qo'shilish tartibining bir variantidir.
Tanlov tartibida
Tanlov tartibida bu joyida taqqoslash. Unda bor O(n2) murakkabligi, uni katta ro'yxatlarda samarasiz qiladi va umuman o'xshashidan yomonroq ishlaydi qo'shish tartibi. Tanlovni saralash soddaligi bilan ajralib turadi, shuningdek, muayyan vaziyatlarda murakkab algoritmlarga nisbatan ishlashning afzalliklariga ega.
Algoritm minimal qiymatni topadi, uni birinchi holatdagi qiymat bilan almashtiradi va ro'yxatning qolgan qismida ushbu amallarni takrorlaydi.[23] Bu ko'proq emas n almashtirish, shuning uchun almashtirish juda qimmat bo'lgan joyda foydalidir.
Samarali navlar
Amaliy umumiy saralash algoritmlari deyarli har doim o'rtacha vaqt murakkabligi (va umuman olganda eng yomon holatdagi murakkablik) algoritmiga asoslanadi.n jurnal n), ulardan eng keng tarqalgani - yig'ma saralash, birlashma va tezkor tortish. Ularning har birining afzalliklari va kamchiliklari bor, eng muhimi, birlashma tartibini oddiy amalga oshirish O (n) qo'shimcha maydon va tezkor kortni oddiy bajarish O (n2) eng yomon murakkablik. Ushbu muammolarni yanada murakkab algoritm evaziga hal qilish yoki yaxshilash mumkin.
Ushbu algoritmlar tasodifiy ma'lumotlarda asimptotik jihatdan samarali bo'lsa, real ma'lumotlar uchun amaliy samaradorlik uchun turli xil modifikatsiyalar qo'llaniladi. Birinchidan, ushbu algoritmlarning qo'shimcha xarajatlari kichikroq ma'lumotlarda muhim ahamiyat kasb etadi, shuning uchun ko'pincha gibrid algoritm ishlatiladi, odatda ma'lumotlar etarlicha kichik bo'lgandan so'ng qo'shish tartibiga o'tadi. Ikkinchidan, algoritmlar allaqachon saralangan ma'lumotlar yoki deyarli saralangan ma'lumotlarda yomon ishlaydi - bular real dunyo ma'lumotlarida keng tarqalgan va ularni O (n) tegishli algoritmlar bo'yicha vaqt. Nihoyat, ular ham bo'lishi mumkin beqarorva barqarorlik ko'pincha biron bir tarzda kerakli xususiyatdir. Shunday qilib, ko'pincha murakkab algoritmlardan foydalaniladi, masalan Timsort (birlashma tartibiga asoslangan) yoki introsort (tez yig'ilishga asoslangan holda, yana uyumga tushish).
Saralashni birlashtirish
Saralashni birlashtirish allaqachon saralangan ro'yxatlarni yangi tartiblangan ro'yxatga birlashtirish qulayligidan foydalanadi. Har ikkala elementni taqqoslash bilan boshlanadi (ya'ni, 1 bilan 2, keyin 3 bilan 4 ...) va agar birinchisi ikkinchisidan keyin kelishi kerak bo'lsa, ularni almashtirish. Keyinchalik, natijada olingan ikkita ro'yxatning har birini to'rtta ro'yxatga birlashtiradi, so'ngra to'rtta ro'yxatni birlashtiradi va hokazo; oxirgi ikki ro'yxat yakuniy saralangan ro'yxatga birlashtirilguncha.[24] Bu erda tavsiflangan algoritmlardan biri bu juda katta ro'yxatlarning o'lchovidir, chunki uning eng yomon ish vaqti O (n jurnal n). Bundan tashqari, u nafaqat massivlarga, balki ro'yxatlarga ham osonlikcha qo'llaniladi, chunki u tasodifiy kirishni emas, balki ketma-ket kirishni talab qiladi. Biroq, u qo'shimcha O (n) kosmik murakkablik va oddiy dasturlarda juda ko'p nusxalarni o'z ichiga oladi.
Birlashtirish navi murakkab algoritmda ishlatilganligi sababli amaliy qo'llanmalar uchun nisbatan yaqinda ommalashgan Timsort, bu dasturlash tillarida standart tartib uchun ishlatiladi Python[25] va Java (sifatida JDK7[26]). Birlashtirish tartibining o'zi odatdagi tartibdir Perl,[27] boshqalar qatorida va kamida 2000 yildan beri Java-da ishlatilgan JDK1.3.[28]
Heapsort
Heapsort ning ancha samarali versiyasidir tanlov saralash. Shuningdek, u ro'yxatning eng katta (yoki eng kichik) elementini aniqlab, ro'yxatning oxiriga (yoki boshiga) qo'yib, so'ngra ro'yxatning qolgan qismida davom etish orqali ishlaydi, ammo bu vazifani a deb nomlangan ma'lumotlar tuzilishi yordamida samarali bajaradi. uyum, maxsus turi ikkilik daraxt.[29] Ma'lumotlar ro'yxati uyumga aylantirilgandan so'ng, ildiz tuguni eng katta (yoki eng kichik) element bo'lishiga kafolat beradi. U olib tashlanib, ro'yxatning oxiriga qo'yilganda, uyum qayta tartibga solinadi, shunda qolgan eng katta element ildizga o'tadi. To'pni ishlatib, keyingi eng katta elementni topish O (log) ni oladi n) O, o'rniga vaqt (n) oddiy tanlov tartibidagi kabi chiziqli skanerlash uchun. Bu Heapsort-ga O (n jurnal n) vaqt, va bu ham eng yomon murakkablik.
Quicksort
Quicksort a algoritmni ajratish va yutish a ga asoslangan bo'lim operatsiya: massivni ajratish, element deb nomlangan burilish tanlangan.[30][31] Burilishdan kichik bo'lgan barcha elementlar undan oldin va barcha katta elementlar undan keyin harakatlanadi. Buni chiziqli vaqt ichida samarali bajarish mumkin va joyida. Keyinchalik kichik va katta sublistlar rekursiv tartibda saralanadi. Bu o'rtacha vaqt murakkabligini O (n jurnal n), kam xarajatli va shuning uchun bu mashhur algoritm. Quicksort-ning samarali qo'llanilishi (joyida bo'linish bilan) odatda beqaror va biroz murakkab, ammo amalda eng tez tartiblash algoritmlari qatoriga kiradi. Uning oddiy O (log) bilan birga n) bo'sh joydan foydalanish, tezkor saralash eng mashhur saralash algoritmlaridan biri bo'lib, ko'plab standart dasturlash kutubxonalarida mavjud.
Quicksort haqida muhim ogohlantirish shundaki, uning eng yomon ko'rsatkichi O (n2); Bu kamdan-kam hollarda, sodda dasturlarda (birinchi yoki oxirgi elementni pivot sifatida tanlash) bu tartiblangan ma'lumotlar uchun sodir bo'ladi, bu odatiy hol. Quicksortdagi eng murakkab masala - bu yaxshi burilish elementini tanlashdir, chunki burilishlarning doimiy ravishda yomon tanlovi O ning pasayishiga olib kelishi mumkin (n2) ishlash, lekin pivotlarni yaxshi tanlash O (n jurnal n) asimptotik jihatdan maqbul bo'lgan ishlash. Masalan, agar har bir qadamda o'rtacha burilish sifatida tanlanadi, keyin algoritm O (n jurnaln). Kabi mediani topish medianlar medianasi tanlash algoritmi ammo O (n) tartiblanmagan ro'yxatlarda ishlash va shuning uchun saralash bilan katta xarajatlarni amalga oshiradi. Amalda tasodifiy burilishni tanlash deyarli aniq O (n jurnaln) ishlash.
Bubble sort oddiy tartiblash algoritmi. Algoritm ma'lumotlar to'plamining boshidan boshlanadi. U dastlabki ikkita elementni taqqoslaydi va agar birinchisi ikkinchisidan kattaroq bo'lsa, ularni almashtiradi. Ma'lumotlar to'plamining oxirigacha qo'shni elementlarning har bir juftligi uchun buni davom ettiradi. Keyin yana dastlabki ikkita element bilan boshlanadi va oxirgi o'tkazishda hech qanday svop bo'lmaguncha takrorlanadi.[33] Ushbu algoritmning o'rtacha vaqti va eng yomon ko'rsatkichi O (n2), shuning uchun u kamdan-kam hollarda katta, tartibsiz ma'lumotlar to'plamlarini saralash uchun ishlatiladi. Bubble sorti oz sonli narsalarni saralash uchun ishlatilishi mumkin (bu erda uning asimptotik samarasizligi yuqori jazo emas). Ko'pikni saralash deyarli har qanday uzunlikdagi ro'yxatda ham samarali ishlatilishi mumkin (ya'ni, elementlar sezilarli darajada joyida emas). Misol uchun, agar biron bir sonli element faqat bitta pozitsiya bilan mos kelmasa (masalan, 0123546789 va 1032547698), qabariq tartiblash almashinuvi ularni birinchi o'tish paytida tartibda oladi, ikkinchi o'tish barcha elementlarni tartibda topadi, shuning uchun tartiblash bo'ladi faqat 2 ni olingn vaqt.

Download 96,78 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish