مرتب سازی انتخابی (Selection Sort)

روش انتخابی اولین روشیه که به ذهن می رسه: بزرگترین رکورد بین رکوردهای لیست رو پیدا می کنیم و به انتهای لیست انتقال می دیم. از بقیه رکوردها بزرگترین رو انتخاب می کنیم و انتهای لیست - کنار رکورد قبلی - قرار می دیم. در این روش یک عنصر انتخاب و با تمام  عناصر مقایسه مشود  و ... مثلا :

0:  9 1 6 4 7 3 5

1:  5 1 6 4 7 3 9

2:  5 1 6 4 3 7 9

3:  5 1 3 4 6 7 9

4:  4 1 3 5 6 7 9

5:  3 1 4 5 6 7 9

6:  1 3 4 5 6 7 9

پیاده سازی (مرتب سازی انتخابی) در c++

void selection_sort ( int arr[] , int n )

{

  register int i , j ;

  int max , temp ;

  for ( i = n - 1 ; i > 0 ; i -- )

  {

    max = 0 ;

    for ( j = 1 ; j <= i ; j ++ )

      if ( arr[ max ] < arr[ j ] )

            max = j ;

            temp = arr[ i ] ;

            arr[ i ] = arr[ max ] ;

            arr[ max ] = temp ;

  }

}

پیاده سازی (مرتب سازی انتخابی) در پاسکال

procedure selection_sort ( var arr : array of integer ) ;

var

    i , j , max , temp : integer ;

begin

    for i := High ( arr ) downto Low ( arr ) + 1 do

    begin

        max := 0 ;

        for j := Low ( arr ) + 1 to i do

            if arr[ max ] < arr [ j ] then

                        max := arr[j] ;

                        temp := arr[ i ] ;

                        arr[ i ] := arr[ max ] ;

                        arr[ max ] := temp ;

    end ;

end ;

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

اگر تعداد رکوردها برابر n باشه ، n-1 مرحله لازم است تا تمام داده ها مرتب شوند. مرحله اول n-1 مقایسه ، مرحله دوم n-2 مقایسه ، ... و مرحله آخر 1 مقایسه انجام می گیرد. پس روی هم رفته برای مرتب کردن n رکورد به n(n-1)/2 مقایسه نیاز داریم ، که نشون میده این روش چندان مناسب نیست.

اولین عیب این روش ثابت بودن تعداد مقایسه ها و در نظر گرفتن شیوه چینش رکوردهاست. مثلا حالتی که رکوردها به طور کاملا معکوس باشند (یعنی رکورد اول بزرگترین رکورد و لیست نزولی باشه) با حالتی که لیست کاملا مرتب باشه هیچ تفاوتی نداره ، و همیشه n(n-1)/2 مقایسه باید انجام بگیره!!!

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

در کل روش انتخابی به عنوان یکی از روشهای تعویضی کاربرد چندانی نداره. مخصوصا اگه با رکوردهای زیادی سر و کار داشته باشیم.

دو حلقه تکرار وجود دارد که حلقه خارجی n-1  بار (n  تعداد عناصر لیست است) و حلقه داخلی n/2 بار اجرا می شود

تعداد مقایسه = 1/2(n^2-n)

تعداد تعویض ها در بدترین حالت = n^2 / 4+3(n-1)

تعداد تعویض ها در بهترین حالت = 3(n-1)

در بهترین حالت فقطn-1  عنصر باید تغییر مکان یابد و در هر تغییر مکان نیز سه مقایسه باید انجام گیرد. لذا تعداد تعویضها در بهترین حالت برابر 3(n-1)  است. تعداد تعویضها در حالت متوسط از فرمول پیچیده ای محاسبه می شود که نتیجه آن عبارت زیر است .

 تعداد تعویضها در حالت متوسط = x(log n + y)

که در فرمول فوق y مقدار ثابتی برابر با 0/577216 است گرچه تعداد مقایسه در الگوریتم حبابی و انتخابی باهم برابر است ولی الگوریتم انتخابی روش بهتری است