مرتب سازی مبنا

صفحه 1:
| ۱6-۲۱ ۱۵۰ ۱۸ ۴ eee مرتب سازی 1880139 روشی است که اغلب در کارهای روزمره از آن استفاده می ‎Pere te eee LCE Lee cee ey‏ ا ل ل ل کنیم ابتدا به حروف اول فامیلی آنها توجه کرده و بر این اساس آنها را مرتب می کنیم.به عبارتی دیگر اسامی به 26 دسته مرتب میشوند.دسته اول با حرف ۳" دسته دوم با حرف فا شوند و الى آخر.بديهى است كه اكر هيج نامى بيشتر از ©) حرف نداشته باشد اسامى را مم ۱ شرح می دهیم. براى هر رقم با شروع از كم ارزش ترين به با ارزش ترين رقم اين اعمال را انجام ميدهيم هر عدد را به ترتيبى كه در آرايه قرار دارد خوانده و بر اساس ارزش رقمى كه در حال يردازش است أن را در يكى از (0) صف قرار ميدهيم.سيس هر صف را با شروع از صفى ا ا ا 0 000000 1 ‎Brand‏ ل ل ا 

صفحه 2:
ا ل ا ل ل ل ل ل ‎eM ie ah eRe el ea ele)‏ تا Peer ES te ees eee ib enor SPE eS :Q(0] 11 (۳ 92 Osi Bs :Q{4] Qisip 25 0]6[: 6 977 BY 0]18[: 8 :0]9[ آرايه بعد از كذر اول ‎neh‏ ل اك 

صفحه 3:
7 Fete ble whee Tet Slee Ieee Ses) 93۳ ‏ره‎ ‎Q[3]: 33 37 ‏اناق‎ ‎0]5[: 7 :0]6[ :Q{7] 0]8[: 6 0]9[: 2 es, را 6 66,66۵,668 

صفحه 4:
pene SUSE EBC Iba) uae for (i = 1; i<=S ; i++) 95-2 00 } Pay Sa ey) for G = +;j <N;j++) i ;k=ith digit of x[j] splace x{[j] at rear of q[k] 1 for (j=0;j<10;j++) place element of q[j] in next sequential position of x { 

صفحه 5:
|1000 OB PCa 2 بدترين حالت كه 5-17 مى باشد ييجيدكى اين الكوريتم (0)11*11 و د ‎tee ep eco cn‏ 09 ۳ 

مرتب سازی مبنا ()Radix sort مرتب سازی Radixروشی است که اغلب در کارهای روزمره از آن استفاده می کنیم.مثال هنگامی که می خواهیم اسامی دانشجویان یک کالس را به ترتیب حروف الفبا مرتب کنیم ابتدا به حروف اول فامیلی آنها توجه کرده و بر این اساس آنها را مرتب می کنیم.به عبارتی دیگر اسامی به 32دسته مرتب میشوند.دسته اول با حرف ”آ“ دسته دوم با حرف ”ب“ والی آخر آغاز میشوند.در مرحله دوم هر دسته بر اساس حرف دوم فامیلی ها مرتب می شوند و الی آخر.بدیهی است که اگر هیچ نامی بیشتر از 12حرف نداشته باشد اسامی را میتوان حداکثر در 12مرحه مرتب کرد.حال این روش را برای مرتب سازی تعدادی عدد شرح می دهیم. برای هر رقم با شروع از کم ارزش ترین به با ارزش ترین رقم این اعمال را انجام میدهیم هر عدد را به ترتیبی که در آرایه قرار دارد خوانده و بر اساس ارزش رقمی که در حال پردازش است آن را در یکی از 10صف قرار میدهیم.سپس هر صف را با شروع از صفی که با رقم صفر شماره گذاری شده تا صفی که با رقم 9شماره گذاری شده است در بردار اولیه می نویسیم.وقتی این عمل برای هر رقم انجام گرفت(با شروع از رقم سمت راست به سمت رقم سمت چپ) آرایه مرتب خواهد شد. شکل زیر مراحل مرتب سازی آرایه زیر را با روش Radixنشان می دهد. 25,57,48,37,12,92,86,33 گذر اول:فقط رقم یکان اعداد را نگاه کرده و هر یک را در صف مربوطه می نویسیم. ]:Q[0 ]:Q[1 ‏Q[2]: 12 92 ‏Q[3]: 33 ]:Q[4 ‏Q[5]: 25 ‏Q[6]: 86 ‏Q[7]: 57 37 ‏Q[8]: 48 ]:Q[9 12,92,33,25,86,57,37,48: آرایه بعد از گذر اول گذر دوم :اعداد را بر اساس رقم دوم دKر یکی از صفها قرار می دKهیم. آرایKه بعد از گذر دوم که مرتب شده است ]:Q[0 ‏Q[1]: 12 ‏Q[2]: 25 ‏Q[3]: 33 37 ‏Q[4]: 48 ‏Q[5]: 57 ]:Q[6 ]:Q[7 ‏Q[8]: 86 ‏Q[9]: 92 25,33,37,48,57,86,92 ,12: : به صورت زیر استRadix sort الگوریتم for (i = 1 ; i<=S ; i++) ددK عKداد ارقامKعKKK=تS KیهKعداد موجود در آراKداد اKعKKK=تN { for (j = ۰ ; j <N ; j++) { ;k=ith digit of x[j] ;place x[j] at rear of q[k] } for (j=0;j<10;j++) place element of q[j] in next sequential ;position of x } پیچیدگی زمانی Radix sort در بدترین حالت که S=Nمی باشد پیچیدگی این الگوریتم ) O(N*Nو در بهترین حالت که S=log Nمیباشد ) O(N log Nاست.