ساختمان داده ها در جاوا ::: آموزش الگوریتم Bubble sort یا مرتب سازی حبابی

سايت مرجع زبان برنامه نويسي جاوا                                                       Java.TadbirPoya.ir> Articles> Data Structure> Bubble Sort

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

 

 

تکنولوژيهای جاوا
Java SE
Java EE
Java ME
JasperReports

 

لينك هاي مفيد
تدبيرگران پوياپرداز
دانلود هاي جاوا
آموزش جاوا
بازگشت
خانه

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 شماره مقاله  :   58

      تاريخ ايجاد :      1388/12/25

        تاريخ ويرايش :   1388/12/25

        دفعات بروز رساني :    0 

  نويسنده :        ----

 

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

please wait

شما در حال انتقال به صفحه جدید ما می باشید. لطفا چند لحظه صبر نمایید



 

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

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

برای مشاهده تصویر در ابعاد بزرگتر، روی آن کلیک کنید

 

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

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

W.C :  o(n2)

AVG.C: o(n2)

B.C: o(n)

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

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

برای مشاهده تصویر در ابعاد بزرگتر، روی آن کلیک کنید

 

 

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

 

دانلود برنامه هاي مورد استفاده در اين مقاله

مطالب موجود در اين سايت به جهت ارتقاء سطح علمي برنامه نويسان جاوا تهيه و تنظيم شده است. در صورت تمايل مي توانيد مطالب خود را در جهت اصلاح يا ارتقاء مقالات موجود و يا ايجاد مقالات جديد به آدرس ايميل زير ارسال نماييد.

 JArticles@TadbirPoya.ir

استفاده از مطالب موجود در سايت با ذكر منبع بلامانع است.

Copyright @2008-2009 TadbirPoya.ir Co.All rights reserved