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

تحلیل عملکرد و پیاده‌سازی با زبان‌های برنامه‌نویسی ++C و Python

✤    ۲۰ شهریور ۱۳۸۵ - آخرین به‌روزرسانی: ۵ فروردین ۱۳۹۹

یکی از روش‌های مرتب‌سازی، روش مرتب‌سازی حبابی (Bubble Sort) است که به آن روش تعویض استاندارد (Standard Exchange) نیز می‌گویند. این روش شامل چند مرحله است که در هر مرحله یک عنصر از لیست به طور قطع در محل مناسب خود قرار می‌گیرد.

لیست زیر را در نظر بگیرید که می‌خواهیم به صورت صعودی (از کوچک به بزرگ) مرتب کنیم:

  

4  3  8  1  6  2

  

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

  

1 - 1)    4  3  8  1  6  2    →    3  4  8  1  6  2

  

همین کار را با عناصر دوم و سوم انجام می‌دهیم:

  

1 - 2)    3  4  8  1  6  2    →    3  4  8  1  6  2

  

و همینطور عناصر سوم و چهارم:

  

1 - 3)    3  4  8  1  6  2    →    3  4  1  8  6  2

  

و الی آخر:

  

1 - 4)    3  4  1  8  6  2    →    3  4  1  6  8  2

1 - 5)    3  4  1  6  8  2    →    3  4  1  6  2  8

  

زمانی که به انتهای لیست رسیدیم، بزرگترین عنصر بین داده‌ها به انتهای لیست منتقل شده است.

در مرحله بعد، مجددا از ابتدا شروع کرده و تا انتها ادامه می‌دهیم. اما با توجه به این که به طور قطع عنصر nام در جای اصلی خود قرار دارد، تا عنصر (n - 1)ام پیش می‌رویم. در پایان این مرحله، بزرگترین عدد در لیست نامرتب باقیمانده، به انتهای آن منتقل می‌شود که دومین عدد از نظر بزرگی در کل لیست است:

  

2 - 1)    3  4  1  6  2  8    →    3  4  1  6  2  8

2 - 2)    3  4  1  6  2  8    →    3  1  4  6  2  8

2 - 3)    3  1  4  6  2  8    →    3  1  4  6  2  8

2 - 4)    3  1  4  6  2  8    →    3  1  4  2  6  8

  

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

  

3 - 1)    3  1  4  2  6  8    →    1  3  4  2  6  8

3 - 2)    1  3  4  2  6  8    →    1  3  4  2  6  8

3 - 3)    1  3  4  2  6  8    →    1  3  2  4  6  8

  

4 - 1)    1  3  2  4  6  8    →    1  3  2  4  6  8

4 - 2)    1  3  2  4  6  8    →    1  2  3  4  6  8

  

5 - 1)    1  2  3  4  6  8    →    1  2  3  4  6  8

  [برگرد بالا]

  [برگرد بالا]

  

در پایان این مراحل، لیست مرتب شده است.

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

  

پیاده‌سازی مرتب‌سازی حبابی

  [برگرد بالا]

این الگوریتم را به زبان برنامه‌نویسی ++C - برای آرایه‌ای از اعداد صحیح - می‌توان به صورت زیر پیاده‌سازی کرد:

  

void bubble_sort_1(int arr[], int n){

  int i, j, t;

  for(i = n - 2 ; i >= 0 ; i--)

    for(j = 0 ; j <= i ; j++)

      if(arr[j] > arr[j + 1]){

        t = arr[j];

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

        arr[j + 1] = t;

      }

}

  

پیاده‌سازی مرتب‌سازی حبابی در زبان برنامه‌نویسی Python نیز به صورت زیر است. متغیر arr در این تابع می‌تواند از هر نوع شیء باشد که عملگر بزرگتر برای آن تعریف شده است.

  

def bubble_sort_1(arr):

    for i in range(len(arr) - 2, -1, -1):

         for j in range(i + 1):

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

                 arr[j], arr[j + 1] = arr[j + 1], arr[j]

  

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

  

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

  [برگرد بالا]

