الگوریتم مرتب سازی حبابی

تصور کن یه لیوان آب و چند تا حباب داری. حباب‌های سبک‌تر همیشه به سمت بالا حرکت می‌کنن، درسته؟ الگوریتم مرتب‌سازی حبابی هم دقیقاً همین کار رو با داده‌ها انجام می‌ده. این الگوریتم داده‌ها رو مثل حباب‌هایی که توی آب حرکت می‌کنن، یکی یکی مقایسه و جابجا می‌کنه تا در نهایت به یه لیست کاملاً مرتب برسی.

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

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

# تابع مرتب سازی حبابی در پایتون

def bubble_sort(arr):

    n = len(arr)

    # انجام n-1 دور تکرار برای مرتب‌سازی

    for i in range(n):

        # پرچم برای تشخیص جابجایی

        swapped = False

        # مقایسه و جابجایی عناصر مجاور

        for j in range(0, n-i-1):

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]  # جابجایی

                swapped = True

        # اگر در این دور هیچ جابجایی‌ای انجام نشود، حلقه متوقف می‌شود

        if not swapped:

            break

# تست تابع

numbers = [64, 34, 25, 12, 22, 11, 90]

print("لیست قبل از مرتب‌سازی:", numbers)

bubble_sort(numbers)

print("لیست بعد از مرتب‌سازی:", numbers)

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

فرض کن یه لیست نامرتب از اعداد داریم: [5, 1, 4, 2, 8]. هدف ما اینه که این لیست رو به ترتیب صعودی مرتب کنیم.

دور اول: حرکت بزرگترین عنصر به انتها

• گام اول: 5 و 1 رو مقایسه می‌کنیم. چون 1 کوچکتره، جابجا می‌شن: [1, 5, 4, 2, 8]
• گام دوم: 5 و 4 رو مقایسه می‌کنیم. 4 کوچکتره، پس جابجا می‌شن: [1, 4, 5, 2, 8]
• گام سوم: 5 و 2 رو مقایسه می‌کنیم. 2 کوچکتره، دوباره جابجایی داریم: [1, 4, 2, 5, 8]
• گام چهارم: 5 و 8 رو مقایسه می‌کنیم. 5 کوچکتره، پس جابجایی نداریم: [1, 4, 2, 5, 8]

// تابع مرتب سازی حبابی در دارت

void bubbleSort(List<int> arr) {

  int n = arr.length;

  // انجام n-1 دور تکرار برای مرتب‌سازی

  for (int i = 0; i < n; i++) {
      
    bool swapped = false;

    // مقایسه و جابجایی عناصر مجاور

    for (int j = 0; j < n - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {
          
        // جابجایی عناصر

        int temp = arr[j];

        arr[j] = arr[j + 1];

        arr[j + 1] = temp;

        swapped = true;

      }

    }

    // اگر هیچ جابجایی‌ای در این دور انجام نشود، حلقه متوقف می‌شود

    if (!swapped) break;
        
  }

}

// تست تابع

void main() {

  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];

  print('لیست قبل از مرتب‌سازی: $numbers');

  bubbleSort(numbers);

  print('لیست بعد از مرتب‌سازی: $numbers');
  
}

بعد از این دور، بزرگترین عدد (8) به انتهای لیست منتقل شده و در جایگاه صحیح خودش قرار گرفته. حالا لیست رو داریم: [1, 4, 2, 5, 8].

دور دوم: تکرار فرآیند برای عناصر باقی‌مانده

حالا همین فرآیند رو برای n-1 عنصر اول تکرار می‌کنیم (چون عنصر آخر مرتب شده):

• گام اول: 1 و 4 رو مقایسه می‌کنیم. جابجایی نداریم.
• گام دوم: 4 و 2 رو مقایسه می‌کنیم. 2 کوچکتره، جابجا می‌شن: [1, 2, 4, 5, 8]
• گام سوم: 4 و 5 رو مقایسه می‌کنیم. جابجایی نداریم.

بعد از این دور، دومین عدد بزرگ (5) هم در جایگاه خودش قرار گرفته. لیست فعلی: [1, 2, 4, 5, 8].

دورهای بعدی تا مرتب‌سازی کامل:

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

مرتب‌سازی حبابی به زبان کد: پایتون و دارت

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

پیاده‌سازی با پایتون:

