Xulosa. Saralash algoritmi Sorting algoritmi

Insertion sort algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtirish
Reja:

1. 
   Saralash algoritmi.
   
2. 
   Algoritm barqarrorligi.
   
3. 
   Algoritm turlari.
   
4. 
   Xulosa.
   

Saralash algoritmi - Sorting algoritmi.

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);

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

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.
Tasnifi
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 (log² n) va yomon xulq O (n²). (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.
  

Barqarorlik

O'yin kartalarida barqaror turga misol. Kartalar barqaror navbati bilan saralash bo'yicha tartiblanganida, har ikkala 5-lar avval chiqarilgan tartibda bir xil tartibda qolishi kerak. Agar ular barqaror bo'lmagan tartib bilan saralansa, 5-lar qarama-qarshi tomonga o'tishi mumkin tartiblangan chiqishda tartib.
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).
modeli, ishlash vaqti bilan algoritmlar  , masalan, radix sort, shunga mutanosib vaqt talab etadi Θ (n jurnal n), chunki n dan oshmasligi bilan cheklangan  va saralash uchun ko'proq sonli elementlar kattaroq qismini talab qiladi k ularni xotirada saqlash uchun.^[16]

Taqqoslanmaydigan turlar

Boshqalar
Ba'zi algoritmlar yuqorida muhokama qilinganlarga nisbatan sust, masalan bogosort cheklanmagan ish vaqti va stoge sort qaysi bor O(n^2.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.

•