Kompyuter ilmlari va dasturlashtirish
Radix Sort-dan foydalanish cheklovlari
Download 75.97 Kb.
|
3 mustaqil ish D
|
Radix Sort-dan foydalanish cheklovlari:
Radix Saralash Boshqa saralash usullaridan farqli o'laroq, radix saralash kalitlarning tuzilishini ko'rib chiqadi Kalitlar M tayanchda ifodalangan deb faraz qiling sanoq tizimi (M = radix), ya'ni M = 2 bo'lsa, kalitlar ikkilik tizimda ifodalanadi Saralash dagi bitlarni solishtirish orqali amalga oshiriladi bir xil pozitsiya Alfanumerik kalitlarga kengaytma torlar Radix almashinuvi tartibi Bitlarni chapdan o'ngga qarab tekshiring: Eng chap bitga nisbatan massivni tartiblang Bo'lim massivi Rekursiya yuqori pastki qatorni rekursiv tartiblash, eng chap qismiga e'tibor bermaslik pastki pastki qatorni rekursiv saralash, eng chap qismiga e'tibor bermaslik Vaqt: O(b N) Radix almashinuvi tartibi Oldingi sahifadagi tartibni qanday qilamiz? Quicksort-dagi bo'lim bilan bir xil g'oya.Takrorlang 1 bilan boshlanadigan kalitni topish uchun yuqoridan pastga qarab skanerlang; 0 bilan boshlanadigan kalitni topish uchun pastdan yuqoriga skanerlang; kalitlarni almashtirish; skanerlash indekslari kesishmaguncha; Radix almashinuvi tartibi Radix Exchange Sort va boshqalar. Tez tartiblash O'xshashliklar ikkala bo'lim massivi ikkala kichik massivlarni rekursiv tartiblash Farqlar • Bo'lish usuli • radix almashinuvi massivni quyidagilarga bo'linadi 2b-1 dan katta yoki kamroq • kattaligiga asoslangan bo'limlarni tezkor saralash massivning qaysidir elementidan yoki undan kam • Vaqt murakkabligi • Radiks almashinuvi O (bN) • Tez tartiblash oʻrtacha O harfi (N log N) • Tezkor saralash eng yomon holat O (N2 ) To'g'ri Radix Saralash k uchun:= 0 dan b−1 gacha massivni barqaror tarzda tartiblang, “Saralash” nimani anglatishini unutibman barqaror tarzda"!!! Barqaror turda, tengning boshlang'ich nisbiy tartibi kalitlari o'zgarmaydi. Misol uchun, tartibning birinchi bosqichiga e'tibor bering oldingi sahifadan: Download 75.97 Kb. Do'stlaringiz bilan baham: 
|