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

از کجا شروع کنیم؟

ببین، فرض کن یه لیست از قیمت محصولات داری: ۵۰۰، ۲۰۰، ۸۰۰، ۴۰۰ و ۶۰۰ هزار تومن. می خوای این قیمت ها از ارزون ترین تا گرون ترین مرتب بشن. راه حل اول اینه که خودت با چشم عددها رو جابجا کنی؛ اما کامپیوتر باید دقیقا بدونه هر مرحله چه تصمیمی بگیره. اینجا می رسیم به الگوریتم مرتب سازی حبابی یا همون Bubble Sort.

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

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

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

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

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

مثلا توی لیست [5, 1, 4, 2, 8]، بعد از اولین دور کامل، عدد ۸ در انتهای لیست قرار داره. دور بعد دیگه لازم نیست ۸ رو بررسی کنیم. اسم Bubble Sort هم از این ایده اومده که مقدارهای بزرگ تر کم کم به انتهای آرایه حرکت می کنن؛ نه اینکه واقعا حباب فیزیکی توی کامپیوتر وجود داشته باشه!

این تصویر یه نمای کلی از مفهوم الگوریتم رو نشون می ده. نکته ای که باید ازش یاد بگیری خود رنگ و شکل نیست؛ مقایسه جفت های مجاور و کوچک شدن بخش نامرتب در هر دوره. اگه این دو تا رو بفهمی، بخش سخت داستان رو رد کردی.

یه تفاوت مهم رو همین جا یاد بگیر: «مرتب کردن» با «پیدا کردن» فرق داره. مرتب سازی حبابی ترتیب داده ها رو تغییر می ده؛ ولی جستجوی خطی و جستجوی دودویی برای پیدا کردن یک مقدار استفاده می شن. مخصوصا الگوریتم جستجوی دودویی معمولا به داده مرتب نیاز داره؛ البته این دلیل نمی شه قبل از هر جستجو حتما Bubble Sort اجرا کنیم.

مرتب سازی حبابی با مثال قدم به قدم

حالا همون مثال معروف رو با هم جلو می بریم. لیست اولیه مون [5, 1, 4, 2, 8] هست. هدفمون اینه که آخر کار [1, 2, 4, 5, 8] داشته باشیم. هر دور یا Pass از چپ به راست حرکت می کنیم و فقط عنصرهای کناری رو مقایسه می کنیم.

برای اینکه باورت بشه، دور اول رو ریزتر باز کنیم. اول ۵ و ۱ رو مقایسه می کنیم و نتیجه می شه [1, 5, 4, 2, 8]. بعد ۵ و ۴ جابجا می شن و می رسیم به [1, 4, 5, 2, 8]. مرحله بعد ۵ و ۲ هست و لیست به [1, 4, 2, 5, 8] می رسه. در نهایت ۵ از ۸ کوچیک تره و جابجایی نداریم. این چهار مقایسه، دور اول رو کامل می کنن.

دور دوم به جای چهار مقایسه، فقط سه مقایسه لازمه؛ چون انتهای لیست همین الان مرتب شده. نتیجه [1, 2, 4, 5, 8] می شه. دور سوم با دو مقایسه و بدون هیچ جابجایی تموم می شه. پس اگه یک متغیر مثل swapped داشته باشیم، می فهمیم داده ها مرتب شدن و همون لحظه خارج می شیم.

حالا یه تمرین کوچیک: روی کاغذ [4, 3, 2, 1] رو بنویس. هر بار که دو همسایه رو عوض می کنی یه خط بکش. چند جابجایی لازم شد؟ جواب درست شش تاست. همین تمرین ساده، تفاوت درک کردن الگوریتم با حفظ کردن کد رو نشون می ده.

شبه کد Bubble Sort قبل از برنامه نویسی

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

bubble_sort(items):
    for each pass:
        swapped = false
        compare adjacent items in the unsorted section
        if left > right:
            swap them
            swapped = true
        if swapped is false:
            stop

اینجا left > right یعنی می خوایم صعودی مرتب کنیم. برای نزولی کردن می تونیم جهت مقایسه رو برعکس کنیم. فقط این شبه کد رو با پایتون اشتباه نگیر؛ نمونه اجرایی واقعی پایین قرار داره.

