bubble sorting in an array

[galmca]

#include <stdio.h>
#define SIZE 10

int main()
{
int a[ SIZE ];
int i,n,pass,hold;
printf("enter the number of elements in an array:");
scanf("%d",&n);

printf( "Data items in original order\n" );

for ( i = 0; i <= SIZE - 1; i++ )
printf( "%4d", a[ i ] );

for ( pass = 1; pass <= SIZE - 1; pass++ )

for( i = 0; i <= SIZE - 2; i++ )
printf( "%d %d ", a[ i ], hold );
if ( a[ i ] > a[ i + 1 ] ) {
hold = a[ i ];
a[ i ] = a[ i + 1 ];
a[ i + 1 ] = hold;
}

printf( "\nData items in ascending order\n" );

for ( i = 0; i <= SIZE - 1; i++ )
printf( "%4d", a[ i ] );

printf( "\n" );

return 0;
}

the above program is for bubble sorting....
but it is not running properly....when i enter number of elements in an array:7
and enter array elements:5 10 15 14 16 18 20 ....it prints...some weird output of array in ascending order :1280315..1280313..etc..and then prints data items in ascending order after bubble sorting is:5 10 15 16 18 20...
whats wrong with the code?plz make some necessatu changes and plz explain th code if u can to make the program run successfully...im really confused now...????could u plz explain the functioning of for loops... here,,,???im confused now how is that working ..why have we taken i=size -2?in the for loop?plz explain the for loops ?
and plz make my program run correctly....its not showing any error but not running properly......

[Narue]

I refuse to help you until you learn how to indent your code. You're using code tags, so the problem is on your end. I don't know if you're lazy, or just stupid, but either way it makes your code harder to read and I don't have time to reformat it just so that I can help you with your problem.

And don't use bubble sort, ever. It has no redeeming qualities.

[Asif_NSU]

#define SIZE 10
... ... ...
int main()
{
     int a[ SIZE ];
     ... ... ...
     ... ... ...

     printf("enter the number of elements in an array:");
     scanf("%d",&n);

What is the point of asking for number of elements in the array when u have already defined the size of that array? If u want to work with fewer numbers then u have to use n instead of SIZE for the rest of ur program, which u havent done!!!

printf( "Data items in original order\n" );   
for ( i = 0; i <= SIZE - 1; i++ )  
     printf( "%4d", a[ i ] );

Did u even fill the array first???? No u did not. U are working with garbage values.

1. U first need to fill ur array (may be using random values or any other way)
2. U have to replace all the occurences of SIZE with n after the statement

scanf("%d",&n);

[Asif_NSU]

And don't use bubble sort, ever. It has no redeeming qualities.

Yes Bubble sort is the least efficient algorithm available.
However, for small data sets it doesnt matter much what sorting algorithm u use. And bubble sort does have a few good qualities. Apart from being the simplest and the easiest of the sorting algorithms it knows when the data set is already sorted(just a slight modification) making it ideal for sorted or nearly sorted data items(along with insertion sort).

From galmca's code it is quite apparent that he is trying to learn bubble sort, and u replied "don't use bubble sort, ever"!!!!!!!! ;)

[Narue]

>However, for small data sets it doesnt matter much what sorting algorithm u use.
That's true, so let's look at it from a clarity standpoint. But first, two reasonable implementations:

#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

#define length(x) (sizeof x / sizeof *x)

void bubble_sort(int array[], int size);
void insert_sort(int array[], int size);

int main()
{
  int a[] = {5,8,3,8,1,9,0,2,4};
  int b[] = {5,8,3,8,1,9,0,2,4};

  copy(a, a + length(a), ostream_iterator<int>(cout, " "));
  cout<<endl;
  copy(b, b + length(b), ostream_iterator<int>(cout, " "));
  cout<<endl;

  bubble_sort(a, length(a));
  insert_sort(b, length(b));

  copy(a, a + length(a), ostream_iterator<int>(cout, " "));
  cout<<endl;
  copy(b, b + length(b), ostream_iterator<int>(cout, " "));
  cout<<endl;
}

void bubble_sort(int array[], int size)
{
  for (int i = 0; i < size; i++) {
    bool swapped = false;

    for (int j = size - 1; j > i; j--) {
      if (array[j - 1] > array[j]) {
        swap(array[j - 1], array[j]);
        swapped = true;
      }
    }

    if (!swapped)
      break;
  }
}

void insert_sort(int array[], int size)
{
  int j, save;

  for (int i = 1; i < size; i++) {
    save = array[i];
    for (j = i; j >= 1 && save < array[j - 1]; j--)
      array[j] = array[j - 1];
    array[j] = save;
  }
}

Now we can look at your arguments from an objective viewpoint (yes, I can do that):

for small data sets it doesnt matter much what sorting algorithm u use

Small data sets have a tendency toward getting much bigger. This is a naive excuse, and I won't spend time on it because it doesn't deserve time.

Apart from being the simplest and the easiest of the sorting algorithms

I fail to see how the algorithm for bubble sort is simpler or easier than insertion sort. They're both simple, they're both easy. However, you'll find that the concept behind insertion sort is easier to grasp than that of bubble sort (from my experience as a teacher). The implementation is also easier to get right (I've written them and helped others write them enough to be able to say this with confidence).

