Sharof rashidov nomidagi samarqand davlat universiteti amaliy matematika yo

Algoritmlarni taqqoslash va Taqqoslash turlari

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-sotiqlari va 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.
Tasnifi
Saralash algoritmlari ko'pincha quyidagicha tasniflanadi:
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.
Barqaror 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 jurnal² n degani (log n)².

Taqqoslash turlari

Quyida jadval mavjud taqqoslash turlari. Taqqoslash tartibini quyidagidan ko'ra yaxshiroq bajarish mumkin emas O(n jurnal n).
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). 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 ≪ 2^k, bu erda ≪ "nisbatan kamroq" degan ma'noni anglatadi.
Namunalar ma'lumotlarning bir nechta chelaklarga samarali ravishda taqsimlanishi va keyin bir nechta protsessorlarga saralashni o'tqazish orqali taqqoslanmaydigan turlarning har qandayini parallel qilish uchun ishlatilishi mumkin, chunki chelaklar allaqachon bir-birlari orasida tartiblangan.