مرتب سازی رادیکس (Radix Sort)
در «مرتب سازی رادیکس (Radix Sort)» اعداد را رقم به رقم مرتب می کنیم. از کم ارزش ترین رقم شروع می کنیم. سپس به رقم بعدی می رویم. این روش مقایسه نمی کند و فقط با اعداد صحیحِ نامنفی کار می کند.
ایده اصلی در یک نگاه
رادیکـس یعنی «پایه عددی». در ده دهی، ده رقم داریم. در هر مرحله، بر اساس رقمِ فوکوس، اعداد را در 10 سطل می ریزیم. سپس دوباره پشت سرهم به آرایه برمی گردانیم و به رقم بعدی می رویم.
- از رقم کم ارزش شروع کن.
- در سطل مناسب بریز و برگردان.
- به رقم بعدی برو تا تمام شود.
مرتب سازی پایدار (Stable)
مرتب سازی «پایدار» ترتیب عناصرِ هم ارزش را حفظ می کند. در رادیکس این مهم است. چون هر بار فقط یک رقم مرتب می شود. اگر پایدار نباشد، زحمت مرحله قبل خراب می شود.
پیاده سازی Radix Sort در پایتون
در این نسخه، هر دور یک رقم را پردازش می کنیم و با سطل ها آرایه را می سازیم.
mylist = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", mylist)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(mylist)
exp = 1
while maxVal // exp > 0:
while len(mylist) > 0:
val = mylist.pop()
radixIndex = (val // exp) % 10
radixArray[radixIndex].append(val)
for bucket in radixArray:
while len(bucket) > 0:
val = bucket.pop()
mylist.append(val)
exp *= 10
print(mylist)
Radix با الگوریتم های دیگر
رادیکس می تواند از هر الگوریتم «پایدار» درونِ سطل ها استفاده کند. اینجا از «مرتب سازی حبابی (Bubble Sort)» برای هر سطل استفاده شده است.
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
def radixSortWithBubbleSort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
radixList = [[], [], [], [], [], [], [], [], [], []]
for num in arr:
radixIndex = (num // exp) % 10
radixList[radixIndex].append(num)
for bucket in radixList:
bubbleSort(bucket)
i = 0
for bucket in radixList:
for num in bucket:
arr[i] = num
i += 1
exp *= 10
mylist = [170, 45, 75, 90, 802, 24, 2, 66]
radixSortWithBubbleSort(mylist)
print(mylist)
گام های عملی
- بیشینه را پیدا کن و exp را 1 بگذار.
- تا وقتی max // exp > 0، ادامه بده.
- اعداد را طبق رقمِ exp در سطل ها بریز.
- از سطل ها به آرایه برگردان.
- exp را در 10 ضرب کن و تکرار کن.
پیچیدگی زمانی
پیچیدگی برابر O(n \cdot k) است. n تعداد اعداد است. k تعداد رقمِ بیشینه است. اگر رقم ها کم باشند، کار بسیار سریع می شود. اما رقم های زیاد، زمان را افزایش می دهد.
جمع بندی سریع
- مرتب سازی رادیکس مقایسه ای نیست.
- پایداری برای رادیکس ضروری است.
- برای اعداد نامنفی مناسب است.
- دامنه رقم ها اگر کم باشد، عالی است.
- برای مقایسه ببین: مرتب سازی شمارشی و مرتب سازی سریع.