فرض کنیم لیستی با n عنصر با روش مرتب‌سازی حبابی مرتب می‌شوند. عمل اصلی روش‌های مرتب‌سازی مبتنی بر مقایسه، مقایسه‌ها هستند. در مرحله اول، n - 1 مقایسه صورت می‌گیرد، تا بزرگترین عنصر به انتهای لیست منتقل شود. در مرحله دوم، n - 2 مقایسه و به همین ترتیب، در مرحله iام (i < n) تعداد n - i مقایسه صورت می‌گیرد. این تعداد را می‌توان از کد برنامه‌نویسی ذکر شده فوق هم استخراج کرد. پس تعداد کل مقایسه‌ها برای مرتب کردن n عنصر برابر است با:

  

\[ T(n) = (n - 1) + (n - 2) + (n - 3) + \cdots + 2 + 1 = \frac{ n (n - 1)}{ 2 } \]

  

چنین عبارتی از مرتبه $\theta(n^2)$ است.

  

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

  [برگرد بالا]

قطعه کد فوق برای تمامی حالات چینش عناصر لیست به یک ترتیب عمل می‌کند. یعنی حتی اگر عناصر از قبل مرتب باشند، تمامی مقایسه‌ها - بدون جابجا شدن عنصری - انجام می‌شود. قطعه کد فوق در بهترین حالت، بدترین حالت و حالت متوسط از مرتبه $\theta(n^2)$ خواهد بود.

برای بهینه‌تر شدن الگوریتم، کدها را به صورت زیر تغییر می‌دهیم:

  

void bubble_sort_2(int arr[], int n){

  int i, j, t, c;

  for(i = n - 2 ; i >= 0 ; i--){

    hasChange = 0;

    for(j = 0 ; j <= i ; j++)

      if(arr[j] > arr[j + 1]){

        t = arr[j];

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

        arr[j + 1] = t;

        hasChange = 1;

      }

    if(hasChange == 0)

      break;

  }

}

  

def bubble_sort_2(arr):

    for i in range(len(arr) - 2, -1, -1):

        hasChange = False

        for j in range(i + 1):

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

                arr[j], arr[j + 1] = arr[j + 1], arr[j]

                hasChange = True

        if not hasChange:

            break

  

مقدار متغیر hasChange قبل از شروع هر مرحله صفر شده و در صورت جابجا شدن محتوای دو خانه از آرایه مقدار آن به یک تغییر پیدا می‌کند. بنابراین، اگر مقدار آن در پایان مرحله صفر باشد، یعنی هیچگونه جابجایی در لیست صورت نگرفته و می‌توان نتیجه گرفت لیست مرتب است (چرا؟).

چنین کدی مرتبه زمانی اجرای الگوریتم را در بهترین حالت به $\theta(n)$ تقلیل می‌دهد. چرا که اگر لیست از همان ابتدا مرتب باشد، با تمام شدن اولین مرحله (با n - 1 مقایسه) و بررسی مقدار متغیر c، مرتب بودن لیست مشخص شده و ادامه روند مرتب‌سازی متوقف می‌شود.

  

ویژگی‌های مرتب‌سازی حبابی

  [برگرد بالا]

1- همانگونه که بحث شد، پیچیدگی زمانی اجرای این الگوریتم در بدترین حالت و حالت متوسط از مرتبه $\theta(n^2)$ است. پیچیدگی زمانی بهترین حالت، با تابع bubble_sort_1 از مرتبه $\theta(n^2)$ و با تابع bubble_sort_2 از مرتبه $\theta(n)$ است.

2- مرتب‌سازی حبابی یک روش مرتب‌سازی درجا است. یعنی نیاز به فضای کمکی نداشته و با جابجا کردن عناصر در داخل خود لیست، آنها را مرتب می‌کند.

