تبلیغات


الگوریتم های مرتب سازی: مرتب سازی حبابی (Bubble-sort)

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

 bubble sort

 

در پست قبل مفهومی از مرتب سازی را برای شما گفتیم و یک تابع برای مرتب سازی ارایه دادیم ، در این پست به سراغ مرتب سازی حبابی (bubble sort) می رویم که از معروف ترین الگوریتم های مرتب سازی است .قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:

– مفهوم مرتب سازی

-bubble sort

-insertion sort

-merge sort

quick sort

– Heap sort

-Distribution sorts

– Concurrent sorts

Counting Sort

در این روش مرتب سازی هر عنصر آرایه فقط با عنصر کناری خود مقایسه می شود و اگر عنصر n ام بزرگ تر از عنصر n+1 ام بود جای این دو عنصر عوض می شود این کار تا زمانی که تمام آرایه مرتب شود ادامه می یابد .

اسم این الگوریتم را مرتب سازی حبابی (bubble sort) گذاشته اند  زیرا هر عنصر آرایه فقط با عنصر کناری خو بررسی می شود در تصویر متحرک زیر می توانید آرایه ای را ببینید که با بابل ، سورت می شود :

مرتب سازی حبابی bubble sort

تابع مرتب سازی حبابی (bubble sort) را در زیر می بینید :

 

فرض کنید آرایه ی  ۵ عنصری   ۴ ۱ ۶ ۵ ۸ را دارید و می خواهید آن را با الگوریتم بابل مرتب کنید :

 

۸ ۵ ۶ ۱ ۴

۵ ۸ ۶ ۱ ۴

۵ ۶ ۸ ۱ ۴

۵ ۶ ۱ ۸ ۴

۵ ۶ ۱ ۴ ۸

۵ ۱ ۶ ۴ ۸

۱ ۵ ۶ ۴ ۸

۱ ۵ ۴ ۶ ۸

۱ ۴ ۵ ۶ ۸

 