it knows when the data set is already sorted

Resulting in a linear pass over the data set, yes. However both implementations I gave do that. This isn't an argument in favor of bubble sort, it's an argument that manages to keep bubble sort in the game. Of course, insertion sort handles this feature automagically while bubble sort requires a modification (the addition of a "when to stop" flag) to the basic algorithm.

making it ideal for sorted or nearly sorted data items

But no better than insertion sort, and it takes more work to get that "ideal" algorithm.

>From galmca's code it is quite apparent that he is trying to learn bubble sort
galmca has a lot to learn before trying any sorting algorithms. But why start learning with the worst possible thing? Why not learn the right way, then if you're interested in poor algorithms as a curiosity, take a look?

>and u replied "don't use bubble sort, ever"!!!!!!!!
No, I replied: "don't use bubble sort, ever." I have a strong distaste of using multiple punctuation characters without good cause. And you still haven't given a good reason for using bubble sort. There's no existing situation (outside of theoretical computer science) where bubble sort is better than any other sorting algorithm.

Bubble sort should have died long ago, but people like you keep saying "Aww, it's not really that bad if the data set is miniscule and won't ever grow and the items are tiny and you don't compare it with any other sorting algorithm or take your head out of the sand and look around". But of course, you're not going to listen to me because hey, what do I know?

[Asif_NSU]

First I would like to make ur bubble sort implementation a bit shorter so that it doesnt look bigger than ur insertion sort which i believe u did intentionally.

void bubble_sort(int array[], int size)
{
  bool swapped =  true;

  while(swapped){
    swapped =  false;

    for (int i = 0; i < size - 1 ; ++i)
       if (array[i] > array[i+1]) {
          swap(array[i], array[i+1]);
          swapped = true;
       }
  }
}

However, you'll find that the concept behind insertion sort is easier to grasp than that of bubble sort (from my experience as a teacher).

One time a student went up to John Von Neumann after a calculus lecture. "Professor Von Neumann," the student said, ``I don't understand how you got the answer to that last problem on the board." Von Neumann looked at the problem for a minute and said, "e^x." The puzzled student thought he had been unclear. "I know that's the answer, Professor Von Neumann. I just don't see how to get there." Von Neumann looked at the student for a minute, stared into space, and repeated, "e^x ". The student started to get frustrated. "But how did you get that answer?" Von Neumann turned to the student and said, "Look kid, what do you want? I just did it for you two different ways".
Moral: Sometimes professors have a hard time remembering what life was like before they knew calculus inside out. Having taught the same material over and over again, year after year, they just don't understand why the students haven't mastered it yet.

I m a student and from my "experience"(whatever) i will tell u which one is easier and which one is not. The sorting algorithm that has the easiest of the concepts is the selection sort and may be then it's insertion sort. Bubble sort may not have the easiest of the concepts(actually i sometimes wonder how can it even sort like this) but once u write the code for bubble sort it just sinks into u. Without any brainstorming u can write the code flawlessly over and over again. It is the easiest "to learn", "to write" and most importantly u can do that without any brainstorming(IMPORTANT) and without any flaws. While to achieve the same level of fluency in other sorting algorithms u have to go to narue and she must "help u write them enough to be able to say this with confidence".

"I fail to see how the algorithm for bubble sort is simpler or easier than insertion sort."-- i think i have explained why u failed to see that, it's not ur fault, it's just ur experience.... :)