پیاده سازی الگوریتم مرتب سازی حبابی در ۳ زبان

من سه زبان رو انتخاب کردم چون ممکنه یکی با پایتون شروع کرده باشه، یکی مشغول یادگیری دارت و فلاتر باشه، یکی هم از روبی خوشش بیاد. ایده Bubble Sort توی هر سه تا دقیقا یکسانه. چیزی که عوض می شه شکل نوشتن حلقه، آرایه و جابجاییه؛ این نشون می ده فهم الگوریتم مهم تر از اسم زبان برنامه نویسیه.

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

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

def bubble_sort(items):
    n = len(items)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break
    return items

numbers = [5, 1, 4, 2, 8]
print(bubble_sort(numbers))

خروجی [1, 2, 4, 5, 8] هست. به range(n - i - 1) دقت کن؛ این عبارت نمی ذاره هر بار انتهای مرتب شده رو دوباره بررسی کنیم. وقتی جابجایی هم نداشتیم، break باقی دورها رو حذف می کنه. البته این بهینه سازی، بدترین حالت O(n²) رو از بین نمی بره.

توی پایتون لازم نیست برای کار روزمره Bubble Sort بنویسی. وقتی فقط می خوای اطلاعات مرتب بشن، sorted(numbers) یک لیست جدید می سازه و numbers.sort() همون لیست رو تغییر می ده. فرق این دو تا رو بفهم؛ چون توی پروژه واقعی خیلی مهم تر از حفظ کردن یک الگوریتم آموزشی هست.

numbers = [5, 1, 4, 2, 8]
copy_sorted = sorted(numbers)
print(numbers)
print(copy_sorted)
numbers.sort()
print(numbers)

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

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

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

