bubble sort

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

 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  رو می شه  جور دیگری پیاده سازی کرد ولی این بهتره.اگر برنامه را طور دیگری نوشته اید یا با زبان  دیگری حتما آن را در نظرات بیان کنید.

 

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

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۶۲ دیدگاه

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

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

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

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

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

  • سلام
    استاد ما دربرنامه علاوه بر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 را تعریف کردیم مدام بزنیم دونه دونه مرتب شه اما با گذاشتن حلقه با یک بار زدن این کار انجام می شود .

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

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

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

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

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

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

    • بله میشه استفاده کرد
      البته جزئیات استفاده که پاس کردن اجزای مورد نظر بعد دلخواهتون هست مربوط به پیاده سازی میشه نه الگوریتم

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

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

  • سلام

    توی این جمله :
    مرتبه این الگوریتم در بدترین حالت ( O(n^2 است

    منظورتون از O و n رو می شه بگید ؟

    ممنون

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

      یک جورایی هزینه ی الگوریتم ، n تعداد اعضای آرایه است ، که می گه هر چه n زیاد می شود زمانی که الگوریتم می گیرد به صورت تصاعدی نسبت به n زیاد می شود

  • سلام من میخوام آرایه ای بنویسم به طول ۵که اونو سورت کنم و درrichtextbox قرار بدم لطفا کمکم کنید

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

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

  • سلام
    من درس ساختمان داده رو برداشتم اما برنامه نویسی پیشرفته رو تا حالا برنداشتم و رشته ام آی تی هستش و برای آی تی ها پیشرفته پیش نیاز ساختمان داده نیست میخواستم بدونم ساختمان داده به پیشرفته خیلی بستگی داره؟؟

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

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

  • flag = 0
    برای برنامه ای به کار میاد که بخواد N بار تکرار بشه! درسته؟

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

      نه برای اون نیست که برنامه n بار اجرا بشه! ممکنه همون دفعه اول خود آرایه مرتب باشه یا بعد از دوبار اجرای حلقه آرایه رتب بشه در نتیجه الزامی نیست حتمی n بار اجرا بشه

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

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

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

  • همین برنامه رو نوشتم مشکل داره اصل برنامه رو واست میل کردم اگه میشه مشکلشو بگی

  • سلام خسته نباشید یک سوال داشتم :

    چرا توی حلقه ی (while(flag==1

    بعدش flag=0 ????

    motevajeh nmisham in ghesmato :((

  • با عرض خسته نباشید!
    سوال:الگوریتم مرتب سازی Group sort وجود داره?
    اگه وجود داره لطفا توضیح بدید.

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

    I was very happy for the comment. I will continue with more power.

  • لطفا هیپ سورت هم بگذارید

  • Pingback: open-mind » الگوریتم های مرتب سازی : مفهوم مرتب سازی

    • سلام الگوریتم کی می تونه کمکم کنه امتحان دارم ۲۷ممنون میشم

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

        تو این مدت نمی تونی کتاب خیلی خوبی رو بخونی و نتیجه بگیری ولی یک کتاب هست به اسم: “طراحی الگوریتم ها” نویسندگان “نیپولیتان-نعیمی پور” ترجمه “مهندس جعفر نژاد قمی”
        که می تونی برای امتحان مباحثی که استاد درس داره از روش بخونی
        البته ترجمه کتاب مقدمه ای بر الگوریتم ها معروف به “CLRS” هم تازه اومده اگر اینو بخونی بهتر البته اگه پیداش کنی

پاسخ دهید

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