توضیح الگوریتم مرتب سازی تعویضی و پیاده سازی آن در زبان های مختلف

فرایند کار الگوریتم مرتب سازی تعویضی به این صورت است که هر عنصر در آرایه‌های برنامه‌ نویسی را با عنصر دیگری مقایسه می‌کند. در حین مقایسه، عناصری را که در جایگاه مناسب خود قرار نگرفته‌اند، با یکدیگر جابه‌جا یا تعویض می‌کند. دقیقا مانند رفتاری که الگوریتم مرتب سازی حبابی انجام می‌دهد. تنها تفاوت اصلی این الگوریتم‌ها روش آن‌ها برای مقایسه عنصرها است. «الگوریتم مرتب سازی تعویضی» (Exchange Sort Algorithm) به میزان زیادی به الگوریتم مرتب‌سازی حبابی شباهت دارد. در واقع بعضی از افراد، به مرتب‌سازی تعویضی به عنوان نوع دیگری از «مرتب سازی حبابی» (Bubble Sort) رجوع می‌کنند. حتی گاهی وقتی که کدهای مربوط به الگوریتم مرتب سازی تعویضی را می‌بینند، به جای استفاده از نام اصلی آن که مرتب‌سازی تعویضی است، آن را به نام الگوریتم مرتب‌سازی حبابی صدا می‌زنند.

در این مطلب از مجله فرادرس با الگوریتم مرتب سازی تعویضی آشنا می‌شویم. با کمک مثال‌های ساده‌ای سعی می‌کنیم که به بهترین شکل ممکن، این الگوریتم و روش کار آن را درک کنیم. سپس شبه کد مرتبط با آن را می‌بینیم. در بخش بعدی به پیاده‌سازی کدهای الگوریتم از روی آن شبه کد پرداخته‌ایم. در واقع، کدهای مرتب‌سازی تعویضی را با کمک ۵ زبان برنامه نویسی مختلف کدنویسی کردیم. در نهایت هم پیچیدگی‌ها، کاربردها و امتیازهای استفاده از این الگوریتم را بررسی می‌کنیم.

الگوریتم مرتب سازی تعویضی چیست؟

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

مرتب‌سازی تعویضی برای مرتب‌سازی آرایه به هر دو صورت نزولی و صعودی کار می‌کند. برای عملکرد نزولی آن فقط کافی است که شرط مقایسه درون حلقه درونی را برعکس کنیم.

تسلط به روش های طراحی الگوریتم با فرادرس

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

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

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

• فیلم آموزش طراحی الگوریتم به صورت جامع و با مفاهیم کلیدی در فراردس
• فیلم آموزش طراحی الگوریتم همراه با مرور و تست کنکور ارشد در فراردس
• فیلم آموزش طراحی الگوریتم در کنار حل مثال های عملی در فراردس
• فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم در فراردس

مثالی برای درک روش کار الگوریتم

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

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

در مثالی که برای کمک به درک روش کار الگوریتم مرتب‌سازی تعویضی آماده کرده‌ایم، از آرایه‌ فرضی به شکل arr[] = {5, 1, 4, 2, 8} استفاده می‌کنیم. خروجی آرایه باید به صورت {1, 2, 4, 5, 8} شود. به صورت خلاصه می‌توان مراحل کار را در سه قدم توضیح داد.

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

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 )

در بالا می‌بینیم که الگوریتم دو عنصر اول را مقایسه کرده و از آنجا که عدد ۵ بزرگتر از عدد ۱ است، جای آن دو عدد را با هم تعویض می‌کند. سپس با توجه به اینکه هیچ کدام از عناصر از عدد ۱ کوچکتر نیستند، بعد از اولین پیمایش آرایه به شکل زیر در می‌آید.

(1 5 4 2 8) 

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

(1 5 4 2 8 ) –> ( 1 4 5 2 8 )

همین‌طور که مشاهده می‌کنیم، از آنجا که عدد ۴ از عدد ۵ کوچکتر است، جای این دو عنصر نیز در آرایه با هم تعویض می‌شود. مقایسه همین‌طور ادامه پیدا می‌کند تا به عدد ۲ برسیم.

( 1 4 5 2 8 ) –> ( 1 2 5 4 8 )

از آنجا که عدد ۲ هم از عدد ۴ کوچکتر است، باز هم باید جای عنصر دوم با عنصر مقایسه شده با آن تعویض شود. اما - همین‌طور که در پایین مشاهده می‌شود - در ادامه روند هیچ عنصر دیگری کوچکتر از ۲ نیست و آرایه به همان شکل باقی می‌ماند.

( 1 2 5 4 8 )