مرتبه این الگوریتم در بدترین حالت  ( O(n^2  است و  در  بهترین حالت  ( O(n است  به همین خاطر برای سورت کردن تعداد زیادی عنصر مناسب نیست .

در زیر برنامه ای آمده است که در آن تابع مرتب سازی حبابی آمده است که در تابع main  برنامه  آرایه ای به  تابع داده شده تا آن را سورت کند و آرایه را قبل و بعد از مرتب سازی چاپ کند

 

 

 

البته  الگوریتم bubble  رو می شه  جور دیگری پیاده سازی کرد ولی این بهتره.اگر برنامه را طور دیگری نوشته اید یا با زبان  دیگری حتما آن را در نظرات بیان کنید.

 

این هم کد بازگشتی مرتب سازی حبابی که یکی از خوانندگان درخواست کرده بود.


تبلیغات:

۴۴ دیدگاه

  • سلام ببخشید من واقعا کلافه شدم نمیدونم باید چیکار کنم
    من ۵۰۰ عدد تصادفی تولید کردم و در یک فایل ذخیره کردم
    حالا باید اون فایل رو بخونم و اعداد تصادفی که در اون فایل ذخیره شده رو با مرتب سازی حبابی مرتب کنم ولی هرکاری میکنم نمیشه
    لطفا کمک کنین :(((

  • سلام
    برای مرتب کردن آرایه ای از رشته ها باید چی کار کرد؟

    • توی سی پلاس پلاس عمگرهای مقایسه ای شبیه > برای رشته ها هم پیدا سازی شده است ! همون کاری رو که برای مرتب سازی اعداد می کنید برای رشته ها هم می توانید بکنید.

  • سلام.بخشید میشه یه روش بهینه تر بدین که دیگ خونه های سورت شده رو چک نکنه از اول؟
    با تشکر

    • فرهاد دلیرانی

      با مرتب سازی حبابی نمی شه – یعنی اگر تغییرش داد دیگه مرتب سازی حبابی نیست یه چیز دیگش – الگوریتم های سورت دیگر رو باید ببینید .

  • سلام
    استاد ما دربرنامه علاوه برi متغیر j هم تعریف کرده و برحسب هردوش نوشته الان گیج شدم.. یعنی بدون متغیر j هم درسته؟

    • فرهاد دلیرانی

      هر دوش درسته

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

  • سلام میشه نقش flag رو در برنامه توضیح بدید..ممنون میشم

    • فرهاد دلیرانی

      فلگ می گه آرایه سورت شده هست یا نه ، اگر سورت شده باشه دیگه دفعه ی بعد حلقه اجرا نمی شه

      • محمد محمودی

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

  • خیلی عالی بود با تشکر از سایت خوبتون

  • خیلی خوب و مفهومی بود .
    کدها رو خودم نوشتم و کامپایل کردم.
    خسته نباشید .

  • سلام میشه مرتب سازی حبابی رو به تعداد آرایه های ۲۰ عنصری در ++cبرام بنویسد بخدا دعاتون میکنم فقط زود میخوامش مرسی ببخشید

  • سلام. شما پروژه دانشجویی هم درست میکنید؟

  • ممنون از مطالب مفیدتون
    چطور می تونم آرایه دو بعدی رو به روش حبابی مرتب کنم

    • فرهاد دلیرانی

      باهاش مثل یک آرایه ی یک بعدی رفتار کنید ! مثل کد زیر :

  • من به این صورت در سی شارپ این رو پیاده کردم و جواب هم گرفتم ، درک این فکر می کنم ساده تر به حلقه تکرار دوم توجه کنید ، ساده بیان شده (برای ابتدای کار و یادگیری دوستان فکر می کنم جالب باشه)

    int[] a = new int[3];
    int temp;
    a[0] = 9;
    a[1] = 5;
    a[2] = 15;

    for (int i = 0; i < 3; i++)
    {
    for (int j = 0; j < 2; j++)
    {
    if (a[j]<a[j+1])
    {
    temp = a[j];
    a[j] = a[j + 1];
    a[j + 1] = temp;
    }
    }
    }

    string s = "";
    for (int i = 0; i < 3; i++)
    {
    s += a[i].ToString() + ",";
    }
    this.Text = s.Substring(0, s.Length - 1);
    // ۱۵,۹,۵

  • فلوچارت های این برنامه ها چطوریه

  • سلام
    ممنون من نتونستم به طور کامل مفهوم while (منظورم دقیقا کارش چیه) در مثال متوجه بشم می دونم اگه نباشه به طور کامل مرتب نمیکنه .
    اگه امکان داشته باشه بیشتر توضیح بدین.

    • حلقه while برای اینکه این روند sort تا زمان مرتب شدن کل اعدادمون ادامه میده و قطع نمیشه برای همین کل برنامه که می نویسیم را در حلقه می ذاریم اگه نذاریم باید روی دکمه ای برایش کد sort را تعریف کردیم مدام بزنیم دونه دونه مرتب شه اما با گذاشتن حلقه با یک بار زدن این کار انجام می شود .

  • سلام میخواستم بدونم این سورت حبابی رو میشه برای رشته ها هم نوشت؟؟؟؟؟؟؟؟؟؟؟

    • فرهاد دلیرانی

      آره ، معیار اون مقایسه ی دو رشتتون حرف اولشون باشه ولی اگر حرف اولشون برابر بود حرف دومشون رو مقایسه کنید ، اگر حرف دومشون برابر بود حرف سومشون رو مقایسه کنید وهمین طور تا آخر!

    • بله میشه! چون کاراکترهای رشته ها هم قابل مقایسه با همدیگر هستند.

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

  • من میخاستم یه شمارنده تو برنامم بزارم تا بفهمم مثلا برای مرتب کردن ۵ تا عدد این دستور العمل ها ۷۰ بار تکرار میشه تا با این طریق بتونم آزمایش کنم ک هر الگوریتم برای چه جور داده و چه تعداد داده بهترین کارایی رو داره ولی نمیدونم چه جوری این شمارنده را در برنامم قرار بدم ؟؟؟؟؟؟ممنون میشم کمکم کنید

    • با فرض recursive بودن برنامه ی شما، میتونید از یک متغیر global یا از پاس کردن یک متغیر به صورت reference به هر از سطح از برنامه برای شمارش استفاده کنید. عمل افزایش شمارنده رو در بعد از شرط خاتمه انجام بدید چرا که در آخرین عمق و با ارضای شرط خاتمه، شما به عمق جدیدی وارد نمیشید و شمارش لازم نیست.
      اما با فرض iterative بودن برنامه ی شما، با استفاده از یک متغیر local در ابتدای دستورات اولین حلقه عمل افزایش شمارنده رو انجام بدید.

  • سلام
    من یک سوال دارم که نتونستم درست به جواب برسم.
    میخوام مرتب سازی حبابی رو به روش بازگشتی پیاده سازی کنم.
    اگه میشه کمک کنید.
    ممنون

  • عالی بود

  • سلام .
    لطفا کمکم کنید من می خوام یه برنامه بنویسم که ده تا اسم از کاربر بگیره اونا رو به ترتیب حروف الفبا مرتب کنه میشه بگید چه طور از بابل سورت برای این کار میشه استفاده کرد

    • فرهاد دلیرانی

      شما باید آرایه ای از رشته ها رو به تابع بفرستید و سمت چپ ترین حرف آن ها را از نظر بزرگی کد اسکی بررسی کنید و اگر برابر بودند حرف بعدی آن ها را مقایسه کنید.

نظر خود را بنویسید.

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *