مرتب سازی انتخابی یکی از انواع الگوریتم مرتب سازی می باشد که جزو دستهٔ الگوریتم های مرتب سازی مبتنی بر مقایسه است. این الگوریتم دارای پیچیدگی زمانی از درجهٔ O ( n2 ) است که به همین دلیل اعمال آن روی مجموعهٔ بزرگی از اعداد کارا به نظر نمی رسدو به طور عمومی ضعیفتر از نوع مشابهش که مرتب ساز درجی است عمل می کند. این مرتب سازی به دلیل سادگی اش قابل توجه است. کارایی آن برحسب تعداد ورودی ها در نمودار زیر نشان داده شده است.
این الگوریتم این گونه عمل می کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می کنیم و این روند را برای n - 1 عدد اول تکرار می کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می کنیم. زیرلیست اول که قبلاً مرتب کرده ایم و سایر اعضای لیست که هنوز مرتب نشده است. در جدول زیر مثالی از پیاده سازی این روال بر روی ۶ عدد آمده است.
ورودی: ۳۴ ۱۵ ۴ ۱۲ ۵۵ ۲۴ ۱ ) ۴ ۱۵ ۳۴ ۱۲ ۵۵ ۲۴ ۲ ) ۴ ۱۲ ۳۴ ۱۵ ۵۵ ۲۴ ۳ ) ۴ ۱۲ ۱۵ ۳۴ ۵۵ ۲۴ ۴ ) ۴ ۱۲ ۱۵ ۲۴ ۵۵ ۳۴ ۵ ) ۴ ۱۲ ۱۵ ۲۴ ۳۴ ۵۵ پیاده سازی الگوریتم در زبان های برنامه نویسی الگوریتم در پایتون A = for i in range ( len ( A ) ) : min_idx = i for j in range ( i+1, len ( A ) ) : if A > A: min_idx = j A, A = A, A print ( " Sorted array" ) for i in range ( len ( A ) ) : print ( " %d" % A, end=" \t" ) الگوریتم در جاوا /** * @param arr a to a is the array to sort */ private static void selectionSort ( double arr ) { for ( int i= 0; i < arr. length - 1; i++ ) // ( could i < arr. length - 1 because single element is also min element ) for ( int j= i + 1; j < arr. length; j++ ) if ( arr > arr ) { double temp= arr; arr= arr; arr= temp; } } الگوریتم درC++ # include < iostream. h> void selectionSort ( int *array, int length ) //selection sort function { int i, j, min, minat; for ( i=0; i< ( length - 1 ) ; i++ ) { minat=i; min=array; for ( j=i+1; j< ( length ) ; j++ ) //select the min of the rest of array { if ( min> array ) //ascending order for descending reverse { minat=j; //the position of the min element min=array; } } int temp=array ; array=array; //swap array=temp; } } void printElements ( int *array, int length ) //print array elements { int i=0; for ( i=0; i< 10; i++ ) cout< < array< < endl; } void main ( ) { int a={9, 6, 5, 23, 2, 6, 2, 7, 1, 8}; // array to sort selectionSort ( a, 10 ) ; //call to selection sort printElements ( a, 10 ) ; // print elements } تحلیل مرتبه الگوریتم تحلیل الگوریتم مرتب سازی انتخابی برخلاف بسیاری از مرتب سازی های دیگر بسیار ساده است. زیرا که هیچ کدام از حلقه های آن به اعداد موجود در لیست ورودی بستگی ندارد. در مرحلهٔ اول به دست آوردن کمینه در لیست n عنصری نیاز به پیمودن کل n عدد و n – 1 مقایسه دارد و سپس باید کمینهٔ به دست آمده با اولین عدد جابجا شود. در مرحلهٔ بعدی به دست آوردن دومین کمینه در لیست 1 - n عنصری نیاز به پیمودن کل 1 - n عدد و 2 - n مقایسه دارد و کمینهٔ به دست آمده بادومین عدد جابجا شودو این روند ادامه پیدا می کند. پس کلاً تعداد مقایسه ها عبارتست از:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین الگوریتم این گونه عمل می کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می کنیم و این روند را برای n - 1 عدد اول تکرار می کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می کنیم. زیرلیست اول که قبلاً مرتب کرده ایم و سایر اعضای لیست که هنوز مرتب نشده است. در جدول زیر مثالی از پیاده سازی این روال بر روی ۶ عدد آمده است.
ورودی: ۳۴ ۱۵ ۴ ۱۲ ۵۵ ۲۴ ۱ ) ۴ ۱۵ ۳۴ ۱۲ ۵۵ ۲۴ ۲ ) ۴ ۱۲ ۳۴ ۱۵ ۵۵ ۲۴ ۳ ) ۴ ۱۲ ۱۵ ۳۴ ۵۵ ۲۴ ۴ ) ۴ ۱۲ ۱۵ ۲۴ ۵۵ ۳۴ ۵ ) ۴ ۱۲ ۱۵ ۲۴ ۳۴ ۵۵ پیاده سازی الگوریتم در زبان های برنامه نویسی الگوریتم در پایتون A = for i in range ( len ( A ) ) : min_idx = i for j in range ( i+1, len ( A ) ) : if A > A: min_idx = j A, A = A, A print ( " Sorted array" ) for i in range ( len ( A ) ) : print ( " %d" % A, end=" \t" ) الگوریتم در جاوا /** * @param arr a to a is the array to sort */ private static void selectionSort ( double arr ) { for ( int i= 0; i < arr. length - 1; i++ ) // ( could i < arr. length - 1 because single element is also min element ) for ( int j= i + 1; j < arr. length; j++ ) if ( arr > arr ) { double temp= arr; arr= arr; arr= temp; } } الگوریتم درC++ # include < iostream. h> void selectionSort ( int *array, int length ) //selection sort function { int i, j, min, minat; for ( i=0; i< ( length - 1 ) ; i++ ) { minat=i; min=array; for ( j=i+1; j< ( length ) ; j++ ) //select the min of the rest of array { if ( min> array ) //ascending order for descending reverse { minat=j; //the position of the min element min=array; } } int temp=array ; array=array; //swap array=temp; } } void printElements ( int *array, int length ) //print array elements { int i=0; for ( i=0; i< 10; i++ ) cout< < array< < endl; } void main ( ) { int a={9, 6, 5, 23, 2, 6, 2, 7, 1, 8}; // array to sort selectionSort ( a, 10 ) ; //call to selection sort printElements ( a, 10 ) ; // print elements } تحلیل مرتبه الگوریتم تحلیل الگوریتم مرتب سازی انتخابی برخلاف بسیاری از مرتب سازی های دیگر بسیار ساده است. زیرا که هیچ کدام از حلقه های آن به اعداد موجود در لیست ورودی بستگی ندارد. در مرحلهٔ اول به دست آوردن کمینه در لیست n عنصری نیاز به پیمودن کل n عدد و n – 1 مقایسه دارد و سپس باید کمینهٔ به دست آمده با اولین عدد جابجا شود. در مرحلهٔ بعدی به دست آوردن دومین کمینه در لیست 1 - n عنصری نیاز به پیمودن کل 1 - n عدد و 2 - n مقایسه دارد و کمینهٔ به دست آمده بادومین عدد جابجا شودو این روند ادامه پیدا می کند. پس کلاً تعداد مقایسه ها عبارتست از:
wiki: مرتب سازی انتخابی