در این مقاله قصد داریم در مورد الگوریتم مرتب سازی تعویضی Exchange Sort Algorithm بحث کنیم. این الگوریتم یک روش مرتب سازی ساده و درجا است که با پیدا کردن کوچک‌ترین عنصر در بخش نامرتب آرایه و جابه‌جا کردن آن با اولین عنصر این بخش، به تدریج آرایه را مرتب می‌کند. در هر مرحله، بخش مرتب‌شده آرایه بزرگ‌تر می‌شود تا در نهایت کل آرایه مرتب شود. مرتب سازی تعویضی به دلیل سادگی و کم بودن تعداد جابه‌جایی‌ها، در مواردی که جابه‌جایی داده‌ها هزینه‌بر است، مناسب است.
الگوریتم مرتب سازی تعویضی چیست؟
الگوریتم مرتب سازی تعویضی یک الگوریتم مرتب سازی ساده و درجا است که شبیه الگوریتم مرتب سازی حبابی است که با یافتن کوچک‌ترین (یا بزرگ‌ترین) عنصر در بخش نامرتب آرایه و جابه‌جا کردن آن با اولین عنصر در آن بخش، عمل مرتب سازی را انجام می‌دهد. این فرآیند به طور متناوب تکرار می‌شود، به این صورت که در هر مرحله، کوچک‌ترین عنصر از بخش نامرتب آرایه انتخاب شده و به انتهای بخش مرتب شده منتقل می‌شود. این الگوریتم با وجود سادگی، به دلیل پیچیدگی زمانی O(n^2)، برای آرایه‌های بزرگ کارایی مناسبی ندارد، اما به دلیل تعداد کم جابه‌جایی‌ها، در مواردی که جابه‌جایی داده‌ها هزینه‌بر است، می‌تواند مفید باشد.
مراحل پیاده سازی الگوریتم مرتب سازی تعویضی
این الگوریتم، عناصر مجاور آرایه را با هم مقایسه کرده و اگر در ترتیب نامناسبی قرار داشته باشند، جای آنها را عوض می‌کند. این فرایند را به صورت مکرر تکرار می‌کند تا آرایه مرتب شود.
مثال:
arr[] = {5, 1, 4, 2, 8}
مراحل:
مرحله ۱: پیمایش اول
مقایسه ۵ و ۱: 5 > 1 ، پس تعویض می‌کنیم. آرایه می‌شود:
{۱, ۵, ۴, ۲, ۸}
مقایسه ۵ و ۴: 5 > 4 ، پس تعویض می‌کنیم. آرایه می‌شود:
{۱, ۴, ۵, ۲, ۸}
مقایسه ۵ و ۲: 5 > 2 ، پس تعویض می‌کنیم. آرایه می‌شود:
{۱, ۴, ۲, ۵, ۸}
مقایسه ۵ و ۸: 5 < 8 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۴, ۲, ۵, ۸}
مرحله ۲: پیمایش دوم
مقایسه ۱ و ۴: 1 < 4 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۴, ۲, ۵, ۸}
مقایسه ۴ و ۲: 4 > 2 ، پس تعویض می‌کنیم. آرایه می‌شود:
{۱, ۲, ۴, ۵, ۸}
مقایسه ۴ و ۵: 4 < 5 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۲, ۴, ۵, ۸}
مقایسه ۵ و ۸: 5 < 8 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۲, ۴, ۵, ۸}
مرحله ۳: پیمایش سوم
مقایسه ۱ و ۲: 1 < 2 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۲, ۴, ۵, ۸}
مقایسه ۲ و ۴: 2 < 4 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۲, ۴, ۵, ۸}
مقایسه ۴ و ۵: 4 < 5 ، تعویضی انجام نمی‌شود. آرایه می‌ماند:
{۱, ۲, ۴, ۵, ۸}
در این مرحله آرایه بصورت (۸,۵,۴,۲,۱) مرتب شده است.
مزایا و معایب الگوریتم مرتب سازی تعویضی
در زیر به بررسی مزایا و معایب الگوریتم مرتب سازی تعویضی می‌پردازیم:
مزایا:
- سادگی پیاده‌سازی: الگوریتم تعویضی بسیار ساده و قابل فهم است و پیاده‌سازی آن آسان است. این امر برای آموزش مفاهیم اولیه مرتب سازی بسیار مفید است.
- پایداری: مرتب سازی تعویضی پایدار است. این بدان معناست که ترتیب نسبی عناصر با مقدار برابر در آرایه خروجی، همان ترتیب آنها در آرایه ورودی است.
- مناسب برای آرایه‌های کوچک و تقریباً مرتب: اگر آرایه ورودی کوچک باشد یا عناصر آن تقریباً مرتب باشند، الگوریتم تعویضی می‌تواند عملکرد قابل قبولی داشته باشد. در این موارد، سربار الگوریتم‌های پیشرفته‌تر توجیه‌پذیر نیست.
معایب:
- کارایی پایین: پیچیدگی زمانی الگوریتم تعویضی در حالت بدترین و متوسط O(n²) است. این بدان معناست که زمان اجرای الگوریتم با افزایش تعداد عناصر به صورت مجذوری افزایش می‌یابد. بنابراین، برای آرایه‌های بزرگ، این الگوریتم بسیار کند است.
- تعداد زیاد مقایسه: الگوریتم تعویضی تعداد زیادی مقایسه بین عناصر انجام می‌دهد، حتی اگر آرایه تقریباً مرتب باشد.
- مناسب برای آرایه‌های بزرگ نیست: به دلیل پیچیدگی زمانی O(n²)، برای آرایه‌های بزرگ، الگوریتم تعویضی بسیار ناکارآمد است. الگوریتم‌های کارآمدتری مانند مرتب سازی ادغامی (Merge Sort) یا مرتب سازی سریع (Quick Sort) با پیچیدگی زمانی O(n log n) وجود دارند که برای آرایه‌های بزرگ بسیار مناسب‌تر هستند.
کاربردهای الگوریتم مرتب سازی تعویضی
الگوریتم‌های مرتب سازی تعویضی مانند Bubble Sort و Selection Sort با وجود سادگی، در عمل برای داده‌های بزرگ کارایی مناسبی ندارند. اما در برخی شرایط خاص، استفاده از این الگوریتم‌ها منطقی و مؤثر است. در ادامه به مهم‌ترین کاربردهای آنها اشاره می‌شود:
۱. آموزش مفاهیم پایه الگوریتم و برنامه‌نویسی
- سادگی مفهومی و پیاده‌سازی این الگوریتم‌ها باعث شده‌اند که در دوره‌های مقدماتی آموزش برنامه‌نویسی، به عنوان اولین الگوریتم‌های مرتب سازی آموزش داده شوند.
- به دلیل ماهیت مرحله‌به‌مرحله و قابل مشاهده بودن عملکرد، در تصویری‌سازی الگوریتم‌ها نیز بسیار کاربرد دارند.
۲. استفاده در سیستم‌های کوچک با نیازهای ساده
- در سیستم‌های تعبیه‌شده (Embedded Systems) با منابع محدود که داده‌های ورودی کوچک هستند (مثلاً کمتر از ۱۰ یا ۲۰ عنصر)، استفاده از الگوریتم‌هایی مانند Selection Sort منطقی است.
- گاهی در میکروکنترلرها یا سیستم‌های ساده، سادگی کد مهم‌تر از کارایی است.
۳. کاربرد در داده‌های تقریباً مرتب
- نسخه بهینه‌شده‌ی Bubble Sort می‌تواند عملکرد خوبی در مرتب سازی داده‌هایی که تقریباً مرتب هستند، داشته باشد (زمان اجرا نزدیک به O(n)).
- در این موارد، الگوریتم ممکن است در همان چند دور ابتدایی متوقف شود، چون متوجه می‌شود لیست مرتب است.
۴. موقعیت‌های تست و بررسی عملکرد الگوریتم‌ها
- الگوریتم‌های تعویضی به عنوان معیار پایه (Baseline) در تست و ارزیابی سایر الگوریتم‌های مرتب سازی پیچیده‌تر مورد استفاده قرار می‌گیرند.
۵. پروژه‌ها و تمرین‌های دانشگاهی
- به دلیل سادگی، این الگوریتم‌ها انتخاب مناسبی برای تمرین طراحی و تحلیل الگوریتم‌ها در دروس دانشگاهی هستند.
- در تمرین‌های مقایسه‌ای، برای بررسی تفاوت کارایی بین الگوریتم‌های O(n²) و الگوریتم‌های بهینه‌تر مانند Merge Sort و Quick Sort به‌کار می‌روند.
مقایسه الگوریتم مرتب سازی تعویضی با ادغامی
در این قسمت از مقاله به مقایسه الگوریتم مرتب سازی تعویضی با الگوریتم ادغامی می‌پردازیم:
| ویژگی | مرتب سازی تعویضی | مرتب سازی ادغامی |
| پیچیدگی زمانی ( بدترین حالت) | (۲^n)O | ( n log n )O |
| پیچیدگی زمانی ( بهترین حالت) | (n)O | O( n log n ) |
| روش اجرا | مقایسه و تعویض عناصر مجاور | تقسیم بازگشتی و ادغام مرتب شده |
| کارایی روی داده های بزرگ | ضعیف | بسیار خوب |
| مناسب برای سیستم های با حافظه محدود؟ | بله | خیر (نیاز به حافظه اضافی دارد) |
پیاده سازی الگوریتم مرتب سازی تعویضی
در ادامه پیاده سازی الگوریتم با زبان‌های برنامه نویسی مختلف آورده شده است.
پیاده سازی الگوریتم مرتب سازی تعویضی با زبان برنامه نویسی ++C
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for Exchange sort
// in Descending order
void exchangeSort(int num[], int size)
{
int i, j, temp;
for (i = 0; i < size - 1; i++) {
for (j = i + 1; j < size; j++) {
// Sorting into descending
// order when previous element
// is smaller than next element
if (num[i] < num[j]) {
// Swapping
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
// Driver code
int main()
{
int arr[5] = { 5, 1, 4, 2, 8 };
// Function call
exchangeSort(arr, 5);
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
پیاده سازی الگوریتم مرتب سازی تعویضی با زبان برنامه نویسی جاوا
import java.util.Arrays;
public class ExchangeSort {
// Function for Exchange sort in Descending order
static void exchangeSort(int[] num) {
int size = num.length;
int temp;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
// Sorting into descending order when previous element
// is smaller than the next element
if (num[i] < num[j]) {
// Swapping
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
// Driver code
public static void main(String[] args) {
int[] arr = { 5, 1, 4, 2, 8 };
// Function call
exchangeSort(arr);
// Printing the sorted array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
پیاده سازی الگوریتم مرتب سازی تعویضی با زبان برنامه نویسی پایتون
# Python code for the above approach
# Function for Exchange sort
# in Descending order
def exchange_sort(arr):
size = len(arr)
for i in range(size - 1):
for j in range(i + 1, size):
# Sorting into descending
# order when previous element
# is smaller than next element
if arr[i] < arr[j]:
# Swapping
arr[i], arr[j] = arr[j], arr[i]
# Driver code
if __name__ == "__main__":
arr = [5, 1, 4, 2, 8]
# Function call
exchange_sort(arr)
for num in arr:
print(num, end=" ")
پیاده سازی الگوریتم مرتب سازی تعویضی با زبان برنامه نویسی #C
using System;
class Program {
// Function for Exchange sort
// in Descending order
static void ExchangeSort(int[] num, int size)
{
int i, j, temp;
for (i = 0; i < size - 1; i++) {
for (j = i + 1; j < size; j++) {
// Sorting into descending
// order when previous element
// is smaller than next element
if (num[i] < num[j]) {
// Swapping
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
// Driver code
static void Main()
{
int[] arr = { 5, 1, 4, 2, 8 };
// Function call
ExchangeSort(arr, 5);
// Printing the sorted array
for (int i = 0; i < 5; i++) {
Console.Write(arr[i] + " ");
}
}
}
پیاده سازی الگوریتم مرتب سازی تعویضی با زبان برنامه نویسی جاوا
// Function for Exchange sort in Ascending order
function exchangeSort(arr) {
const size = arr.length;
for (let i = 0; i < size - 1; i++) {
// Outer Loop
for (let j = i + 1; j < size; j++) {
// Inner Loop
// Sorting into ascending order if
// the previous element is bigger than the next
// element; we swap to make it in ascending order
if (arr[i] > arr[j]) {
// Swapping
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
// Driver code
const arr = [5, 1, 4, 2, 8];
// Function call
exchangeSort(arr);
// Output the sorted array
console.log(arr.join(' '));
خروجی تمام کد های بالا بصورت زیر است:
۸ ۵ ۴ ۲ ۱
سخن آخر
الگوریتم‌های مرتب سازی تعویضی مانند Bubble Sort و Selection Sort، با وجود سادگی و سهولت درک، از نظر عملکرد برای داده‌های بزرگ کارایی پایینی دارند و معمولاً در کاربردهای واقعی جای خود را به الگوریتم‌های بهینه‌تری مانند Merge Sort می‌دهند. با این حال، به دلیل سادگی مفهومی، عدم نیاز به حافظه اضافی و مناسب‌بودن برای داده‌های کوچک یا تقریباً مرتب، این الگوریتم‌ها همچنان در محیط‌های آموزشی، پروژه‌های تمرینی، و برخی سیستم‌های محدود کاربرد دارند. در نهایت، انتخاب الگوریتم مرتب سازی باید بر اساس نیاز، شرایط اجرایی و منابع در دسترس انجام گیرد.
