Bubble Sort

[maximus123]

Hi
I'm trying to do a simple bubble sort on a list of numbers. So I'm trying to write a program that will go through an array of numbers, compare one with the next one and if the first is larger than the second, they'll be switched. I've managed to create a while loop which works but only once through the list, this sorts the numbers a bit but obviously not completely. I cannot figure out how to get it to repeat. I presume maybe nesting this within another while loop but I can't think what condition to use for the outer loop. Anyway here is the portion of the code which works, and my question is what is the best way to get this loop to repeat itself?

#include<iostream>



int main(){

float bubble[23]={1,5,16,3,75,4,5,23,12,34,34,705,345,435,234,6,45,4,9,0,56,32,78};
int elements=sizeof(bubble)/sizeof(int);
int arrnum=0;
int changes=0;

while(arrnum<elements)
    {
    if(*(bubble+arrnum)>*(bubble+arrnum+1)){
                       
                float temp=*(bubble+arrnum);
                *(bubble+arrnum)=*(bubble+arrnum+1);
                *(bubble+arrnum+1)=temp;
                changes+=1;
                }
                       
     arrnum++;                   
      }


std::cout<<changes<<std::endl;

system("pause");
}

Any help would be appreciated.
P.S I don't want to change the basic idea of my code too much as the point here is to get practice using arrays and pointers, rather than perhaps some more advanced method for a bubble sort.

[Albatross]

Take a look at this bubble sort psuedocode.

procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

What does it have that your implementation is missing?

-Albatross

[maximus123]

Is it the idea of 'until not swapped'? Because in my code above I have a line which adds a 1 every time the if statement is completed, that line is within the if statement and reads; 'changes+=1'. I was hoping to enclose my while loop within another loop which basically said 'perform this inner loop until nothing is added to the variable 'changes' i.e perform the inner loop until the if statement is not used for an entire round of the while loop.
However the condition I was trying to set was something like while(changes!=0), but i couldn't get it to work. So I guess I mean something along these lines

#include<iostream>



int main(){

float bubble[23]={1,5,16,3,75,4,5,23,12,34,34,705,345,435,234,6,45,4,9,0,56,32,78};
int elements=sizeof(bubble)/sizeof(int);
int arrnum=0;
int changes=0;

while(changes!=0)
{
while(arrnum<elements)
    {
    if(*(bubble+arrnum)>*(bubble+arrnum+1)){
                       
                float temp=*(bubble+arrnum);
                *(bubble+arrnum)=*(bubble+arrnum+1);
                *(bubble+arrnum+1)=temp;
                changes+=1;
                }
                       
     arrnum++;                   
      }

}


system("pause");
}

But this doesn't compile and I think I know why, however I've tried a few variations on this theme and cannot get the inner loop to execute more than once.

[Albatross]

Your new program compiles alright for me, though I admit I'm not using -pedantic.

However, you are forgetting to reset something (actually, two somethings), and your outer while loop will never run due to changes being 0 when the condition is checked at the top of the loop.

Furthermore, you probably should have had bubble as an array of ints. Yes, I know having the type of the main array of a bubble sort be float is cute. XD

-Albatross

[maximus123]

Yes you're right it does compile, that came out wrong, I meant it wasn't doing what I hoped it would.

The changes variable being 0 at the top is also why I was certain there was a problem but I've tried just declaring the variable without assigning it an initial value but that has caused the same issues.

As for the resetting issue, do you mean the arrnum value back to zero each time before the commencement of the inner loop? I had a go bringing the int arrnum=0 line within the scope of the outer loop but that has done nothing. I'm out of ideas I'm afraid, loop syntax definitely not a strong point.

[Albatross]

To avoid the changes issue, you could either use a do-while loop (recommended) or initialize it to something that's not zero.

Have you tried using a for loop for your inner loop? That should help clean things up a bit regarding the whole looping process.

Arrnum is not the only thing that needs to be reset to zero just before the inner loop starts.

How well do you understand how a bubble sort works?

-Albatross

[maximus123]

Ah yes, the do-while loop, I had forgotten about that, that's a good idea, so the code will get a chance to run before checking the condition.

As for how well I understand the bubble sort, I would have to say, only moderately. I understand that it compares two values, it switches them using a holding variable and pointers pointing to the data in the array. However not much more than that.

[Albatross]

Basically, a bubble sort for n elements works the following way:

1. Start by comparing element 0 and element 1.
2. If the element with a higher index is smaller than the one with the lower index, swap them so that the element with a lower value has a lower index.
3. Repeat #2, comparing the next two elements until element n-2 and n-1 have been compared.
4. If any swaps were made while iterating over the elements, repeat the entire process again until a pass is made with no swaps. If a pass is made with no swaps, that means the array is sorted.

It's basically a cheap and dirty sort and one of the easiest to understand sorting algorithms. It just goes back and forth, flipping elements until each element is in the right order.

-Albatross