# تابع مرتب‌سازی حبابی در پایتون
def bubble_sort(arr):
    n = len(arr)
    # n-1 دور تکرار برای مرتب‌سازی
    for i in range(n):
        swapped = False # پرچم برای تشخیص جابجایی
        # مقایسه و جابجایی عناصر مجاور
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j] # جابجایی
                swapped = True
        # اگر در این دور هیچ جابجایی‌ای انجام نشود، حلقه متوقف می‌شود
        if not swapped:
            break

# تست تابع
numbers = [64, 34, 25, 12, 22, 11, 90]
print("لیست قبل از مرتب‌سازی:", numbers)
bubble_sort(numbers)
print("لیست بعد از مرتب‌سازی:", numbers)

توضیح کد پایتون: اینجا n طول آرایه رو مشخص می‌کنه. حلقه‌ی بیرونی (for i in range(n)) هر بار یک عنصر رو به جایگاه نهایی خودش می‌فرسته، و حلقه‌ی داخلی (for j in range(0, n - i - 1)) عناصر مجاور رو مقایسه و جابجا می‌کنه. اگر در یک دور کامل هیچ جابجایی‌ای اتفاق نیفته (یعنی swapped مقدار False باقی بمونه)، یعنی لیست مرتب شده و نیازی به ادامه‌ی کار نیست.

پیاده‌سازی با دارت:

// تابع مرتب‌سازی حبابی در دارت
void bubbleSort(List<int> arr) {
  int n = arr.length;
  // n-1 دور تکرار برای مرتب‌سازی
  for (int i = 0; i < n; i++) {
    bool swapped = false;
    // مقایسه و جابجایی عناصر مجاور
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // جابجایی عناصر
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    // اگر هیچ جابجایی‌ای در این دور انجام نشود، حلقه متوقف می‌شود
    if (!swapped) break;
  }
}

// تست تابع
void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];
  print('لیست قبل از مرتب‌سازی: $numbers');
  bubbleSort(numbers);
  print('لیست بعد از مرتب‌سازی: $numbers');
}

توضیح کد دارت: پیاده‌سازی در دارت هم شبیه پایتون است و از دو حلقه‌ی تو در تو بهره می‌برد. منطق swapped برای بهینه‌سازی و توقف زودتر الگوریتم در هر دو زبان مشابه است.

مزایا و معایب مرتب‌سازی حبابی: نقاط قوت و ضعف

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

مزایا:

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

معایب:

• کارایی پایین برای داده‌های بزرگ: بدترین عیب این الگوریتم، کارایی ضعیف آن برای مجموعه‌های داده‌ی بزرگ است. پیچیدگی زمانی آن در بدترین و متوسط حالت O(n^2) است که باعث می‌شود برای حجم بالای داده‌ها بسیار کند عمل کند.
• جابجایی‌های زیاد: در مقایسه با سایر الگوریتم‌های مرتب‌سازی، تعداد جابجایی‌ها (swaps) در مرتب‌سازی حبابی می‌تواند بسیار زیاد باشد که به عملکرد آن آسیب می‌زند.
• عدم بهینه‌سازی ذاتی: حتی اگر لیست تقریباً مرتب باشد، این الگوریتم همچنان مجبور است تعداد زیادی مقایسه انجام دهد (مگر اینکه بهینه‌سازی swapped را به آن اضافه کنیم).

• آموزش و یادگیری: بهترین مثال برای معرفی مفهوم الگوریتم‌های مرتب‌سازی به دانشجویان.
• لیست‌های کوچک: در مواردی که تعداد عناصر بسیار کم است (مثلاً کمتر از 10-20 آیتم)، سادگی پیاده‌سازی آن می‌تواند بر کارایی پایینش غلبه کند.
• تشخیص لیست‌های تقریباً مرتب: نسخه‌ی بهینه‌شده‌ی آن می‌تواند به سرعت تشخیص دهد که یک لیست تقریباً مرتب است و در زمان کمی کار را به اتمام برساند.

پرسش‌های متداول درباره مرتب‌سازی حبابی:

جمع‌بندی: حبابی کوچک اما مهم

مرتب‌سازی حبابی شاید بهترین یا سریع‌ترین الگوریتم مرتب‌سازی نباشه، اما قطعاً یکی از مهم‌ترین‌هاست؛ چون دروازه‌ی ورود بسیاری از ما به دنیای جذاب و گاهی پیچیده‌ی الگوریتم‌هاست. با درک این الگوریتم پایه، می‌تونی به سراغ الگوریتم‌های پیشرفته‌تر بری و مهارت‌های برنامه‌نویسی خودت رو ارتقا بدی.

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