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

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

مقدمه : الگوریتم مرتب سازی حبابی

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

تا حالا شده که یه عالمه عدد رو بخوای مرتب کنی اما ندونی از کجا شروع کنی؟ خب، یه راه حل ساده و ابتدایی وجود داره که بهش میگن “الگوریتم مرتب سازی حبابی” یا به انگلیسی “Bubble Sort“. این روش مثل حباب‌هایی که توی آب از پایین به بالا میان، داده‌ها رو یکی یکی مرتب می‌کنه و در نهایت به یه لیست مرتب می‌رسی.

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

آموزش پایتـون : دوره‌ی آموزش پایتون بهترین انتخاب برای دانشجویان مبتدی در برنامه‌نویسی است، زیرا پای...

مشاهده دوره

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

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

الگوریتم مرتب سازی حبابی یا Bubble Sort یکی از ساده‌ترین روش‌های مرتب‌سازی داده‌هاست. اگه یه لیست از اعداد داشته باشیم، این الگوریتم میاد و اعداد رو دو به دو با هم مقایسه می‌کنه و اگه لازم باشه، جاشون رو عوض می‌کنه. این کار رو انقدر ادامه میده تا لیست به طور کامل مرتب بشه.

حالا فرض کن یه لیست از اعداد مثل این داریم:

[5, 3, 8, 4, 6]

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

مرحله به مرحله با مرتب سازی حبابی

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

[5, 1, 4, 2, 8]

مرحله 1: مقایسه‌ی عدد اول و دوم
ابتدا عدد اول و دوم رو با هم مقایسه می‌کنیم. تو اینجا 5 رو با 1 مقایسه می‌کنیم. چون 1 کوچیکتره، جاشون رو عوض می‌کنیم:

[1, 5, 4, 2, 8]

مرحله 2: مقایسه‌ی عدد دوم و سوم
حالا میریم سراغ عدد دوم و سوم. 5 رو با 4 مقایسه می‌کنیم. چون 4 کوچیکتره، باز هم جابجایی انجام می‌دیم:

[1, 4, 5, 2, 8]

مرحله 3: مقایسه‌ی عدد سوم و چهارم
حالا 5 و 2 رو مقایسه می‌کنیم. چون 2 کوچیکتره، باز هم جابجایی داریم:

[1, 4, 2, 5, 8]

مرحله 4: مقایسه‌ی عدد چهارم و پنجم
در نهایت، 5 و 8 رو مقایسه می‌کنیم. چون 5 از 8 کوچیکتره، دیگه جابجایی نداریم. پس تو این مرحله چیزی تغییر نمی‌کنه تا اینجا، بزرگترین عدد یعنی 8 به جایگاه درست خودش رفته (مثل یه حباب که به بالای آب میاد). اینجا یه نکته مهمه: بعد از هر دور مقایسه، می‌تونیم مطمئن بشیم که بزرگترین عدد در جای درست خودش قرار گرفته.

حالا این مراحل رو دوباره برای باقی عددها تکرار می‌کنیم. هر بار این کار رو انقدر انجام می‌دیم تا کل لیست مرتب بشه.

مرحله دوم مرتب سازی حبابی: لیست جدیدمون اینه:

[1, 4, 2, 5, 8]

دوباره از اول شروع می‌کنیم. این بار عدد 1 با 4 مقایسه می‌شه که نیازی به جابجایی نداره. ولی وقتی 4 و 2 رو مقایسه می‌کنیم، چون 2 کوچیکتره، جابجایی داریم:

[1, 2, 4, 5, 8]

الان تقریباً لیستمون مرتب شده. باز هم بزرگترین عدد توی آخرین جایگاهه.

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

[1, 2, 4, 5, 8]

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

دو مثال ساده از پیاده‌سازی الگوریتم مرتب سازی حبابی (Bubble Sort) با استفاده از زبان‌های برنامه‌نویسی پایتون و دارت آورده‌ام :

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

مقدمه زبان برنامه نویسی دارت در سال‌های اخیر رشد آهسته و پیوسته‌ای داشته؛ به همین خاطر این روزها این...

مشاهده دوره

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

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

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

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

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

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');
  
}

توضیح :
در دارت هم مثل پایتون، از دو حلقه تو در تو استفاده می‌کنیم. اولین حلقه برای تکرار کل لیست و دومین حلقه برای مقایسه و جابجایی عناصر مجاور در صورت عدم جابجایی، الگوریتم زودتر متوقف می‌شه.
هر دوی این مثال‌ها الگوریتم Bubble Sort رو به شکلی ساده پیاده‌سازی می‌کنند و می‌تونن به راحتی در پروژه‌ها استفاده بشن.

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

خب، حالا که با مراحل کار آشنا شدیم، بیایم ببینیم این روش چه مزایا و معایبی داره.

مزایا:

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

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

مناسب برای لیست‌های کوچک: اگه تعداد داده‌ها خیلی کم باشه، این الگوریتم می‌تونه به خوبی کار کنه. چون سادگی‌اش باعث می‌شه برای لیست‌های کوچک سریع و موثر باشه.

معایب:

کارایی پایین: الگوریتم Bubble Sort وقتی که لیست خیلی بزرگی داشته باشی، کارایی خوبی نداره. چون باید همه‌ی عددها رو بارها و بارها مقایسه کنه. این یعنی زمان اجرای اون توی بدترین حالت برابر با O(n2) هست که باعث می‌شه برای لیست‌های بزرگ مناسب نباشه.

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

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

بهینه‌سازی مرتب سازی حبابی

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

این تغییر کوچیک باعث می‌شه که مرتب سازی حبابی کمی کاراتر بشه، به خصوص وقتی که لیست تقریباً مرتب باشه.

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

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

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

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

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

آموزش لینوکس اِسِنشیالز

آموزش لینوکس 0 تا 100 که در یک دهه اخیر که دنیای فناوری به طرز شگفت‌آوری پیشرفت کرده است، هر کسی که ...

مشاهده دوره

نتیجه‌گیری

در نهایت، مرتب سازی حبابی (Bubble Sort) یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی هست که به سادگی می‌تونی اون رو درک و پیاده‌سازی کنی. هرچند این الگوریتم برای داده‌های بزرگ کارایی مناسبی نداره، اما برای یادگیری مفاهیم اولیه مرتب‌سازی و پیاده‌سازی الگوریتم‌ها، یه ابزار عالیه. با وجود معایبش، مرتب سازی حبابی همچنان یکی از پایه‌های مهم در دنیای الگوریتم‌هاست.

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

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

راستی، یادتون نره که حتماً پیج “نابغه‌ها” رو توی یوتیوب، اینستاگرام و بقیه شبکه‌های اجتماعی دنبال کنید تا اولین نفرایی باشید که از آموزش‌های جدید باخبر می‌شید! 🔔