مرتبسازیهای خطی
در شرایطی که عناصری که قرار است مرتب شوند دارای یک سری محدودیتهای خاص یا شرایط خاص می باشند، میتوان برای مرتب کردن آنها از روشهایی به غیر از روشها یا الگوریتمهای مرتب سازی مقایسهای مانند :مرتبسازی_ادغامی استفاده کرد و به الگوریتمهای سریعتری از (O(n log n دست یافت. به دسته ای از این گونه مرتب سازیها که بر پایهٔ یک سری شرایط خاص عناصر هستند و دارای پیچیدگی خطی هستند مرتب سازی خطی میگوییم. مرتب سازیهای مقایسهای الگوریتمی سریع تر از(O(n log n ندارند که این موضوع با کمک درخت تصمیم اثبات میشود.
محتویات |
انواع مرتب سازیها خطی [ویرایش]
انواع مرتب سازیهای خطی عبارتند از مرتب سازی شمارشی، مرتب سازی سطلی، مرتب سازی مبنایی و BeadSort و BrustSort و PigeonholeSort و...
مرتبسازی_شمارشی [ویرایش]
در این الگوریتم محدودیت اعمال شده روی داده این است که کلید تمامی عناصر باید اعداد صحیح بوده و بین 1 تا m قرار بگیرند که m یک عدد ثابت است و این الگوریتم با استفاده از آرایهای از اعداده صحیح به طول m عناصر مورد نظر را مرتب میکند. به طور خلاصه الگوریتم به این صورت عمل میکند که تعداد دفعات ظاهر شدن هر عنصر در ورودی را با کمک آرایه گرفته شده حساب میکند و سپس با این اطلاعات از ابتدا شروع کرده و هر عنصر را به تعداد دفعات ظهورش در ورودی در خروجی قرار میدهد، و با توجه به اینکه این عمل را از 1 تا m انجام میدهد خروجی مرتب شدهاست. برای تشریح کامل الگوریتم به صفحه مرتبسازی_شمارشی مراجعه کنید.
مرتبسازی پایهای [ویرایش]
این الگوریتم مرتب سازی برای مرتب کردن اعدادی با طول ثابت به اندازهٔ k مورد استفاده قرار میگیرد و کاربرد دارد.البته بهتر است دقت شود اعداد با طول کمتر از k را میتوان با قرار دادن صفر در سمت راست انها به اعداد ی به طول k تبدیل شوند. به طور خلاصه روش کار این الگوریتم به این صورت است که عناصر را در k مرحله با استفاده از مرتب سازی شمارشی مرتب میکند. به این صورت که ابتدا عناصر را بر حسب کم ارزشترین رقم انها مرتب میکند و سپس بر حسب رقم بعدی کم ارزش آنها و این کار را تا رقم k ادامه داده و در انتها عناصر مرتب شده هستند. ذکر این نکته ضروریست که الگوریتم شمارشی که برای این الگوریتم استفاده میشود حتماً باید پایدار باشد. این الگوریتم به سال 1887 بر میگردد. در ان دوران از این الگوریتم در ماشینهای 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