List<int> bubbleSort(List<int> items) {
  final n = items.length;
  for (var i = 0; i < n - 1; i++) {
    var swapped = false;
    for (var j = 0; j < n - i - 1; j++) {
      if (items[j] > items[j + 1]) {
        final temp = items[j];
        items[j] = items[j + 1];
        items[j + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return items;
}

void main() {
  final numbers = <int>[5, 1, 4, 2, 8];
  print(bubbleSort(numbers));
}

در دارت هم خروجی [1, 2, 4, 5, 8] می شه. فقط چون جابجایی چندگانه مثل نمونه پایتون رو به همون شکل نداریم، از متغیر temp استفاده کردیم. برای مرتب سازی واقعی داده ها در یک اپ Flutter معمولا از numbers.sort() استفاده می کنی؛ برای مرتب کردن آبجکت ها هم می تونی مقایسه کننده اختصاصی بدی.

final prices = <int>[500, 200, 800, 400];
prices.sort();
print(prices);

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

مرتب سازی حبابی در روبی

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

def bubble_sort(items)
  n = items.length
  (n - 1).times do |i|
    swapped = false
    (n - i - 1).times do |j|
      if items[j] > items[j + 1]
        items[j], items[j + 1] = items[j + 1], items[j]
        swapped = true
      end
    end
    break unless swapped
  end
  items
end

numbers = [5, 1, 4, 2, 8]
p bubble_sort(numbers)

خروجی روبی هم [1, 2, 4, 5, 8] خواهد بود. توی پروژه واقعی از numbers.sort برای نسخه مرتب شده جدید یا numbers.sort! برای تغییر خود آرایه استفاده می کنی. اگه با این زبان کار می کنی، دوره روبی نابغه ها مثال های بیشتری از آرایه، تست و ساخت برنامه واقعی داره.

مرتب سازی صعودی و نزولی چه فرقی داره؟

تقریبا هر کسی که الگوریتم مرتب سازی حبابی رو یاد می گیره، یه بار می پرسه: «برای مرتب سازی از بزرگ به کوچیک باید کل کد رو عوض کنم؟» نه. برای داده های عددی کافیه شرط مقایسه رو برعکس کنی. شرط items[j] > items[j + 1] یعنی صعودی؛ شرط items[j] < items[j + 1] یعنی نزولی.

def bubble_sort_desc(items):
    for i in range(len(items) - 1):
        swapped = False
        for j in range(len(items) - i - 1):
            if items[j] < items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break
    return items

print(bubble_sort_desc([5, 1, 4, 2, 8]))

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

چطور تک تک دورهای Bubble Sort رو ببینیم؟

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

def show_passes(items):
    values = list(items)
    for i in range(len(values) - 1):
        swapped = False
        for j in range(len(values) - i - 1):
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swapped = True
        print(f"Pass {i + 1}: {values}")
        if not swapped:
            break
    return values

show_passes([5, 1, 4, 2, 8])

این کد باید سه دور نشون بده: اول [1, 4, 2, 5, 8]، بعد [1, 2, 4, 5, 8] و آخر هم همون فهرست مرتب بدون جابجایی. برای درس های الگوریتم، چاپ کردن وضعیت هر Pass از هزار بار خوندن کد خشک مفیدتره.

پیچیدگی زمانی الگوریتم مرتب سازی حبابی

خب، حالا سوال فنی تر: سرعت الگوریتم مرتب سازی حبابی چقدره؟ اینجا با مفهومی به اسم پیچیدگی زمانی یا Time Complexity روبرو می شیم. به جای اندازه گرفتن ثانیه روی یک لپ تاپ خاص، بررسی می کنیم تعداد کارهای الگوریتم با زیاد شدن داده ها چه تغییری می کنه.

مثلا اگه ۱۰۰۰ عدد داشته باشی، تعداد مقایسه ها در حالت بدترین ترتیب می تونه به ۴۹۹٬۵۰۰ برسه. برای ۱۰ هزار عدد این عدد می شه ۴۹٬۹۹۵٬۰۰۰ و برای ۱۰۰ هزار عدد حدود ۵ میلیارد! دقیقا همین رشد مربعی باعث می شه Bubble Sort برای مجموعه داده بزرگ انتخاب خوبی نباشه.

نکته ظریفش اینه که اگه پرچم swapped رو حذف کنی، حتی وقتی لیست از قبل مرتبه هم حلقه ها ادامه پیدا می کنن. پس بهترین حالت O(n) مربوط به نسخه بهینه با توقف زودهنگامه، نه هر نسخه ای که اسم Bubble Sort روش گذاشتیم.

تعداد جابجایی با تعداد مقایسه یکی نیست. الگوریتم ممکنه دو عدد رو بررسی کنه ولی اصلا عوضشون نکنه. برای فهم عملکرد، بهتره این دو معیار رو جدا حساب کنی؛ این دقیقا همون مهارتیه که توی تحلیل کارایی، دیباگ و بعدا طراحی سرویس های سریع به کار میاد.

تعداد مقایسه و جابجایی رو اندازه بگیریم

می خوام از حرف زدن درباره سرعت بیایم سراغ اندازه گیری واقعی. توی کد بعدی تعداد مقایسه ها و جابجایی های مرتب سازی حبابی رو می شماریم. نه ابزار اضافی می خواد و نه به اینترنت نیاز داره. خودت می تونی ورودی رو عوض کنی و ببینی چی می شه.

def bubble_sort_stats(values):
    items = list(values)
    comparisons = 0
    swaps = 0
    for i in range(len(items) - 1):
        swapped = False
        for j in range(len(items) - i - 1):
            comparisons += 1
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return items, comparisons, swaps

print(bubble_sort_stats([5, 1, 4, 2, 8]))

برای همین مثال خروجی ([1, 2, 4, 5, 8], 9, 4) هست؛ یعنی ۹ مقایسه و ۴ جابجایی. حالا ورودی رو [1, 2, 3, 4, 5] بذار: فقط ۴ مقایسه داریم و جابجایی صفره. ورودی برعکس رو هم امتحان کن تا تفاوت رو با چشم ببینی.

آیا Bubble Sort پایدار است؟

یه ویژگی مهم که کمتر توی آموزش های مقدماتی بهش دقت می شه، پایداری یا Stable بودن مرتب سازه. فرض کن دو دانشجو نمره مساوی گرفتن و می خوای بر اساس نمره مرتبشون کنی. اگه الگوریتم پایدار باشه، ترتیب اولیه اون دو دانشجو بعد از مرتب شدن تغییر نمی کنه.

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

students = [(17, "Sara"), (20, "Ali"), (17, "Nima")]
for i in range(len(students) - 1):
    for j in range(len(students) - i - 1):
        if students[j][0] > students[j + 1][0]:
            students[j], students[j + 1] = students[j + 1], students[j]
print(students)

می بینی که هر دو نمره ۱۷ کنار هم قرار می گیرن و ترتیب «سارا» و «نیما» مثل قبل باقی می مونه. این مثال بهت نشون می ده الگوریتم فقط مخصوص اعداد نیست؛ برای داده های ترکیبی هم می شه مبنای مقایسه تعیین کرد.

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

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

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

یه نکته دیگه: همون کد پایتون و دارت و روبی که بالاتر نوشتم، لیست ورودی رو تغییر می ده. اگه داده اولیه رو هم لازم داری، قبل از اجرای الگوریتم ازش کپی بگیر. خیلی از باگ های واقعی پروژه ها نه از منطق مرتب سازی، بلکه از همین اثر جانبی تغییر داده اصلی پیش میاد.

بهینه سازی Bubble Sort چقدر کمک می کنه؟

همین که بعد از هر دور انتهای مرتب شده رو کنار می ذاریم و با swapped زود خارج می شیم، مرتب سازی حبابی بهتر عمل می کنه. اما نباید از این نتیجه بگیریم که «نسخه بهینه» یک دفعه هم رده الگوریتم های سریع برای داده های بزرگ می شه؛ بدترین حالت هنوز O(n²) باقی می مونه.

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

برای شروع پیشنهاد من همون نسخه ساده با پرچم swapped هست. اول منطق رو قورت بده، بعد برو سراغ بهینه سازی. این قانون فقط مال Bubble Sort نیست؛ توی هر پروژه نرم افزاری، «درست کار کردن» قبل از «سریع تر کار کردن» اهمیت داره.

مقایسه Bubble Sort با روش های دیگه

اگه با سرچ «بهترین الگوریتم مرتب سازی» اومدی اینجا، باید یک چیز رو روشن کنیم: هیچ الگوریتمی برای همه شرایط بهترین نیست. Bubble Sort فوق العاده آموزشیه، ولی انتخاب حرفه ای معمولا به حجم داده، مرتب بودن نسبی، حافظه و نوع کلید مقایسه بستگی داره.

مثلا در پایتون تابع sorted و متد list.sort برای مرتب سازی روزمره مناسبن و مرتب سازی پایدار ارائه می کنن. در دارت متد List.sort داری و در روبی هم sort و sort!. یاد گرفتن Bubble Sort برای این نیست که همه اینها رو کنار بذاری؛ برای اینه که بفهمی پشت درخواست ساده «این داده ها رو مرتب کن» چه تصمیم هایی وجود داره.

کجا از مرتب سازی حبابی استفاده می کنیم؟

کاربرد اصلی مرتب سازی حبابی در سال ۲۰۲۶ همچنان آموزش الگوریتم ها، مصاحبه های مقدماتی و تمرین تحلیل کده. وقتی می خوای مفهوم حلقه تو در تو، مقایسه، جابجایی، پیچیدگی زمانی یا Early Exit رو یاد بگیری، مثال خیلی خوبیه. توی سیستم های واقعی با هزاران یا میلیون ها رکورد، معمولا جایگزین های مناسب تری وجود داره.

فرض کن یه فروشگاه اینترنتی ایرانی داری و باید هزاران سفارش رو بر اساس تاریخ یا مبلغ مرتب کنی. شاید فکر کنی چون Bubble Sort رو بلدی، خودت یه تابع براش بنویسی؛ ولی برای چنین کاری بهتره از مرتب سازی دیتابیس یا امکانات آماده زبان استفاده کنی. دانستن الگوریتم بهت کمک می کنه درباره هزینه اجرا سؤال درست بپرسی، نه اینکه حتما همه چیز رو از اول بسازی.

در ساخت اپ با Flutter هم وقتی محصولات رو بر اساس قیمت مرتب می کنی، منطق مقایسه مهمه؛ نه اینکه خودت اصرار داشته باشی Bubble Sort رو داخل UI اجرا کنی. در ابزارهای لینوکسی و امنیتی هم گاهی لازمه خروجی لاگ ها، شدت هشدارها یا نتایج اسکن مجاز رو مرتب کنی. اینجا هم انتخاب الگوریتم و ساختار داده بهتر، از رنگ و لعاب خروجی مهم تره.

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

۵ اشتباه رایج در نوشتن مرتب سازی حبابی

اولین اشتباه اینه که مرز حلقه داخلی رو تا n ببری و بعد به items[j + 1] دسترسی بدی. اون وقت آخر لیست از محدوده خارج می شی. علت وجود n - i - 1 همینه: عنصر سمت راست باید واقعا وجود داشته باشه.

اشتباه دوم اینه که فکر کنی بعد از فقط یک دور همه داده ها مرتب شدن. بعد از یک دور، فقط بزرگ ترین مقدار بخش نامرتب در جای درست قرار می گیره؛ بقیه هنوز ممکنه به هم ریخته باشن.

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

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

چطور کد مرتب سازی حبابی رو تست کنیم؟

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

def bubble_sort(items):
    values = list(items)
    for i in range(len(values) - 1):
        swapped = False
        for j in range(len(values) - i - 1):
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swapped = True
        if not swapped:
            break
    return values

test_cases = [[], [7], [3, 3, 1], [-2, 5, 0], [1, 2, 3], [3, 2, 1]]
for case in test_cases:
    assert bubble_sort(case) == sorted(case)
print("All tests passed")

اگه All tests passed رو دیدی، حداقل این شش حالت درست جواب دادن. البته این به معنی اثبات صد درصد درستی برای تمام ورودی های ممکن نیست؛ فقط یه قدم خیلی خوبه. اگه از این نوع تمرین خوشت اومد، یادگیری تست نویسی در پایتون، دارت یا روبی می تونه مسیر بعدیت باشه.

آیا در مصاحبه برنامه نویسی Bubble Sort می پرسن؟

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

مثلا اگر ازت بپرسن «وقتی ۱۰ برابر داده بیشتر بشه چه اتفاقی برای زمان اجرا می افته؟»، باید بتونی درباره O(n²) حرف بزنی. اگه بپرسن «وقتی لیست از قبل مرتبه چی؟»، باید شرط توقف زودهنگام رو توضیح بدی. و اگه بپرسن «در محصول واقعی از چی استفاده می کنی؟»، پاسخ مناسب اغلب امکانات آماده و تست شده زبان و دیتابیسه.

بعد از این آموزش چی یاد بگیری؟

اگه تازه وارد برنامه نویسی شدی، همین امروز با یکی از سه زبان مثال ها یک لیست رو مرتب کن، حالت نزولی رو اضافه کن و تعداد مقایسه ها رو بشمار. فردا برو سراغ Insertion Sort یا Selection Sort و خروجی هاشون رو با همین ورودی مقایسه کن. این تمرین ها مهارت حل مسئله می سازن؛ چیزی که با حفظ کردن سینتکس به دست نمیاد.

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

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

جمع بندی و ویدیوی مرتبط

اگه فقط یه نکته از این مقاله یادت بمونه، این باشه: الگوریتم مرتب سازی حبابی رو برای یاد گرفتن فکر کردن الگوریتمی بخون، نه برای اینکه از فردا هر پروژه ای دیدی به زور با Bubble Sort مرتبش کنی. الان می دونی چطور جفت های همسایه رو مقایسه کنی، چرا پایان هر دور یک بخش از لیست مرتب می شه و چه زمانی با swapped باید متوقف بشی.

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

اگه دوست داری الگوریتم مرتب سازی حبابی رو به جای خوندن متن، تصویری و قدم به قدم یاد بگیری، ویدیوی پایین رو حتما ببین. توی این ویدیو خودم توضیح دادم که Bubble Sort دقیقا چطوری کار می کنه، عددها چطور با هم مقایسه می شن و چرا بعضی وقت ها باید جاشون رو عوض کنیم. پیشنهاد می کنم بعد از دیدن ویدیو، کدهای پایتون، دارت و روبی که بالاتر گذاشتم رو هم اجرا کنی. حتی می تونی ترتیب عددهای مثال رو تغییر بدی و ببینی الگوریتم چطوری مرتبشون می کنه. اینجوری به جای حفظ کردن چند خط کد، واقعا منطق مرتب سازی حبابی رو یاد می گیری.