3- مرتب‌سازی حبابی - با پیاده‌سازی به یکی از روش‌های فوق - یک روش مرتب‌سازی پایدار است. یعنی در حین مرتب‌سازی ترتیب عناصری که مقدار یکسانی دارند تغییر نمی‌کند. اگر در قطعه کدهای فوق، در مقایسه عناصر آرایه به جای < از =< استفاده می‌کردیم، مرتب‌سازی ناپایدار می‌شد. چرا که عناصری با مقادیر یکسان را نیز جابجا کرده و ترتیب آنها را به هم می‌زد.


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

تا کنون ۱۱۷ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

amasoudfam.ir/l/443lw

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram

نام: *  
پست الکترونیک (محرمانه):
پیام: *  
• bluegirl
۱ فروردین ۱۳۸۶، ساعت ۰۸:۵۸

سلام سایتتون عالیه...خسته نباشید...لطفا heap رو هم بدارید

• www.tameshk51@yahoo.com
۲۴ مهر ۱۳۸۶، ساعت ۲۰:۱۵

دمت گرم

• کاوه
۷ آذر ۱۳۸۶، ساعت ۰۱:۰۴

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

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

با تشکر

• نگار
۱۵ آذر ۱۳۸۶، ساعت ۰۱:۰۶

سلام

ميشه لطف كنيد فرق بين مرتب سازي ادغامي و مرتب سازي  سريع و مرتب سازي حبابي رو توضيح بدين

با تشكر

• alireza
۲۱ اسفند ۱۳۸۶، ساعت ۱۵:۴۰

salam

be in khaater be aan raveshe moratab saazi hobaabi migooyand ke hobaab be dalile in ke hobaab chon

chegaalish bishtar az aab hast be samte sathe aab miaayad va chon koochak ast hamishe aval gharaar migirad.

rassti agar mishe dar sitetun flow chart in ravesh raa ham begozaarid ba zekre mesaal.

• مينا
۲۲ اردیبهشت ۱۳۸۸، ساعت ۲۳:۰۰

سلام

اگه امكانش هست برنامه مرتب سازي ادغامي و مرتب سازي سريع رو برام ايميل كن فقط اگه لطفت شامل

حال من شد برنامه كاملشو ميخوام  به هر زبان برنامه نويسي كه باشه چون ميخوام با ويژوال بيسيك بنويسم

هر چند كه هيچ اميدي ندارم احتمال شما هم مثل ديگران كمكي به من نمي كنيد ولي بازم ممنون !!!

مسعود اقدسی‌فام
۲۳ اردیبهشت ۱۳۸۸، ساعت ۰۷:۵۱

سلام مینا خانم

قبل از ارسال پیام نکاتی رو که تذکر داده شده مطالعه کردید؟ ما نه برنامه آماده داریم و نه به ایمیل کسی ارسال می کنیم.

موفق باشید.

• saeid
۱۶ اردیبهشت ۱۳۹۰، ساعت ۱۳:۰۸

مطالب بیشتری در مورد مرتب سازی ها در سایت قرار دهید

با تشکر از زحمات گرانقدرتان.

• ارزو
۲۶ مهر ۱۳۹۰، ساعت ۱۲:۴۴

سلام خسته نباشید

عالـــــــــــــــــــــــــــــــــــــــــــــــــی بود0606060606060606060606060606060606

• hasty``
۱۲ دی ۱۳۹۰، ساعت ۱۶:۵۸

04 kheili khob bood merc

• أأ
۲۴ دی ۱۳۹۰، ساعت ۲۰:۵۰

010101

• haji
۳۰ بهمن ۱۳۹۰، ساعت ۰۸:۴۴

متـــــــــــــــــــــــــــــــشکرم06

• بنده ی خدا
۱۳ اسفند ۱۳۹۰، ساعت ۱۷:۳۲

با تشکر بسیار.

فقط ان منهای یک باید باشه

• محسن
۲۴ خرداد ۱۳۹۱، ساعت ۱۰:۴۹

عالی بود. 3 نمره کمکم کردید.مرسی

• jetboy
۱۸ آبان ۱۳۹۱، ساعت ۱۸:۴۴

سلام :

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

