Bubble sort

**Mr.Lnx** · 11-16-2012

Hello. I have a doubt about this code

Code:

#include <stdio.h>
void bubble_sort(int []);
#define LEN 5
 
int main( void )
{
    
        int array[LEN] = { 5 , 1 , 4 , 2 , 8 } , count =0  ;
        
        printf(" Before sorting ");
        
        for(; count<LEN; count++)
        printf(" %d " , array[count]);
        
        bubble_sort(array);
        
        printf(" After sorting ");
        
        count = 0;
        
        while( count < LEN )
        {
        printf(" %d " , array[count]);
        count++;
    }
 
        return 0;
}
void bubble_sort(int array[])
{
        int i , j;
        
        for( i = LEN - 1; i >= 1; i-- )  // <-------
        {
                printf("\n");
                
                for(j=0; j<5; j++)   // <-------
                {
                        if( array[j] > array[j+1] )
                        
                        {
                                int temp = array[j];
                                array[j] = array[j+1];
                                array[j+1] = temp;
                        }
                        
                        printf("\n %d" , array[j]);  // <----- print in every passing  
                }
        }
        
        return;
}
 
/*
 
 Before sorting  5  1  4  2  8 
 
1st passing  ( 4 >= 1)
 
 1
 4
 2
 5
 8
 
2nd passing  ( 3 >= 1)
 
 1
 2
 4
 5
 8
 
3rd passing  ( 2 >= 1)
 
 1
 2
 4
 5
 8
 
4th passing ( 1 >= 1)

 1
 2
 4
 5
 8  
 
 After sorting  1  2  4  5  8 
 
 */

I think the i>=1 it does one more passing that is unnecessary because the array is already sorted (after 3rd passing ).... I think i > 1 is the right. What is your opinion about that ? I had an argue with a friend about this.

**std10093** · 11-16-2012

What would you sau for i>0 ?

example

**Nyah Check** · 11-16-2012

well i ran your code and it printed 2 5s at the end of the sorting looking at the algorithm i think the mixup comes when j goes up to 4 and i comes down to 1 and there is the case when i and j are equal causing a problem.. let me edit and run..

**Nyah Check** · 11-16-2012

check this out .. i tried this and the code sorts perfectly...

Code:

int i , j;

        for( i = LEN - 1; i >= 1 && i != j; i--)
        {
            printf("\n");
            for(j=0; j != i && j < LEN; j++)
            {
                if( array[j] > array[j+1] )
                {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }

**sean** · 11-16-2012

the array is already sorted

I won't pretend to have gotten enough sleep last night to settle this myself, but don't forget that as far as a sorting algorithm knows, the array might already be sorted before it even starts. Just because the array you happen to be testing with IS sorted at that point, it doesn't mean your algorithm can assume that yet.

**root** · 11-16-2012

This is a better solution, in this way if there aren't swaps(so it means that is ordered) it stops.
Said formally, in the best case the time complexity of this implementation in 0(n) instead of O(n^2) of the classic one.

Code:

void bsort (int* array, int length){
int i,j,flag=1,temp;

  for(i=0; (i<length-1) && flag; i++) {
        flag=0; 

        for (j=length-1; j>i; j--){

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

**iMalc** · 11-16-2012

Your original post has a buffer overrun. j<5 should be j<LEN-1.

The easiest way to see if you have the boundary conditions correct is to see what happens if there are exactly two items. There should be only one compare, and if they were out of order then one swap.
If you include the change I just mentioned above, then the original code will do exactly that. However, your i>1 idea would instead mean that zero comparisons are made and it would fail to sort.
Therefore the outer loop is correct as-is; your friend was right, and you were wrong. But you both fail on missing the buffer overrun.

**Mr.Lnx** · 11-17-2012

Originally Posted by iMalc

Your original post has a buffer overrun. j<5 should be j<LEN-1.

The easiest way to see if you have the boundary conditions correct is to see what happens if there are exactly two items. There should be only one compare, and if they were out of order then one swap.
If you include the change I just mentioned above, then the original code will do exactly that. However, your i>1 idea would instead mean that zero comparisons are made and it would fail to sort.
Therefore the outer loop is correct as-is; your friend was right, and you were wrong. But you both fail on missing the buffer overrun.

I face problems in understanding the algorithm. Not problems in C syntax or something about the language.

I want to discuss with someone about it... I don't want to take some algorithm from web in order to give it in some exercise. Thank you for your time....

On the topic now.... if we have 10 elements 0....9 for example... we really need 8 comparisons (inner loop) among the elements. (This technique is not the improvement of the algorithm of course).

Generally if we have n elements we really need n-1 comparisons among the elements...... so inner loop would be concerned about that.

Now... I can't understand how will be the outer loop . I think the number of outer passings is something different from comparisons into inner loop.

for example PASSING 1 -> n-1 comparisons...
PASSING 2-> n-1 comparisons... and so forth

how can know the number of passings before go inner loop ? I just really confused... I can't understand... I have understood quicksort algorithm and now I face problems? :/

**Adak** · 11-17-2012

That's the problem with Bubble sort. It moves just one value, one index over, every time it iterates through the inner loop. It's fast on sorting small sets, but Insertion sort is faster. Once you start adding in the optimizations to Bubble sort to make it competitive with Insertion sort, you need more code - so you've gained nothing. It's still slower than Insertion sort, it's more code, and it's not as easy to remember.

If you miss out on understanding Bubble sort's "secrets", imo, you haven't missed much.

**iMalc** · 11-17-2012

Originally Posted by Mr.Lnx

On the topic now.... if we have 10 elements 0....9 for example... we really need 8 comparisons (inner loop) among the elements. (This technique is not the improvement of the algorithm of course).

Actually, the first pass would need 9 item comparisons in the inner loop.

Code:

0   1   2   3   4   5   6   7   8   9 // Item index
 \ / \ / \ / \ / \ / \ / \ / \ / \ /
  1   2   3   4   5   6   7   8   9   // 1st, 2nd 3rd comparisons etc

Thre are modifications to bubble sort such that subsequent passes can be significantly shorter in some cases, or the algorithm may even terminate after any given pass if the sorting is detected as complete. But in all cases, the first pass contains N-1 comparisons.

Think about how many comparisons are needed to determine if N items are in order. Because bubble sort can be made to exit after the first pass, no matter what, it still needs to do that much work in the first pass.
Psst, check out my homepage, link below

Thread: Bubble sort

Thread Tools

Search Thread

Display

Bubble sort

Similar Threads

using bubble sort to sort a matrix by sum..

bubble sort

Bubble Sort, Qucik Sort

a little help with bubble sort

My Bubble Sort, help