الگوریتم مرتب سازی حبابی (Bubble Sort)

[Sarp]

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

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


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

W.C : o(n2)​

AVG.C: o(n2)​

B.C: o​

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


​

public class bubbleSort{
		  public static void main(String a[]){
		    int i;
		    int array[] = {12,9,4,99,120,1,3,10};
		    System.out.println("Values Before the sort:\n");
		    for(i = 0; i < array.length; i++)
		      System.out.print( array[i]+"  ");
		    System.out.println();
		    bubble_srt(array, array.length);
		    System.out.print("Values after the sort:\n");
		    for(i = 0; i <array.length; i++)
		      System.out.print(array[i]+"  ");
		    System.out.println();
		    System.out.println("PAUSE");
		  }
		
		  public static void bubble_srt( int a[], int n ){
		    int i, j,t=0;
		    for(i = 0; i < n; i++){
		      for(j = 1; j < (n-i); j++){
		        if(a[j-1] > a[j]){
		          t = a[j-1];
		          a[j-1]=a[j];
		          a[j]=t;
		        }
		      }
		    }
		  }
		}

​