جدول زیر بعضی از الگوریتم های مرتب سازی را معرفی می کند که در کاربردهای واقعی استفاده نمی شوند زیرا به شدت از کارایی پایینی برخوردار بوده و یا احتیاج به یک سخت افزار خاص دارند.

                                                             جدول ۳

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

    مقایسه ای

  پایدار

1.  الگوریتم های مقایسه ای ( Comparison Sorting Algorithms ) :

مرتب سازی مقایسه ای نوع خاصی از الگوریتم های مرتب سازی است که تنها می تواند عناصر آرایه را از طریق یک عملگر مقایسه ای منفرد         ( اغلب عملگر ” کوچکتر از “ ) بخواند که مشخص می کند کدامیک از دو عنصر باید در آرایه نهایی در ابتدا قرار بگیرند.

2.  الگوریتم های پایدار ( Stable Sorting Algorithms ) :

الگوریتم های مرتب سازی پایدار ، ارتباط نسبی رکوردهای با مقادیر مساوی را نگه می دارد. به عنوان مثال فرض کنید در یک آرایه رکورد R قبل از رکورد S ظاهر شده است. حال به الگوریتمی پایدار گفته می شود که این ترتیب را نگه دارد ، یعنی در آرایه مرتب شده ، R قبل از S ظاهر شود.

الگوهای استفاده از حافظه و مرتب سازی اندیسی :

هنگامیکه اندازه آرایه ای که در حال مرتب شدن است ار میزان حافظه اختصاص داده شده به آن فراتر می رود ، باید عمل swapping یا مبادله روی دیسک ( البته با سرعت بسیار کمتر ) انجام شود . در اینجاست که الگوهای استفاده از حافظه از اهمیت فراوانی برخوردار می شوند. یک الگوریتم هنگامی می تواند کارامد باشد که آرایه آن به راحتی در حافظه اصلی قرار بگیرد. در این سناریو تعداد مقایسه ها از اهمیت کمتری برخوردار خواهند شد و در عوض تعداد قطعاتی از حافظه که باید به دیسک کپی شوند و از دیسک مبادله شوند ، تبدیل به شاخص عمده ای در کارایی الگوریتم خواهند شد. بنابراین ، تعداد گذرها و محلی کردن ( localization ) مقایسه ها می توانند مهمتر از تعداد سطرهای مقایسه شوند ، و تا هنگامیکه مقایسه عناصر مجاور با یکدیگر در حد سرعت باس سیستم ( و یا با بکارگیری تکنیک caching ، حتی در حد سرعت CPU ) باشد ، این سرعت در مقایسه با سرعت دیسک می تواند بسیار سریع باشد.

برای مثال ، الگوریتم بازگشتی QuickSort ، می تواند کارایی قابل قبولی را با RAM کافی ارائه دهد ، اما اگر آرابه در RAM جا نشود ، به دلیل روش بازگشتی که قسمت های آرایه را کپی می کند و باعث می شود که عملیات کپی و جابجایی متعددی بر روی دیسک انجام شود ، سرعت این الگوریتم به شدت کاهش پیدا می کند.

روش دیگری که می توان در مورد این مسئله روی آن کار کرد ، هنگامی است که قصد مرتب سازی رکوردهای متعدد همراه با کلید های نسبی کوچک را داشته باشیم ( به عنوان مثال در پایگاه داده های رابطه ای ). در این مورد ما می توانیم اندیسی را روی آرایه ایجاد کنیم و به جای اینکه کل آرایه را مرتب کنیم ، اندیس آنرا مرتب کنیم. ( بعد از آن می توانیم کل آرایه را با خواندن اندیس ها ، در یک گذر مرتب کنیم ) . به این دلیل که اندیس ها به مراتب کوچکتر از کل آرایه هستند به راحتی می توانند در RAM جای بگیرند ، و بدینوسیله می توانیم مشکل swapping روی دیسک را حل کنیم. این روش را " tag sort " نیز می نامند.

