مرتب سازی انتخابی (selection sort) روش بهبود يافته مرتب سازی حبابی است.

الگوريتم ابتدا کوچکترين عنصر را توسط جستجوی خطی پيدا می کند و آنرا در اولين محل ليست قرار می دهد، سپس دومين عنصر کوچک را پيدا می کند و به همين ترتيب تا آخر.

پیاده سازی

شبه کد الگوریتم مرتب سازی انتخابی به صورت زیر است:

for i:=0 to n-2 do
   min:=i
   for j:=(i + 1) to n-1 do
      if A[j] < A[min] then
         min:= j
      end if
   end for
   swap (A[i] , A[min])
end for

مثال. در زير مراحل مختلف برای مرتب کردن 5 عنصر "64 25 12 22 11" مشاهده می شود.

First Pass
(64 25 12 22 11) ( 11 25 12 22 64)
Second Pass
(11 25 12 22 64) ( 11 12 25 22 64)
Third Pass
(11 12 25 22 64) (11 12 22 25 64)
Forth Pass
(11 12 22 25 64) (11 12 22 25 64)

ارزیابی کارائی

در مقايسه با الگوريتم های ديگر مرتب سازی انتخابی، به دليل سادگی ساختار، صرف نظر از ترتيب داده های ليست هميشه يک زمان اجرا را می دهد. (n-1) جابه جائی در کل مورد نياز است که نسبت به مرتب سازی حبابی کمتر است و اگر تعداد جابه جائی ها مهم باشد مرتب سازی انتخابی روش مناسبی است. تعداد مقايسه ها در کل برابر است با (n-1)+(n-2)+…+1= Θ(n2).

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

مثال.

64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64

یک الگوریتم مرتب سازی الگوریتمی است که عناصر یک لیست را در ترتیب معینی قرار می دهد. کارائی مرتب سازی برای بهینه سازی کاربردهای الگوریتم های دیگر مانند جستجو و ادغام، که به لیست های مرتب نیاز دارند، اهمیت دارد. مرتب سازی برای تهیه خروجی های خوانا برای انسان نیز مفید است.

مرتب سازی حبابی

مرتب سازی انتخابی

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

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

• پیچیدگی زمانی مقایسه عناصر برحسب اندازه لیست (n) . معمولا برای یک الگوریتم مرتب سازی عادی O(n log n) بهترین حالت و O(n²) بدترین حالت است. زمان ایده آل O(n) است.
• پیچیدگی زمانی تعداد جابه جائی ها برای الگوریتم های درجا (in place).
• مصرف حافظه (و استفاده از منابع دیگر سیستم). برخی از الگوریتم های مرتب سازی برون از جا (out place) هستند. که به محل کمکی برای نگهداری داده های موقت علاوه بر داده های در حال مرتب شدن نیاز دارند.
• بعضی از الگوریتم ها بازگشتی یا غیر بازگشتی یا هردو هستند.
• پايداری. الگوریتم های مرتب سازی پايدار ترتیب نسبی رکوردها با کلیدهای مساوی را برقرار می کنند. یعنی اگر دو رکورد R و S با یک کلید وجود داشته باشد و R قبل از S در لیست اصلی آمده باشد، در لیست مرتب شده هم R قبل از S می آید.
• متد کلی. روش مرتب سازی داده ها که می تواند درج،‌ تعویض، انتخاب، ادغام و غیره باشد. برای مثال مرتب سازی حبابی و سریع مرتب سازی تعویضی هستند.