Лекция 2 Алгоритмы сортировки и поиска

radix tartiblash

• Hisoblash tartibi va uning barqarorlik xususiyatidan foydalaniladi.
• Har bir tartiblash tugmasi har bir raqami 0 dan oraliqda bo'lgan d-raqamli raqam sifatida ko'rib chiqilishi mumkin deb taxmin qilinadi.m-1.
• Har bir raqam uchun navbatma-navbat barqaror tartiblashdan foydalaning (masalan, sanash tartibi).o'ngdan chapga. Raqamlar yoki belgilar tartibini saralashhaqiqatan ham muhim.

Radix tartiblash misoli

Kerakalifbo va o'sish bo'yicha ikki belgili kodlarni tartiblash .
1) To'g'ri belgi bo'yicha sanash orqali tartiblang: . Saralashdan keyin barqarorlik tufayli X2 F2 oldida turishda davom etadi.
2) Natijani chap belgi bo'yicha sanash orqali tartiblang va kerakli narsani oling: .
Agar siz chapdan o'ngga saralashni boshlasangiz, chap belgi bo'yicha sanab tartiblashdan so'ng, siz va keyin o'ng belgi bo'yicha hisoblash orqali tartiblashdan so'ng olasiz. , siz noto'g'ri natijaga erishasiz .

Radix turdagi ish vaqti

• Agar turg'un tartib sifatida hisoblash tartiblash ishlatilsa, u holda bir raqam bo'yicha saralash vaqti D ga teng (m+n) va barcha d raqamlari uchun tartiblash vaqti D(d()m+n)).
• Agarmdoimiy bo'lsa, u holda radix tartiblashning ishlash vaqti T ga teng bo'ladi (dn).
• Agar d ham doimiy bo'lsa, u holda radix tartiblashning ishlash vaqti faqat D ga aylanadi (n).
• Sababi: radix sort hech qachon ikkita tartiblash tugmachasini bir-biri bilan solishtirmaydi, lekin hisoblash tartibida massivlarni indekslash uchun bitta raqamdan foydalanadi.