الگوریتمستان - الگوریتم مرتب‌سازی انتخابی

تحلیل عملکرد و پیاده‌سازی با زبان‌های برنامه‌نویسی ++C و Python

✤    ۹ شهریور ۱۳۸۵ - آخرین به‌روزرسانی: ۶ فروردین ۱۳۹۹

روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر لیست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده و به انتهای لیست منتقل می‌کند.

لیست اعداد زیر را در نظر بگیرید که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:

  

2 8 4 1 7

  

در مرحله اول، کل لیست از ابتدا تا انتها بررسی شده و بزرگترین عنصر با عنصر انتهای لیست نامرتب جابجا می‌شود:

  

1)    2 8 4 1 7    →    2 7 4 1 8

در مرحله دوم، پیمایش از ابتدای لیست تا عنصر چهارم صورت گرفته و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:

  

2)    2 7 4 1 8    →    2 1 4 7 8

  

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

  

3)    2 1 4 7 8    →    2 1 4 7 8

  

و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:

  

4)    2 1 4 7 8    →    1 2 4 7 8

  

و به این ترتیب لیست مرتب می‌شود.

  

پیاده‌سازی مرتب‌سازی انتخابی

  [برگرد بالا]

الگوریتم مرتب‌سازی انتخابی به زبان برنامه‌نویسی ++C برای مرتب کردن عناصر آرایه‌ای از اعداد صحیح به صورت زیر پیاده‌سازی می‌شود:

  

void selection_sort(int arr[], int n){

  int i, j, 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;

  }

}

  

یک پیاده‌سازی الگوریتم در زبان Python نیز به صورت زیر است.

  

def selection_sort(arr):

    for i in range(len(arr) - 1, 0, -1):

         maxIndex  = 0

         for j in range(1, i + 1):

             if arr[maxIndex] < arr[j]:

                 maxIndex = j

        arr[i], arr[maxIndex] = arr[maxIndex], arr[i]

  

حلقه بیرونی حد نصاب پیمایش را مشخص کرده و حلقه درونی به ازای هر تکرار حلقه بیرونی، بزرگترین عنصر لیست نامرتب را میابد. سپس محل این عنصر با عنصر انتهای بخش نامرتب جابجا می‌شود.

  

پیچیدگی زمانی مرتب‌سازی انتخابی

  [برگرد بالا]