• مرحله سوم: الان مقدار موجود در جایگاه سوم آرایه را به ترتیب با مابقی عناصر آرایه مقایسه می‌کنیم.

(1 2 5 4 8 ) -> (1 2 4 5 8 )

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

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

شبه کد مرتب سازی تعویضی

برای اینکه هر الگوریتمی را به کدهای زبان برنامه نویسی تبدیل کنیم، همیشه بهتر است که اولین کار، نوشتن شبه کد آن الگوریتم باشد. در کادر زیر شبه کد مربوط به الگوریتم مرتب‌سازی تعویضی را به صورت صعودی تعریف کرده‌ایم.

procedure ExchangeSort(num: list of sortable items)
  n = length(A)

  // outer loop
  for i = 1 to n – 2 do

  // inner loop

      for j = i + 1 to n-1 do

           if num[i] > num[j] do

               swap(num[i], num[j])
           end if
       end for
   end for
end procedure

تمام مراحل مربوط به شبه کد الگوریتم مرتب‌سازی تعویضی به صورت صعودی را در فهرست زیر توضیح داده‌ایم.

• در ابتدای کار بر روی آرایه مورد نظر از خانه arr[1] تا به خانه n – 2  پیمایش می‌کنیم. این پیمایش در حلقه خارجی انجام می‌شود. با کمک پیمایش مورد نظر، هر عنصر را به صورت مجزا با تمام عناصر آرایه به جز خودش مقایسه می‌کنیم. در حلقه درونی همین مقایسه را به صورت منظمی در می‌آوریم. یعنی عنصر مورد نظر را فقط با عناصر بعد از خودش مقایسه می‌کنیم.
• حلقه درونی از ایندکس i + 1st شروع به مقایسه می‌کند. در این فرمول i برابر با ایندکس حلقه خارجی است.
• سپس عنصر i را با عنصر j مقایسه می‌کنیم. هر کدام از این‌ها که بزرگتر باشد باید در خانه عنصر i قرار بگیرد. یعنی در صورت نیاز مقادیر این دو عنصر از آرایه را با یکدیگر جابه‌جا می‌کنیم.
• برای اینکه نظم چیدمان را به صورت نزولی تغییر دهیم، فقط کافی است شرط را برعکس کنیم. یعنی عمل تعویض مقادیر عناصر به شرطی اتفاق بی‌افتد که عنصر j از عنصر i بزرگتر باشد.

• اگر در این مقایسه‌ها به موردی برخورد نکردیم که شرط if num[i] > num[j] برقرار باشد یعنی عناصر در شکل مرتب شده خودشان قرار دارند. بنابراین نیازی به تعویض مکان قرارگیری عنصرهای خاصی وجود ندارد.
• در نهایت فرایند چرخش هر دو حلقه درونی و بیرونی به پایان می‌رسد. از آنجا که ایندکس فعلی حلقه درونی برابر با i+1 است، نیاز نداریم که آخرین عنصر را به حلقه خارجی وارد کنیم. در نتیجه، وقتی که ایندکس حلقه خارجی برابر با n-2 شود، به دلیل ایندکس حلقه داخلی که برابر با i+1 است، آخرین عنصر به صورت خودکار مرتب شده خواهد بود. این سناریو رو می‌توان به عنوان حالت خاص برای این الگوریتم در نظر گرفت.

پیاده سازی کدهای الگوریتم مرتب سازی تعویضی

در این قسمت از مطلب، الگوریتم مرتب سازی تعویضی را از روی شبه کد تعریف شده در بخش قبل با پنج زبان برنامه‌نویسی مختلف پیاده‌سازی کرده‌ایم. داده ورودی به همه کدهای زیر برابر با arr[] = {5, 1, 4, 2, 8} است.

فیلم آموزش برنامه نویسی سورس کدهای الگوریتمی در سی شارپ C#‎ در فرادرس

کلیک کنید

زبان برنامه نویسی ++C

زبان برنامه‌نویسی ++C، یکی از زبان‌های خانواده C و زبانی قدیمی است، اما هنوز هم به عنوان یکی از محبوب‌ترین گزینه‌های برنامه‌نویسی مخصوصا در بعضی از پروژه‌های بزرگ مربوط به مرورگرها یا بازی و غیره استفاده می‌شود. برای پیاده‌سازی الگوریتم مرتب‌سازی تعویضی در زبان ++C باید با حلقه‌ها و قواعد شرطی این زبان آشنا باشید. به همین منظور پیشنهاد می‌کنیم که در صورت نیاز، مطالب بسیار مفید و کامل حلقه for در زبان برنامه نویسی ++C و گزاره های شرطی ساده و تودرتو در ++C به زبان ساده را از مجله فرادرس مطالعه کنید.

