بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

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

       

آشنایی با روش مرتب‌سازی انتخابی،همراه با قطعه کد به زبان برنامه‌نویسی ++C

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی انتخابی» شهریور ماه 1385 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


روش مرتب‌سازی انتخابی (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];
10     arr[max] = temp;
11   }
12 }

  

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

      

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

  [بازگشت به فهرست]

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


این نوشته آخرین بار در تاریخ دوشنبه، ۱۱ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
        آشنایی با روش مرتب‌سازی حبابی و بحث در مورد عملکرد آن، با قطعه کد به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» مهدی

یکشنبه، ۷ خرداد ماه ۱۳۹۶، ساعت ۱۵:۰۴
نفهمیدم چرا ان رو منهای یک کردید  تو فور اولی؟


یکشنبه، ۷ خرداد ماه ۱۳۹۶، ساعت ۲۱:۳۶
مسعود:
اگر آرایه n‌ عنصر داشته باشه، اندیس آخرین عنصر n - 1 هست.

» جیران عرفانی

جمعه، ۲۲ اردیبهشت ماه ۱۳۹۶، ساعت ۱۲:۰۴
مطالب بسیاررررررر آموزنده بود و خیلی بهم کمک کرد
مرسی0403

» Azizahmad

چهارشنبه، ۱ اردیبهشت ماه ۱۳۹۵، ساعت ۱۰:۴۱
سلام خدمت همه شما دوستان..........
کسی میتونه برایم راهنمایی کنه تا آموزش راهنمایی تیوری دیتابس را پیدا نمایم..

»  AzizAhmad

چهارشنبه، ۱ اردیبهشت ماه ۱۳۹۵، ساعت ۱۰:۳۷
ممنون از زحماتی که کشیده اید لطف نموده  پیاده سازی سورت ها را به زبان جاوا هم ارایه نمایید.

»  AzizAhmad

چهارشنبه، ۱ اردیبهشت ماه ۱۳۹۵، ساعت ۱۰:۳۶
ممنون از زحماتی که کشیده اید لطف نموده  پیاده سازی سورت ها را به زبان جاوا هم ارایه نمایید.

» الناز

شنبه، ۲۵ مهر ماه ۱۳۹۴، ساعت ۰۲:۱۳
ضمن عرض سلام و خسته نباشید

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

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

temp = arr[ i ];
    arr[ i ] = arr[ max ];
    arr[ max ] = temp;


شنبه، ۲۵ مهر ماه ۱۳۹۴، ساعت ۰۹:۳۴
مسعود:
بله این امکان وجود داره. به عنوان مثال این پیوند رو ببینید:

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

» baran

جمعه، ۱۰ مهر ماه ۱۳۹۴، ساعت ۰۹:۵۸
برنامه خوبی است ولی اگر ممکن است برنامه مرتب سازی انتخابی به کمک کلاس ها را به ایمیلم ارسال کنید با تشکر

» پری

جمعه، ۲۳ خرداد ماه ۱۳۹۳، ساعت ۲۲:۱۰
اين همون پنكيك سورت يا مرتب سازی كلوچه اي هست?

» ازادی

دوشنبه، ۱ اردیبهشت ماه ۱۳۹۳، ساعت ۰۰:۳۱
سلام لطفا" اگه کدموازی این برنامه یابرنامه دیگه ای رودارین به ایمیلم ارسال کنید

» ماندانا

جمعه، ۲۲ فروردین ماه ۱۳۹۳، ساعت ۱۲:۳۹
سلام.من یه سوال برنامه نویسی c++دارم.کسی هست بلد باشه؟
دیوونه شدم از دستش07

» عباس صادقی

یکشنبه، ۱۰ آذر ماه ۱۳۹۲، ساعت ۱۹:۲۶
با سلام
دوستان عزیز میتونید منو در ساخت پروژم راهنمایی کنید
اینم پروژه: برنامه ای بنویسید که به روش درخت انتخابی 4 آرایه 10 عنصری را از کاربر دریافت و آنها را در یک آرایه بزرگتر قرار دهد؟

» زهرا

جمعه، ۳ آبان ماه ۱۳۹۲، ساعت ۱۰:۲۹
ممنون06

» امیر رضا

پنجشنبه، ۲۵ آبان ماه ۱۳۹۱، ساعت ۱۱:۴۸
سلام
اگه میشد این الگوریتمها را برنامه اش را خط به خط توضیح میدادید خوب بود ممنون



پنجشنبه، ۲۵ آبان ماه ۱۳۹۱، ساعت ۱۳:۴۸
مسعود:
سلام دوست عزیز

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

» afshin

چهارشنبه، ۲۴ اسفند ماه ۱۳۹۰، ساعت ۱۵:۰۵
این کد کار نمیکنه


چهارشنبه، ۲۴ اسفند ماه ۱۳۹۰، ساعت ۱۵:۳۲
مسعود:
کد رو بررسی کردم افشین خان. مشکلی نداره.
اگه مورد خاصی وجود داره بگید، بررسی کنم.

» haji

یکشنبه، ۳۰ بهمن ماه ۱۳۹۰، ساعت ۱۹:۳۷
متشــــــــــــــــــــــــــــــــــکرم06

» سحر

چهارشنبه، ۲۰ مهر ماه ۱۳۹۰، ساعت ۱۸:۱۶
میشه کد این برنامه رو بنویسید.10 عدد از ورودی خوانده در آرایه قرار بده بعد عناصر آرایه را به روش حبابی مرتب کنه و چاپ11

» الی

چهارشنبه، ۱۴ اردیبهشت ماه ۱۳۹۰، ساعت ۱۷:۱۹
توروخدا لطف کنید برنامه های کوچیکی مثل تمرینای حل نشده کتاب رو هم بزارین!!!!!!!!!!!!!!!02