تکنیک دیگری که برای غلبه بر مشکل اندازه حافظه می توان بکار برد ، این است که دو الگوریتم را بگونه ای با هم ترکیب کنیم که مزایای قدرت هر کدام ، کارایی کلی را بهبود ببخشند. برای مثال ، آرایه می تواند به تکه های کوچکی تقسیم شود که آن تکه ها به راحتی در RAM قرار بگیرند. این تکه ها می توانند با الگوریتم های کارامدی چون Quick sort یا Heap sort مرتب شوند و درنتیجه هر قسمت با استفاده از الگوریتم Merge sort ادغام شوند. این روش بهتر از آنست که الگوریتم Merge Sort را در همان ابتدا روی کل آرایه اعمال کنیم ، اما این روش نیز احتیاج به RAM کمتری نسبت به الگوریتم Quick Sort که روی کل آرایه اعمال می شود ، دارد .

پشتیبانی زبانها :

اکثر زبانها از مرتب سازیها پشتیبانی می کنند. این پیاده سازیها معمولاً از یک الگوریتم مشخص که کارایی بالایی دارد برای مرتب سازی حافظه استفاده می کنند ، و برنامه های کاربردی معمولا ترجیح می دهند که یک الگوریتم مرتب سازی شخصی بنویسند. Quick Sort انتخاب اول است ، ولی Heap Sort و Merge Sort نیز پرطرفدار هستند. در اینجا معروفترین زبانها را معرفی کرده ایم :

·        زبان   C دارای یک کتابخانه تابع استاندارد به نام qsort() است که می تواند یک مرتب سازی مقایسه ای اختیاری روی آرایه ای از اشیاء که از یک عملگر مقایسه ای که به عنوان یک اشاره گر به تابع ارسال می شود ، انجام دهد. پیاده سازی آن معمولا لازم نیست که مبتنی بر Quick Sort باشد.

·          زبان ++C نیز از qsort() استفاده می کند منتها از یک تابع STL (کتابخانه استاندارد قالب )  با نام std :: sort که آرایه را در بازه ای تصادفی مرتب می کند ، استفاده می کند. علاوه بر آن کلاس std :: list ( لیست پیوندی ) که احتیاج به دستیابی تصادفی ندارد ، به عنوان متد sort استفاده می شود. نوع عناصری که مرتب می شوند باید عملگر < را پشتیبانی کنند. همچنین C++ دو تابع  stable_sort  و partial_sort را ارائه داده است.

·         زبان  Java از کلاسهای Arrays و Collections که شامل متدهای استاتیک sort() هستند و بترتیب روی آرایه ها و لیست ها عمل می کنند، استفاده می کند.

·          .NET Framework از یک متد استاتیک که Array.Sort()  نام دارد استفاده می کند که می تواند یک آرایه از اشیاء که از مقایسه کننده های اختیاری استفاده می کنند ، را مرتب کند. اگرچه الگوریتم موردنظر مستند نشده است ولی با استفاده از مهندسی معکوس مشخص شده است که مایکروسافت از الگوریتم Quick Sort استفاده می کند. علاوه بر آن .NET از یک متد به نام Sort()  بر روی کلاس ArrayList استفاده می کند که آن نیز از quicksort استفاده می کند. یک نوع جدید به نام List نیز امکانات مرتب سازی را مهیا کرده است.

·         زبان    Perl دارای یک تابع درونی ( built-in ) به نام sort است که از یک تابع مقایسه کننده که مقادیر صحیح منفی ، صفر یا مثبت را بترتیب برای نشان دادن عبارات کوچکتر ، مساوی یا بزرگتر بکار می برد ، استفاده می کند. این زبان در ورژن 5.6 و قبل از آن از الگوریتم quicksort استفاده می کرد و بعد از آن از الگوریتم کندتر و پایدارتر Merge Sort  را بکار برد. انگیزه اصلی برای انتخاب Merge Sort ، امنیت آن بود. Perl یک زبان بسیار محبوب برای نوشتن برنامه های تحت وب است ، بنابراین اگر الگوریتم مرتب سازی آن دارای پیچیدگی زمانی ضعیف و بد باشد ، مهاجمان می توانند ورودی هایی را تولید کنند که عمداً باعث ایجاد رفتارهایی به مانند حمله های DOS شود. Merge Sort از جهاتی از Quick Sort ناکارآمدتر است ولی بر خلاف Quick Sort فاقد جنبه های آسیب پذیری است.

·        زبان   Python از دو تابع درونی به نام های sorted برای مرتب کردن حلقه های تکرار اختیاری و متد sort برای مرتب سازی درجای لیستها استفاده می کند.

                                                             ادامه دارد