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

در علوم کامپیوتر الگوریتم هایی که بیشترین توجه را به خود اختصاص می دهند، الگوریتم های مرتب سازی ( sorting algorithms ) هستند. این الگوریتم ها زمانی به کمک ما می آیند که یک لیست از مقادیر داشته باشیم و بخواهیم آنها را در یک لیست مرتب شده( ordered list ) قرار دهیم. مسئله ی مرتب سازی بخش بزرگی از کارهای برنامه نویسی در دنیای کامپیوتر و نرم افزار است. به سناریوهای زیر توجه کنید:

1- یک دیتابیس از افراد و شماره تماس آنها وجود دارد که میخواهید آن ها به ترتیب الفبایی مرتب شوند(مانند دفترچه تلفن های همراه)

2- نمره های دانش آموزان یک کلاس در اختیار شماست و میخواهید به 5 نفری که بیشترین نمره را کسب کردند جایزه بدهید.

3- یک لیست خدمات بیمه ای در اختیار شماست و میخواهید بدانید کدام خدمت شما کمترین میزان سود را برای شرکت بیمه ی شما به همراه داشته است.

مسائل بالا همه مسائل مرتب سازی هستند. برای اینکه یک مسئله، مسئله ی مرتب سازی( sorting ) به حساب بیاید باید اطلاعات اولیه(ورودی ها) به صورت نامرتب در اختیار مسئله قرار بگیرند و خروجی مورد نظر ما 2 شرط زیر را داشته باشند:

1- ترتیب المان های خروجی باید افزایشی باشد به این معنی که هر المان باید از المان قبل از خود بزرگتر و یا با آن برابر باشد.

2- المان های ورودی باید در خروجی وجود داشته باشند و هیچ المانی حذف نشود، تغییر نکند و المان جدیدی نیز به لیست ورودی افزوده نشود.

برای درک بهتر کارکرد این مسئله لیست ورودی زیر و خروجی آن را در نظر بگیرید:

بیایید یکی از الگوریتم های مشهور مرتب سازی به نام مرتب سازی حبابی( bubble sort ) را باهم بررسی کنیم و ببینیم که مسئله ی بالا چگونه حل می شود:

1- از ابتدای لیست شروع می کنیم و 2 المان اول را باهم مقایسه میکنیم و اگر المان اول بیشتر از المان دوم بود جای آنها را عوض می کنیم و در غیر این صورت به مرحله ی بعد می رویم:

از آنجایی که 5 < 8 است کاری نمیکنیم و به مرحله ی بعد می رویم.

2- 2 المان بعدی ( 8 و 1) را مقایسه میکنیم و از آنجایی که 8 < 1 نیست جای 8 و 1 را عوض می کنیم:

3- حالا 8 المان سوم است و باید آنرا با 3 مقایسه کنیم. نتیجه به صورت زیر می شود:

4- به انتهای لیست رسیدیم و خروجی مرحله ی آخر از حلقه ی اول به شکل زیر است:

5- حالا به ابتدای لیست برمیگردیم و مراحل قبل را مجددا انجام میدهیم

6- تکرار حلقه تا زمانی ادامه پیدا می کند که در تکرار آخر اثری از جابجایی المان های موجود در لیست نبینیم.

در مثال بعد این الگوریتم را پیاده سازی کرده ایم.