دستتــــــــــــــــــــــــــــــــــون درد نکنــــــــــــــــــــــــــــــــــــــــــــــــه

121212121208080606

• asma
۱۹ آبان ۱۳۹۱، ساعت ۱۴:۱۸

س . کمک. یک ماتریس10*10که از روش مرتب سازی ادغامی وحبابی استفاده کند برام میل کنید خیلی مهمه

۱۹ آبان ۱۳۹۱، ساعت ۱۵:۰۶
• مسعود اقدسی‌فام

اسما خانم

شما دو بار درخواست برنامه آماده با ذکر آدرس ایمیل و درخواست برای ارسال به ایمیل کردید. بدون اینکه یکبار تذکرات بخش قرمز رنگ بالای قسمت ارسال پیام رو بخونید یا بهشون اهمیت بدید.

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

موفق باشید.

• zainab
۲۲ آذر ۱۳۹۲، ساعت ۱۸:۴۶

عالی بود very much

جای مطالب بیشتر خیلی  خیلی  خالی

• مهسا
۱۹ فروردین ۱۳۹۳، ساعت ۱۳:۵۶

خوب بود و البته خلاصه و مفید .ممنون01

• ماندانا
۲۲ فروردین ۱۳۹۳، ساعت ۱۲:۴۱

سلام.من یه سوال برنامه نویسی c++دارم.کسی هست بلد باشه؟

دیوونه شدم از دستش

07

• محمد حسین از شهرستان جیرفت
۱۳ آبان ۱۳۹۳، ساعت ۱۴:۰۹

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

  for(j=s-1;j>=1;j--)                              

   for(i=1;i<=j;i++)

     if(a[i]>a[i+1])

     {

       jabeja=a[i];

       a[i]=a[i+1];

       a[i+1]=jabeja;

      }

متغیر ها فرقی نمیکنه که چی باشن من اینجوری تعریفشون کردم

نکته:(s-2)برنامه قبل شده (s-1)

۱۳ آبان ۱۳۹۳، ساعت ۲۳:۳۹
• مسعود اقدسی‌فام

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