تعداد عناصر لیست را n در نظر می‌گیریم. بر اساس توضیحات فوق این الگوریتم n - 1 مرحله دارد. در هر مرحله، عنصر ابتدایی در max قرار گرفته و بقیه عناصر با آن مقایسه می‌شوند. پس در مرحله اول تعداد n - 1 مقایسه، در مرحله دوم تعداد n - 2 مقایسه و به همین ترتیب در مرحله iام تعداد n - i مقایسه صورت می‌گیرد. پس اگر (T(n تعداد کل مقایسه‌ها را نشان دهد، می‌توان نوشت:

  

\[ T(n) = (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 = \frac{n (n - 1)}{ 2 } \]

  

که از مرتبه $\theta(n^2)$ است.

  

ویژگی‌های مرتب‌سازی انتخابی

  [برگرد بالا]

1- پیچیدگی زمانی اجرای این الگوریتم بر اساس محاسبات فوق در بدترین حالت $\theta(n^2)$ است. با توجه به قطعه کد نوشته شده، ترتیب عناصر تغییری در عملکرد آن اینجا نمی‌کند. یعنی این الگوریتم برای داده‌های کاملا مرتب، نامرتب تصادفی و مرتب معکوس به یک ترتیب عمل کرده و تمام مقایسه‌های محاسبه شده در رابطه فوق را انجام می‌دهد. بنابراین پیچیدگی این الگوریتم در بهترین حالت و حالت منوسط نیز $\theta(n^2)$ است.

2- مرتب‌سازی انتخابی یک روش مرتب‌سازی درجا است. یعنی عملیات مرتب‌سازی به در داخل خود لیست و بدون نیاز به حافظه کمکی بزرگ انجام می‌گیرد.

3- در پیاده‌سازی مرتب‌سازی انتخابی به روش فوق، اگر دو عنصر با مقدار بیشینه داشته باشیم، اولی انتخاب شده و به انتهای لیست منتقل می‌شود. در نتیجه ترتیب آنها به هم می‌خورد. بنابراین این پیاده‌سازی روش پایدار نیست. در روش پایدار ترتیب عناصر با مقدار یکسان تغییر نمی‌کند. اما اگر در مقایسه عناصر آرایه به جای > از => استفاده کنید، مرتب‌سازی پایدار خواهد شد.


نسخه‌ی اولیه‌ی این نوشته از وبلاگ برنامه‌نویسی و طراحی الگوریتم به الگوریتمستان منتقل شده است.

تا کنون ۷۸ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

amasoudfam.ir/l/nkaea

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram

نام: *  
پست الکترونیک (محرمانه):
پیام: *  
• mesi
۸ دی ۱۳۸۵، ساعت ۱۲:۱۵

mamno0o0n az matalebeto0o0n

o0o0midvaram dar karat mo0o0vafagh bashi

زندگی دشواری وظیفه است.

                                                    احمد شاملو

• hassan
۹ بهمن ۱۳۸۵، ساعت ۱۰:۳۹

خیلی ممنون از مطالبتون

• najva
۲۷ اردیبهشت ۱۳۸۶، ساعت ۱۵:۱۵

عالی بود    

از این به بعد مرتب اینجا میام

• مريم
۷ خرداد ۱۳۸۶، ساعت ۲۲:۵۶

سلام

من برنامه ي انواع سورت رو در سي پلاس پلاس مي خوام لطفا به من كمك كنيد فقط چند روز وقت دارم.

درجي

جايگزيني

انتخابي

quick sort

خواهش ميكنم به من كمك كنيد.

• تکنیک برتر
۲۰ مرداد ۱۳۸۶، ساعت ۱۰:۰۷

می خواستم اگه می شه روش مرتب سازی حبابی رو کامل توضیح بدهید

مرسی به خاطر آموزش

• ملیحه
۲۶ مرداد ۱۳۸۶، ساعت ۱۱:۵۹

سلام

خسته نباشید مفید بود برام

• Payman84ce
۱ خرداد ۱۳۸۷، ساعت ۰۶:۴۹

ghabl az temp bayad dastore

IF(MAX!=N-I) GHARAR GIRAD

• مهسا
۲۷ خرداد ۱۳۸۷، ساعت ۱۰:۱۴

سلام              خسته نباشید من تابع بازگشتی مرتب سازی انتخابی و مرتب سازی انتخابی می خواهم لطفا کمکم کنید مرسی

• saeed
۲۵ تیر ۱۳۸۷، ساعت ۲۱:۵۵

بسيار عالي بود

• الی
۱۴ اردیبهشت ۱۳۹۰، ساعت ۱۷:۱۹

توروخدا لطف کنید برنامه های کوچیکی مثل تمرینای حل نشده کتاب رو هم بزارین!!!!!!!!!!!!!!!02

• سحر
۲۰ مهر ۱۳۹۰، ساعت ۱۸:۱۶

میشه کد این برنامه رو بنویسید.10 عدد از ورودی خوانده در آرایه قرار بده بعد عناصر آرایه را به روش حبابی مرتب کنه و چاپ11

• haji
۳۰ بهمن ۱۳۹۰، ساعت ۱۹:۳۷

متشــــــــــــــــــــــــــــــــــکرم06

• afshin
۲۴ اسفند ۱۳۹۰، ساعت ۱۵:۰۵

این کد کار نمیکنه

۲۴ اسفند ۱۳۹۰، ساعت ۱۵:۳۲
• مسعود اقدسی‌فام

کد رو بررسی کردم افشین خان. مشکلی نداره.

اگه مورد خاصی وجود داره بگید، بررسی کنم.

• امیر رضا
۲۵ آبان ۱۳۹۱، ساعت ۱۱:۴۸

سلام

اگه میشد این الگوریتمها را برنامه اش را خط به خط توضیح میدادید خوب بود ممنون

۲۵ آبان ۱۳۹۱، ساعت ۱۳:۴۸
• مسعود اقدسی‌فام

سلام دوست عزیز

کدهایی در این سطم با فرض اینکه استفاده کننده اونقدر قدرت برنامه‌نویسی داره که بتونه مشابهش رو بنویسه بدون هیچ توضیحی قرار داده می‌شن.

• زهرا
۳ آبان ۱۳۹۲، ساعت ۱۰:۲۹

ممنون06

• عباس صادقی
۱۰ آذر ۱۳۹۲، ساعت ۱۹:۲۶

با سلام

دوستان عزیز میتونید منو در ساخت پروژم راهنمایی کنید

اینم پروژه: برنامه ای بنویسید که به روش درخت انتخابی 4 آرایه 10 عنصری را از کاربر دریافت و آنها را در یک آرایه بزرگتر قرار دهد؟

• ماندانا
۲۲ فروردین ۱۳۹۳، ساعت ۱۲:۳۹

سلام.من یه سوال برنامه نویسی c++دارم.کسی هست بلد باشه؟

دیوونه شدم از دستش07

• ازادی
۱ اردیبهشت ۱۳۹۳، ساعت ۰۰:۳۱

سلام لطفا" اگه کدموازی این برنامه یابرنامه دیگه ای رودارین به ایمیلم ارسال کنید

• پری
۲۳ خرداد ۱۳۹۳، ساعت ۲۲:۱۰

اين همون پنكيك سورت يا مرتب سازی كلوچه اي هست?

• baran
۱۰ مهر ۱۳۹۴، ساعت ۰۹:۵۸

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

• الناز
۲۵ مهر ۱۳۹۴، ساعت ۰۲:۱۳

ضمن عرض سلام و خسته نباشید

ایا در الگوریتم های مرتب سازی(انتخابی،حبابی، ...) که قسمت اخر،مکان یک عدد رو با حافطه ی کمکی تغییر میدیم،میتونیم بدون در نظر گرفتن اون حافطه بنویسیم؟

منظورم این قسمت و متغیر "تمپ" میباشد

ایا میتوان بدون در نظر گرفتن متغیر تمپ الگوریتم مرتب سازی نوشت؟

temp = arr[ i ];

   arr[ i ] = arr[ max ];

   arr[ max ] = temp;

۲۵ مهر ۱۳۹۴، ساعت ۰۹:۳۴
• مسعود اقدسی‌فام

بله این امکان وجود داره. به عنوان مثال این پیوند رو ببینید:

https://en.wikipedia.org/wiki/XOR_swap_algorithm

•  AzizAhmad
۱ اردیبهشت ۱۳۹۵، ساعت ۱۰:۳۶

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

•  AzizAhmad
۱ اردیبهشت ۱۳۹۵، ساعت ۱۰:۳۷

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

• Azizahmad
۱ اردیبهشت ۱۳۹۵، ساعت ۱۰:۴۱

سلام خدمت همه شما دوستان..........

کسی میتونه برایم راهنمایی کنه تا آموزش راهنمایی تیوری دیتابس را پیدا نمایم..

• جیران عرفانی
۲۲ اردیبهشت ۱۳۹۶، ساعت ۱۲:۰۴

مطالب بسیاررررررر آموزنده بود و خیلی بهم کمک کرد

مرسی0403

• مهدی
۷ خرداد ۱۳۹۶، ساعت ۱۵:۰۴

نفهمیدم چرا ان رو منهای یک کردید  تو فور اولی؟

۷ خرداد ۱۳۹۶، ساعت ۲۱:۳۶
• مسعود اقدسی‌فام

اگر آرایه n‌ عنصر داشته باشه، اندیس آخرین عنصر n - 1 هست.

• ابوالفضل شرافت
۳ اردیبهشت ۱۳۹۷، ساعت ۰۷:۱۷

توضیح فوق العاده ای بود

ممنون از تیم الگوریتمستان

• اسی
۸ اردیبهشت ۱۳۹۸، ساعت ۲۰:۵۸

06مرسی از ملب خوب وبدرد به خورتون امروز بدردم خورد فقط این صفری که قبل فرمول قرار دادی چی هس؟   θ(n2)

• طراحی قالب وردپرس
۸ اردیبهشت ۱۳۹۸، ساعت ۲۰:۵۹

دمتون گرم مفید بود

• amiralii
۲۵ اردیبهشت ۱۳۹۹، ساعت ۱۵:۲۹

0707070707101011