Algoritmlar nazariyasining boshlang’ich tushunchalari

BINGO SORT:: BINGO SORT

Tanlashning qiziqarli xususiyati - tezlikning saralangan ma'lumotlarning tabiatidan mustaqilligi.
Misol uchun, agar massiv deyarli tartiblangan bo'lsa, siz bilganingizdek, kiritish tartiblash uni tezroq (hatto tezkor saralashdan ham tezroq) qayta ishlaydi. Va qo'shimchalar bo'yicha saralash uchun teskari tartiblangan massiv degenerativ holat bo'lib, uni imkon qadar uzoq vaqt saralaydi.
Tanlovni saralash uchun massivni qisman yoki teskari tartiblash rol o'ynamaydi - u uni oddiy tasodifiy tartiblash bilan bir xil tezlikda qayta ishlaydi. Bundan tashqari, klassik tanlash saralash uchun massiv noyob yoki takrorlanuvchi elementlardan iboratmi, muhim emas - bu amalda tezlikka ta'sir qilmaydi.
Lekin printsipial jihatdan, siz algoritmni aldashingiz va o'zgartirishingiz mumkin, shunda u ba'zi ma'lumotlar to'plamlari bilan tezroq ishlaydi. Misol uchun, bingo sort massiv ikki nusxadagi elementlardan iborat bo'lsa, hisobga oladi.

Bu erda hiyla shundaki, tartibsiz qismda nafaqat maksimal element eslab qolinadi, balki keyingi iteratsiya uchun maksimal ham aniqlanadi. Bu takroriy maksimallar bilan ularni har safar yana qidirmaslik, balki massivda bu maksimalga yana bir bor uchrashi bilanoq darhol o'z o'rniga qo'yish imkonini beradi.

Algoritmik murakkablik bir xil bo'lib qolmoqda. Ammo agar massiv takrorlanuvchi raqamlardan iborat bo'lsa, bingo sort buni oddiy tanlashdan o'nlab marta tezroq bajaradi.
# Bingo sort def bingo(ma'lumotlar): # Birinchi o'tish. max = len(ma'lumotlar) - 1 keyingiValue = diapazondagi i uchun ma'lumotlar (maks - 1, -1, -1): agar ma'lumotlar[i] > keyingiValue: keyingiValue = ma'lumotlar[i] esa maksimal va ma'lumotlar == keyingiValue: maks -= 1 # Keyingi o'tishlar. maksimal: qiymat = keyingiValue keyingiValue = diapazondagi i uchun ma'lumotlar (maks - 1, -1, -1): agar ma'lumotlar[i] == qiymat: ma'lumotlar[i], ma'lumotlar = ma'lumotlar, ma'lumotlar[i] maks -= 1 elif ma'lumoti[i] > keyingiValue: keyingiValue = ma'lumotlar[i] esa maksimal va ma'lumotlar == keyingiValue: maks -= 1 ma'lumotni qaytaradi