راهنمای مبتدیان برای مرتب سازی رادیکس: راهنمای گام به گام و کد پایتون

مرتب سازی یک کار ضروری در علوم کامپیوتر است و الگوریتم های مرتب سازی زیادی وجود دارد که هر کدام مزایا و معایب خود را دارند. یکی از کارآمدترین و ساده ترین الگوریتم های مرتب سازی Radix Sort است. در این مقاله نحوه کار Radix Sort را به صورت گام به گام بررسی می کنیم و نمونه کدهای پایتون را برای پیاده سازی آن ارائه می دهیم.
مرتب سازی رادیکس چگونه کار می کند
Radix Sort یک الگوریتم مرتبسازی غیرمقایسه، پایدار و خطی است که دادهها را با گروهبندی عناصر بر اساس ارقام یا کاراکترهای مهم آنها مرتب میکند. دادهها را با مرتبسازی هر رقم یا کاراکتر عنصر به صورت جداگانه، از کمترین رقم به مهمترین رقم، مرتب میکند.
بیایید نمونه ای از مرتب سازی لیست اعداد صحیح زیر را با استفاده از مرتب سازی Radix مثال بزنیم:
[170, 45, 75, 90, 802, 24, 2, 66]
حداکثر تعداد ارقام را در لیست تعیین کنید و در صورت لزوم عناصر را با صفر بپوشانید. در مثال ما، حداکثر تعداد ارقام سه رقم است، بنابراین عناصر را با صفر اضافه می کنیم تا هر سه رقم طولانی شوند:[170, 045, 075, 090, 802, 024, 002, 066]
فهرست را بر اساس کمترین رقم (یعنی سمت راست ترین رقم) مرتب کنید. ده سطل (0-9) ایجاد کنید و هر عنصر را در سطل مربوط به رقم خود قرار دهید. به عنوان مثال، 170، 090، و 802 دارای 0 در سمت راست ترین رقم هستند، بنابراین آنها در سطل 0 قرار می گیرند. لیست بعد از این مرحله به این صورت خواهد بود:[802, 002, 024, 045, 075, 066, 170, 090]
سطل ها را به ترتیب به هم بپیوندید، از سطل 0 شروع کنید و با سطل 9 پایان دهید. لیست بعد از این مرحله به شکل زیر خواهد بود:[802, 002, 024, 045, 075, 066, 170, 090]
مراحل 2 و 3 را برای رقم مهم بعدی (یعنی رقم دوم از سمت راست) تکرار کنید و تا مرتب شدن همه ارقام ادامه دهید. لیست مرتب شده نهایی به صورت زیر خواهد بود:[002, 024, 045, 066, 075, 090, 170, 802]
کد پایتون برای مرتب سازی Radix
اکنون که متوجه شدیم مرتب سازی Radix چگونه کار می کند، اجازه دهید آن را در پایتون پیاده سازی کنیم. کد پایتون برای مرتب سازی Radix در اینجا آمده است:
def radix_sort(nums):
# Determine the maximum number of digits
max_digit = len(str(max(nums)))
# Pad the elements with zeroes if necessary
nums = [str(num).zfill(max_digit) for num in nums]
# Sort the list by each digit
for i in range(max_digit - 1, -1, -1):
buckets = [[] for _ in range(10)]
for num in nums:
buckets[int(num[i])].append(num)
nums = [num for bucket in buckets for num in bucket]
# Convert the elements back to integers
nums = [int(num) for num in nums]
return nums
کد فهرستی از اعداد صحیح را به عنوان ورودی می گیرد و فهرست مرتب شده را با استفاده از مرتب سازی Radix برمی گرداند. با تعیین حداکثر تعداد ارقام در لیست شروع می شود و در صورت لزوم، عناصر را با صفر اضافه می کند. سپس فهرست را بر اساس هر رقم مرتب میکند و با مهمترین رقم شروع میکند و با استفاده از همان مراحلی که قبلاً در مورد آن صحبت کردیم.
یکی از مزایای قابل توجه Radix Sort علاوه بر سادگی و کارایی، پیچیدگی زمانی آن است. پیچیدگی زمانی Radix Sort O(nk) است، که در آن n تعداد عناصری است که باید مرتب شوند و k حداکثر تعداد ارقام یا کاراکترهای یک عنصر است. این باعث می شود Radix Sort یک الگوریتم مرتب سازی کارآمد برای مجموعه داده های بزرگ باشد.
برای اینکه بفهمیم چرا پیچیدگی زمانی Radix Sort O(nk) است، اجازه دهید موارد زیر را در نظر بگیریم:
در مرحله 1، ما باید حداکثر تعداد ارقام یا کاراکترها را در عناصر تعیین کنیم که زمان O(n) را می طلبد.
در مرحله 2، باید هر رقم یا کاراکتر در هر عنصر را تکرار کنیم، که زمان O(kn) را می گیرد.
در مرحله 3، باید سطل ها را به هم متصل کنیم، که زمان O(n) را می طلبد.
مراحل 2 و 3 را برای هر رقم یا کاراکتر در عناصر تکرار می کنیم که زمان O(kn) را می گیرد.
بنابراین، کل پیچیدگی زمانی Radix Sort O(nk) است.
در نتیجه، Radix Sort یک الگوریتم مرتبسازی ساده، کارآمد و پایدار است که دادهها را با گروهبندی عناصر بر اساس ارقام یا کاراکترهای مهم آنها مرتب میکند. با پیچیدگی زمانی O(nk)، یک انتخاب عالی برای مرتب سازی مجموعه داده های بزرگ است. کد پایتونی که در این مقاله ارائه کردیم را می توان به راحتی برای مرتب کردن انواع مختلف داده ها، از جمله رشته ها و تاپل ها، تطبیق داد. با درک نحوه عملکرد Radix Sort و پیچیدگی زمانی آن، می توانید آن را در سناریوهای دنیای واقعی اعمال کنید و عملکرد برنامه های خود را بهبود بخشید.