در کادر زیر کدهای مربوط به پیاده‌سازی الگوریتم مرتب‌سازی تعویضی را با زبان برنامه نویسی ++C نوشته‌ایم.

زبان برنامه نویسی جاوا

در کادر زیر کدهای مربوط به پیاده‌سازی الگوریتم مرتب‌سازی تعویضی را با زبان برنامه نویسی جاوا نوشته‌ایم.

زبان برنامه نویسی پایتون

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

زبان برنامه نویسی #C

در کادر زیر کدهای مربوط به پیاده‌سازی الگوریتم مرتب‌سازی تعویضی را با زبان برنامه نویسی #C نوشته‌ایم.

زبان برنامه نویسی جاوا اسکریپت

در کادر زیر کدهای مربوط به پیاده‌سازی الگوریتم مرتب‌سازی تعویضی را با زبان برنامه نویسی جاوا اسکریپت نوشته‌ایم.

خروجی مربوط به همه کدهای بالا به صورت زیر به کاربر نمایش داده می‌شود.

1 2 4 5 8 

پیچیدگی زمانی و فضایی مرتب سازی تعویضی

الگوریتم مرتب سازی تعویضی هر عنصر در لیست را به صورت دوبه‌دو با بقیه‌ عنصرها مقایسه می‌کند. اگر جفت عنصرهای مقایسه شده، خارج از ترتیب باشند، آن‌ها را جابه‌جا می‌کند. بنابراین، در همه حالت‌های این الگوریتم یعنی، بهترین، بدترین و حالت میانگین آرایه ورودی، «پیچیدگی زمانی» (Time Complexity) برابر با$$O(N^2)$$است. در این فرمول N تعداد اعضای آرایه ورودی را نشان‌ می‌دهد. از آنجا که هر عنصر با همه عناصر دیگر مقایسه ‌می‌شود. در نتیجه به تعداد$$n^2$$عمل مقایسه انجام خواهد شد.

پیچیدگی فضایی مرتب‌سازی تعویضی هم برابر با$$O(1)$$است.

فیلم های آموزش الگوریتم ها و ساختمان داده فرادرس

توانایی طراحی و نوشتن الگوریتم در کنار داشتن علم مربوط به ساختمان داده می‌تواند باعث خلق برنامه‌های با عملکرد بسیار خوب و مصرف منابع بهینه شود. این دو رشته به ظاهر جدا از هم برای گذاشتن بیشترین تاثیر خود در برنامه‌ها نیاز جدی به یکدیگر دارند.

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

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

• فیلم آموزش ساختمان داده ها به صورت جامع و با نکات مهم در فراردس
• فیلم آموزش طراحی الگوریتم به شکل جامع و با مفاهیم کلیدی در فراردس
• فیلم آموزش طراحی الگوریتم همراه با مرور و تست کنکور ارشد در فراردس
• فیلم آموزش ساختمان داده ها و پیاده سازی در C++‎ در فراردس
• فیلم آموزش پیشرفته ساختمان داده در کنار حل سوالات کنکور ارشد و دکتری در فراردس

مزایای مرتب سازی تعویضی

مزیت اصلی مرتب‌سازی تعویضی، سادگی آن است. البته این الگوریتم برای استفاده در مجموعه داده‌های بزرگ مناسب نیست. پیچیدگی زمانی مرتب‌سازی تعویضی در حالت‌های میانگین و بدترین برابر با$$O(N^2)$$است. زیرا این الگوریتم در هربار اجرای عملیات مرتب‌سازی باید به اندازه$$n*(n-1)/2$$تعداد مقایسه انجام دهد.

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

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

جمع بندی

الگوریتم‌های مرتب‌سازی از کاربردی‌ترین الگوریتم‌ها در برنامه‌نویسی و پیاده‌سازی عملیات کامپیوتری هستند. برای مرتب‌سازی داده‌ها انواع گوناگونی الگوریتم معرفی شده‌اند. بعضی از الگوریتم‌های ساده، مانند مرتب‌سازی تعویضی، گزینه‌ بسیار خوبی برای شروع آشنایی با الگوریتم‌ها و مخصوصا تکنیک‌های پیاده‌سازی کدهای مربوط به آن‌ها به وسیله زبان‌های برنامه نویسی‌اند. الگوریتم مرتب سازی تعویضی از لحاظ ظاهری شباهت بسیار زیادی به الگوریتم «مرتب‌سازی حبابی» (Bubble Sort) دارد. اما در بعضی از سناریو‌ها مرتب‌سازی تعویضی از همتای خود، یعنی الگوریتم مرتب‌سازی حبابی، به میزان نسبتا کارآمدتری عمل می‌کند.

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