The ease of implementation is what made bubble sort live this long. It does know when the items are sorted. I said all these in response to ur comment: "And don't use bubble sort, ever. It has no redeeming qualities." Well it does have a few qualities as i pointed it out. I m not arguing whether bubble is better than insertion sort or not. I did say that it is the least efficient algorithm.

U have to consider two things(besides others) when u code. First CPU usage which i know u are very concerned about. And then there is ur "brainpower"; i believe u have 4 ghz of the latter with an air-conditioner in the room so u dont care about what it's running. I will go about writing quicksort or shaker sort when i see my cpu taking real abuse, but will use bubble sort when i think other sorting algos taking the toll on my brain which unlike u i hold precious than my cpu. :mrgreen:

Bubble sort is not for u, it's for us, and it's worth it.

>No, I replied: "don't use bubble sort, ever."
Ofcourse u replied: "don't use bubble sort, ever." It is I who used the extra punctuation marks. U should have seen that since the quotation mark preceeds the exclamations. U replied "don't use bubble sort, ever." And I replied: "u replied "don't use bubble sort, ever"!!!!!!!!"

Thanx for spending ur precious time on this worthless argument.

[Narue]

>which i believe u did intentionally
I didn't, but you can believe that if you want.

>u have to go to narue and she must "help u write them enough to be able
Now you're just being sarcastic. Here I was hoping that my well reasoned arguments would be received with an open mind. I guess I overestimated you.

>Bubble sort is not for u, it's for us, and it's worth it.
I've seen million-dollar projects scuttled because some moronic bobo who didn't know better used bubble sort. You seem to think I'm doing this because I disagree with the concept in theory. I disagree with any practical use of bubble sort because it sucks and has destroyed real applications. I disagree with teaching bubble sort because people who learn bubble sort, use bubble sort. That takes us full circle and you've wasted lots of money and lots of time because "it's for us, and it's worth it".

>i think i have explained why u failed to see that, it's not ur fault, it's just ur experience....
No, you haven't explained anything. I'm not talking about me, I'm talking about the many people that I've taught over the years. When someone who knows better explains both algorithms, insertion sort is grasped more quickly.

I know what our differences are. You advocate mindless repetition because it's easier in the short term and I encourage understanding because it makes you a better programmer. Remember that when I'm working successfully in this field long after you've failed.

>Thanx for spending ur precious time on this worthless argument.
If you weren't dumb enough to contradict me then there wouldn't have been a worthless argument. I don't mind if you disagree with me, or argue your point, but don't encourage shoddy programming practices.

[Asif_NSU]

've seen million-dollar projects scuttled because some moronic bobo who didn't know better used bubble sort. You seem to think I'm doing this because I disagree with the concept in theory. I disagree with any practical use of bubble sort because it sucks and has destroyed real applications. I disagree with teaching bubble sort because people who learn bubble sort, use bubble sort. That takes us full circle and you've wasted lots of money and lots of time because "it's for us, and it's worth it".

This is unbelievable. There is no reason to scuttle a project because someone used bubble sort. It just needs to be replaced with a better sorting algorithm and that's all. I am a moronic bobo but i do understand when to restrict myself from using bubble sort and it is hard to believe that someone used bubble sort in anything like a million dollar project. The only place i would use bubble sort would be a short program where sorting is just a trivial part. This is the reason why i said it's not for u, bcos it is unlikely that u will have to write a program that invovles sorting an array of a mere 100 or so elements. But for us bubble sort is more than enough in such a situation.

I believe that it is not always necessary to choose the best possible algorithm but to choose the algorithm that is sufficient to solve a given problem in a reasonable amount of time.

Yes even my professor did not teach us bubble sort in my data structues course. But the idea of "dont teach bubble bcos they will use it in real world" is just not a smart one. U have to teach bubble sort and also introduce why should it not be used in real life practical programming.

I guess I overestimated you.

From where i can see u r underesmating urself. Look at these lines of insertion sort:

save = array;
... ... ...
for ( ... ;j >= 1 && save < array[j - 1];...)
array[j] = array[j - 1];
array[j] = save;

The idea of firts saving the item to be inserted in the right place, the breaking condition that if a item is in the right place means the set is already sorted etc are what makes it a little elegant and therefore a bit harder to understand and write than bubble. The moment u look at the bubble sort code u can see that theres just a flag and swapping of unsorted elements, and it's obviously easier to grasp than insertion.