این کد که شما ارسال کردید اگه j تا s-1 بره (که s رو تعداد عناصر آرایه در نظر می‌گیریم)[a[i+1 می‌تونه تا [a[s پیش بره، که این عنصر جزو عناصر مورد نظر ما نیست. در کل چنین تغییری تاثیری در پایداری یا ناپایداری الگوریتم مرتب‌سازی نداره.

•  sepideh bandari
۲۵ آبان ۱۳۹۳، ساعت ۱۸:۱۰

06060606060606

عالی بود مسی

• محمدحیدری
۱۵ آذر ۱۳۹۳، ساعت ۲۱:۱۶

خیلی ممنون از اینکه کامل و جامع توضیح داد 01

• ali zamani
۱۶ آذر ۱۳۹۳، ساعت ۲۳:۵۸

برنامه عالیه ولی یه مشکلی داره

تو حلفه :

  (-- for( i = n - 2 ; i >= 0 ; i

باید بشه

(-- for( i = n - 1 ; i >= 0 ; i

لطفا تصحیح کنید

۱۷ آذر ۱۳۹۳، ساعت ۲۳:۲۶
• مسعود اقدسی‌فام

ممنون از توجهتون. اما اگه دقت کنید، مقدار j از 0 تا i تغییر می‌کنه و هر مرحله عنصر j با j+1 مقایسه می‌شه. پس j+1 باید کمتر یا مساوی n - 1 باشه که نتیجه می‌ده i می‌تونه حداکثر n - 2 بشه.

برای i = n-1 مقایسه‌ی [a[n-1] > a[n در آخرین تکرار اتفاق می‌افته که مجاز نیست. چون عناصر از اندیس 0 تا n - 1 قرار دارن.

• آرمین
۱۸ دی ۱۳۹۳، ساعت ۱۲:۱۸

for اول باید از n-1 شروع شه!!!

• آرمین
۱۸ دی ۱۳۹۳، ساعت ۱۲:۳۳

الان ک فک میکنم میبینم n-2 درسته 10

• یاسمین
۲۱ فروردین ۱۳۹۴، ساعت ۲۱:۵۰

سلام .مرتبه ی زمانی یک ماتریس n*nکه به صورت صعودی مرتب شده رو میخوام .لطفا امشب جواب بدید فردا باید تحویل استاد بدم.

• پارسا
۱۸ اردیبهشت ۱۳۹۴، ساعت ۱۳:۰۳

سلام ممنون از توضیحات خوبتون .من چند تا سوال درباره این برنامه داشتم ممنون میشم اگه جواب بدین

شما تو حلقه ی for از n - 2 استفاده کردین چرا این دستور رادر  i-- اعمال نکردین؟مثلا چرا ننوشتین 2- i=i

و اگه بخوایم این برنامه رو برای ارایه ی 20عنصری انجام بدیم همین ساختار رو حفظ میکنه ؟

۱۹ اردیبهشت ۱۳۹۴، ساعت ۱۲:۱۹
• مسعود اقدسی‌فام

بر اساس ساختار حلقه‌ی تکرار for، در زمان ورود به حلقه تنها مقداردهی اولیه (یعنی n - 2) و شرط تکرار حلقه (یعنی  0 >= i) اجرا می‌شه و بخش --i نقشی نداره. در تکرارهای بعدی هم اگه i = i - 2 باشه عملکرد الگوریتم به هم می‌خوره. چون هر بار دو واحد از i کم می‌شه که مورد نظر ما نیست.

برای مطالعه‌ی توضیحات بیشتر راجع به حلقه‌های تکرار این لینک رو ببینید:

http://www.algorithmha.ir/category-برنامه-نویسی-سی-پلاس-پلاس/post-حلقه-های-تکرار-در-سی-پلاس-پلاس/

• popo
۷ خرداد ۱۳۹۵، ساعت ۱۱:۲۴

سلام

میگم اگر بخواییم با سرچ باینری یکی از اطلاعات ارایه پیدا کنیم چجوری میشه؟

• بافهم
۲۳ فروردین ۱۳۹۶، ساعت ۰۸:۳۳

خیلی پرنده و نافهم بود09090909

بی فهم090909090909

• امین
۳۰ اردیبهشت ۱۳۹۶، ساعت ۱۴:۴۹

مرسی

• مریم
۳۱ اردیبهشت ۱۳۹۶، ساعت ۱۷:۲۲

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

• فهیمه
۲۱ آذر ۱۳۹۶، ساعت ۲۰:۳۶

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

• میثم
۹ دی ۱۳۹۶، ساعت ۰۹:۵۱

برنامه ای بنویسید که ماتریس 6در 5 را دریافت کرده و عناصر ان را بنویسید ؟

• مهدى
۹ دی ۱۳۹۶، ساعت ۱۴:۲۷

سلام، مرتب سازى حبايى در ساختمان هم قابل استفادست  ؟ و چاپش هم مانند چاپ  اون تو ارايه ست يا فرق ميكنه؟

تشكر.

• مهدى
۹ دی ۱۳۹۶، ساعت ۱۴:۴۱

و يه چيز ديگه

اگه در ساختمان از هر عدد دو تا باشه تو مرتب سازى و دادن اونا به يه ارايه ى  اون دو عدد يكى حساب ميشن يا دو عدد جدا؟

• زهرا
۱۶ اردیبهشت ۱۳۹۷، ساعت ۱۹:۵۹

سلام لطفا برنامه یک ارایه 10 عنصری که ان را به روش الگوریتم مرتب سازی حبابی مرتب کند رو میگذارین

• آموزش وردپرس رایگان
۸ اردیبهشت ۱۳۹۸، ساعت ۲۱:۳۶

بسیار عالی واقعا راحت و قبل فهم توضیح دادید.13

• فرزانه
۱۳ آبان ۱۳۹۹، ساعت ۱۳:۴۰

ممنون استاد

• Mojtaba
۵ دی ۱۳۹۹، ساعت ۲۰:۳۶

12121212