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

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

اسلاید 1: مرتب سازی مبنا (Radix sort) مرتب سازی Radix روشی است که اغلب در کارهای روزمره از آن استفاده می کنیم.مثلا هنگامی که می خواهیم اسامی دانشجویان یک کلاس را به ترتیب حروف الفبا مرتب کنیم ابتدا به حروف اول فامیلی آنها توجه کرده و بر این اساس آنها را مرتب می کنیم.به عبارتی دیگر اسامی به 32 دسته مرتب میشوند.دسته اول با حرف ”آ“ دسته دوم با حرف ”ب“ والی آخر آغاز میشوند.در مرحله دوم هر دسته بر اساس حرف دوم فامیلی ها مرتب می شوند و الی آخر.بدیهی است که اگر هیچ نامی بیشتر از 12 حرف نداشته باشد اسامی را میتوان حداکثر در 12 مرحه مرتب کرد.حال این روش را برای مرتب سازی تعدادی عدد شرح می دهیم.برای هر رقم با شروع از کم ارزش ترین به با ارزش ترین رقم این اعمال را انجام میدهیمهر عدد را به ترتیبی که در آرایه قرار دارد خوانده و بر اساس ارزش رقمی که در حال پردازش است آن را در یکی از 10 صف قرار میدهیم.سپس هر صف را با شروع از صفی که با رقم صفر شماره گذاری شده تا صفی که با رقم 9 شماره گذاری شده است در بردار اولیه می نویسیم.وقتی این عمل برای هر رقم انجام گرفت(با شروع از رقم سمت راست به سمت رقم سمت چپ) آرایه مرتب خواهد شد.

اسلاید 2: شکل زیر مراحل مرتب سازی آرایه زیر را با روش Radix نشان می دهد. 25,57,48,37,12,92,86,33 گذر اول:فقط رقم یکان اعداد را نگاه کرده و هر یک را در صف مربوطه می نویسیم.Q[0]:Q[1]:Q[2]: 12 92Q[3]: 33Q[4]: Q[5]: 25Q[6]: 86Q[7]: 57 37Q[8]: 48Q[9]: آرایه بعد از گذر اول :12,92,33,25,86,57,37,48

اسلاید 3: گذر دوم: اعداد را بر اساس رقم دوم در یکی از صفها قرار می دهیم.Q[0]:Q[1]: 12 Q[2]: 25Q[3]: 33 37Q[4]: 48Q[5]: 57 Q[6]:Q[7]:Q[8]: 86Q[9]: 92 آرایه بعد از گذر دوم که مرتب شده است :12, 25,33,37,48,57,86,92

اسلاید 4: الگوریتم Radix sort به صورت زیر است: for (i = 1 ; i<=S ; i++) { 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;}S=تعداد ارقام عددN=تعداد اعداد موجود در آرایه

اسلاید 5: پیچیدگی زمانی Radix sort در بدترین حالت که S=N می باشد پیچیدگی این الگوریتم O(N*N) و در بهترین حالت که S=log N میباشد O(N log N) است.