مرتبسازیهای خطی
در شرایطی که عناصری که قرار است مرتب شوند دارای یک سری محدودیتهای خاص یا شرایط خاص میباشند، میتوان برای مرتب کردن آنها از روشهایی به غیر از روشها یا الگوریتمهای مرتبسازی مقایسهای مانند :مرتبسازی ادغامی استفاده کرد و به الگوریتمهای سریعتری از (O(n log n دست یافت. به دسته ای از این گونه مرتبسازیها که بر پایهٔ یک سری شرایط خاص عناصر هستند و دارای پیچیدگی خطی هستند مرتبسازی خطی میگوییم. مرتبسازیهای مقایسهای الگوریتمی سریع تر از(O(n log n ندارند که این موضوع با کمک درخت تصمیم اثبات میشود.
انواع مرتبسازیها خطی
انواع مرتبسازیهای خطی عبارتند از مرتبسازی شمارشی، مرتبسازی سطلی، مرتبسازی مبنایی و BeadSort و BrustSort و PigeonholeSort و…
در این الگوریتم محدودیت اعمال شده روی داده این است که کلید تمامی عناصر باید اعداد صحیح بوده و بین ۱ تا m قرار بگیرند که m یک عدد ثابت است و این الگوریتم با استفاده از آرایهای از اعداده صحیح به طول m عناصر مورد نظر را مرتب میکند. بهطور خلاصه الگوریتم به این صورت عمل میکند که تعداد دفعات ظاهر شدن هر عنصر در ورودی را با کمک آرایه گرفته شده حساب میکند و سپس با این اطلاعات از ابتدا شروع کرده و هر عنصر را به تعداد دفعات ظهورش در ورودی در خروجی قرار میدهد، و با توجه به اینکه این عمل را از ۱ تا m انجام میدهد خروجی مرتب شده است. برای تشریح کامل الگوریتم به صفحه مرتبسازی شمارشی مراجعه کنید.
این الگوریتم مرتبسازی برای مرتب کردن اعدادی با طول ثابت به اندازهٔ k مورد استفاده قرار میگیرد و کاربرد دارد. البته بهتر است دقت شود اعداد با طول کمتر از k را میتوان با قرار دادن صفر در سمت راست آنها به اعداد ی به طول k تبدیل شوند. بهطور خلاصه روش کار این الگوریتم به این صورت است که عناصر را در k مرحله با استفاده از مرتبسازی شمارشی مرتب میکند. به این صورت که ابتدا عناصر را بر حسب کم ارزشترین رقم آنها مرتب میکند و سپس بر حسب رقم بعدی کم ارزش آنها و این کار را تا رقم k ادامه داده و در انتها عناصر مرتب شده هستند. ذکر این نکته ضروریست که الگوریتم شمارشی که برای این الگوریتم استفاده میشود حتماً باید پایدار باشد. این الگوریتم به سال ۱۸۸۷ بر میگردد. در ان دوران از این الگوریتم در ماشینهای Tabulating و همچنین ماشینهای مکانیکی استفاده میشده. برای تشریح کامل این الگوریتم به صفحهٔ مرتبسازی پایهای مراجعه کنید.
این الگوریتم به نوعی میتوان گفت حالت کلی الگوریتم مرتبسازی مبنایی است، در مرتبسازی سطلی عناصری که میخواهیم مرتب کنیم، دارای k مؤلفهٔ a1 تا ak هستند و که مؤلفهٔ ai بر مؤلفهٔ ai-1 در اولویت دارد. در مرتبسازی مبنایی این k مؤلفه ارقام یک عدد بودند ولی در مرتبسازی سطلی این مؤلفهها صرفاً ارقام نیستند. روش کار این الگوریتم هم تقریباً همانند مرتبسازی مبنایی است. به این صورت که ابتدا عناصر را بر حسب مؤلفهٔ اول آنها مرتب میکند و همین گونه تا مؤلفهٔ k ادامه میدهد و در انتها عناصر مرتب شده هستند. برای اطلاعات کامل تر در رابطه با این الگوریت به صفحهٔ مرتبسازی سطلی مراجعه کنید.
منابع
منابع فارسی
"داده ساختارها و طراحی الگوریتم هاً تألیف دکتر محمد قدسی
منابع دیگر
- NIST's Dictionary of Algorithms and Data Structures
- «Corwin, E. and Logar, A.»Sorting in linear time