مرتب‌سازی‌های خطی
در شرایطی که عناصری که قرار است مرتب شوند دارای یک سری محدودیت‌های خاص یا شرایط خاص می‌باشند، می‌توان برای مرتب کردن آنها از روش‌هایی به غیر از روش‌ها یا الگوریتم‌های مرتب سازی مقایسه‌ای مانند :مرتب‌سازی ادغامی استفاده کرد و به الگوریتم‌های سریعتری از (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