Posted by: lrrp | February 7, 2015

Write a method to sort numbers in an array ?

In the bubble sort, as elements are sorted they gradually “bubble” (or rise) to their proper location in the array, like bubbles rising in a glass of soda. The bubble sort repeatedly compares adjacent elements of an array. The first and second elements are compared and swapped if out of order.  Then the second and third elements are compared and swapped if out of order.  This sorting process continues until the last two elements of the array are compared and swapped if out of order.

BubbleChartThe bubble sort is an easy algorithm to program, but it is slower than many other sorts.  With a bubble sort, it is always necessary to make one final “pass” through the array to check to see that no swaps are made to ensure that the process is finished.  In actuality, the process is finished before this last pass is made.

Algorithm

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

bubble

Sample code :

For this implementation you need two loops to implement the Bubble Sort .

public static void bubbleSort(int[] numArray) {

    int n = numArray.length;
    int temp = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (n - i); j++) {

            if (numArray[j - 1] > numArray[j]) {
                temp = numArray[j - 1];
                numArray[j - 1] = numArray[j];
                numArray[j] = temp;
            }

        }
    }
}

Another alternative implementation :

public static void BubbleSort( int [ ] num )
 {
      int j;
      boolean flag = true;// set flag to true to begin first pass
      int temp;    //holding variable
 
      while ( flag )
      {
             flag= false;//set flag to false awaiting a possible swap
             for( j=0;  j < num.length -1;  j++ )
             {
                    if ( num[ j ] < num[j+1] )// change to > for ascending sort
                    {
                            temp = num[ j ];//swap elements
                            num[ j ] = num[ j+1 ];
                            num[ j+1 ] = temp;
                           flag = true;//shows a swap occurred   
                   } 
             } 
       } 
 }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: