close
دانلود فیلم
مرتب سازی انتخابی

 

مرتب سازی انتخابی (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

لینک کوتاه پست
مطالب مرتبط با پست جاری
  • نکات مهم
    1- لطفا نظر خود را با زبان فارسی بیان کنید
    2- رایتم نظرات اسپم و تبلیغی شما را تایید نمی کند
    3- لطفا نظرات شما بدون ابهام و واضح باشد
  • نام
    ایمیل (منتشر نمی‌شود) (لازم)
    وبسایت
    :):(;):D;)):X:?:P:*=((:O@};-:B/:):S
    نظر خصوصی
    مشخصات شما ذخیره شود ؟[حذف مشخصات] [شکلک ها]
    کد امنیتی
به کانال تلگرام سایت ما بپیوندید