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

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مرتب‌سازی انتخابی - الگوریتمستان
الگوریتمستان
  »  

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

        آشنایی با روش مرتب‌سازی انتخابی،همراه با قطعه کد به زبان برنامه‌نویسی ++C
آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی انتخابی» شهریور ماه ۱۳۸۵ از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.

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

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

وبگاه:

متن پیام: *

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

 


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

توروخدا لطف کنید برنامه های کوچیکی مثل تمرینای حل نشده کتاب رو هم بزارین!!!!!!!!!!!!!!!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


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

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


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

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


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

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

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


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

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

مرسی0403


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

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

یکشنبه، ۷ خرداد ماه ۱۳۹۶، ساعت ۲۱:۳۶
مسعود اقدسی‌فام

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


دوشنبه، ۳ اردیبهشت ماه ۱۳۹۷، ساعت ۰۷:۱۷

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

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


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

   

   

پیوند کوتاه: عمر نوشته:  ۲۷۴۰ روز
تعداد بازدید:  ۴۶۱۶۳ بازدید
تعداد امتیاز:  ۶۵ امتیاز
میانگین امتیاز:  ۴.۰۰  از  ۵.۰۰
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  مرتب‌سازی ادغامی
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
»  مرتب‌سازی هرمی
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
»  مرتب‌سازی سریع
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
»  مرتب‌سازی درجی
        آشنایی با روش مرتب‌سازی درجی، همراه با قطعه کد به زبان برنامه‌نویسی ++C
»  مرتب‌سازی حبابی
        آشنایی با روش مرتب‌سازی حبابی و بحث در مورد عملکرد آن، با قطعه کد به زبان برنامه‌نویسی ++C