Need help writing a bubble sort with no loops

[kristyy_mariee]

Ok i only just saw the last two replies I did this today its a bit off but i tried.
Ok this is what ive done so far..

#include <iostream>
 using namespace::std;
 
 
 int bubblesort( int arrayf[], int size);
 
  int bubblesort( int arrayf[], int size)
  {
  int temp;
  int i=0;
  
  arrayf[size];
  
  bool swapped = false;
  
   if (arrayf[i]>arrayf[i+1])
   {
                             
    swapped = true;
    
   temp = arrayf[i];
   arrayf[i] = arrayf[i+1];
   arrayf[i+1] = temp;
   bubblesort(arrayf,0);
   cout<<arrayf[i];
   }
   else {
        if (arrayf[i]>arrayf[size-1])
        {
         bubblesort(arrayf, size--);
        }
        }
   
}   
int main()
{
    int j = 15; 
    int arr[j];
     bubblesort(arr, j);
     
     getchar();
     return 0;
     
     }

[Lindley]

  arrayf[size];

This is not accomplishing anything.

[Paul McKenzie]

Ok i only just saw the last two replies I did this today its a bit off but i tried.
Ok this is what ive done so far..

First, you should pass the array, the size, and the current index. So right at the start, your bubblesort() function doesn't have enough information to know where to start the comparison, and whether to finish or not.

int bubblesort( int arrayf[], int currentItem, int arraySize, bool isSwapped)
{
  //... stuff missing...
  // somewhere code like this will be made to test the items
  if (arrayf[currentItem] > arrayf[currentItem + 1] ) 
  {
       // stuff to do
  }
  // more stuff to do...
  //...
  // somewhere, a call like this will be made to compare the next two items
  bubblesort( arrayf, currentItem + 1, arraySize, isSwapped );
}   

int main()
{
    int arr[] = { 10, 2, 45, 6, 7, 1, -3, 44, 3, 0, 12, 8 };
    const int numValues = sizeof(arr) / sizeof(arr[0]);

    bool bSwapped = false;
    bubblesort(arr, 0, numValues, bSwapped);  // start from the first item
}

The main() function is complete. There is nothing else to add to get the bubblesort to start. Also note the dummy data, and the way I computed the number of items so that you are not stuck on 15 items.

The part you need to fill in is the function, and what I described is how you should be proceeding.

The bubblesort function knows the array, it knows the current item, it knows the array size, and it knows when the items are swapped. So you know everything you need to know as to whether to stop sorting or keep sorting, or go back to the top of the array and start over, etc. I just put in two random lines of code as to a hint of what needs to be done. There is a lot of missing code, for example, checking if you're at the end of the array, you need to decide whether to quit or to go back to the beginning.

So go through this by hand.

The first thing you do is determine if currentItem is at the end of the array. If not, then you will be testing items 0 and 1 (10 and 2). They are out of sequence, so you a) swap them and b) set the bSwapped to true c) call bubblesort again to go to the next two items. Etc...

Regards,

Paul McKenzie

[kristyy_mariee]

I had to include a file as its what my assignment is asking for... I changed my variables to yours and made some changes to the code but its still outputting bogus numbers, do i still need more code?

#include <iostream>
 #include <fstream>
 using namespace::std;
 
 
 int bubblesort( int arrayf[], int currentitem, int arraysize, bool isswapped);
 
 int bubblesort( int arrayf[], int currentitem, int arraysize, bool isswapped)
  {
  int temp;
  
  
if (arrayf[currentitem]!=arraysize){ //checking for end of array

   if (arrayf[currentitem]>arrayf[currentitem+1])//swapping if smaller
   {
                                
   temp = arrayf[currentitem];
   arrayf[currentitem] = arrayf[currentitem+1];
   arrayf[currentitem+1] = temp;
   isswapped = true;
             
             //else {
   //if(arrayf[currentitem]<arrayf[currentitem+1])
   
        //isswapped=false;
        
   bubblesort(arrayf,currentitem+1,arraysize-1,isswapped);
   
                                                          }
                                               
                                              }
}   
int main()
{

     int j = 15; 
    int arr[j];
    const int numValues = sizeof(arr) / sizeof(arr[0]);
//opens file
  ifstream myfile ("integers.txt");
  
  if (myfile.is_open())
  {
    while ( myfile.good() )
    {cout<<"unsorted";
          for(j=0;j<=14;j++){
        myfile>>arr[j];                     
      
      cout << arr[j] << endl;
     
      
} 
 
      bool bSwapped = false;
    bubblesort(arr, 0, numValues, bSwapped);  // start from the first item

    
     cout<<arr[j];
     myfile.close();
     getchar();
     return 0;
     
     }
}}

[Paul McKenzie]

I had to include a file as its what my assignment is asking for... I changed my variables to yours and made some changes to the code but its still outputting bogus numbers, do i still need more code?

1) Are you using a debugger to debug your code? You're supposed to be debugging your code and see where it goes wrong.

2) Start with 3 or 4 numbers, not 15. If you can't get it to work with 3 or 4 numbers, then trying to do 15 will just cause you to lose track.

3)

if (arrayf[currentitem]!=arraysize){ //checking for end of array

This check is not correct. If currentItem is arraysize-1, then you know you've reached the end of the array. The reason is that you're comparing pairs, and the last pair that will be compared are

arraysize-2, arraysize-1

4) Why are you calling bubblesort() this way?

bubblesort(arrayf,currentitem+1, arraysize-1,isswapped);

Why are you calling it with arraysize-1? Do you know that the original arraysize is practically the entire driving force with the recursion? So why are you changing it? Just keep passing arraysize.

Otherwise, what you end up doing is starting the sort in the middle of the array, and you're making your list smaller by changing arraysize. You're making your list disappear at both ends, the beginning and the end, for each call to bubblesort(), and that is not correct.

Regards,

Paul McKenzie

[Paul McKenzie]

Also, why not check for the end of the array first and act upon whether you've reached the end? Then the code becomes much more simple and easier to understand:

   bubblesort(array, currentItem, numberofitems, swapped)
   ...
   Have I reached the end of the array?
   Yes -> 
           Check if swapped is true.
           Yes -> start bubble sort at the beginning again
                  set isSwapped to false
                  call bubblesort starting at item 0.

            No -> Just return.  Everything is sorted.

    No, not reached the end of the array ->          
           Check if current item and next item needs to be swapped.
           Yes -> they need to be swapped
                 Swap them.
                 Set isSwapped to true.
                 Call bubblesort with next item (item + 1)

           No -> they do not need to be swapped
                 Call bubblesort with next item (item + 1)

That is it. That is practically the entire function without writing it in C++. The goal now is can you follow it? Again, start with 4 numbers that are not sorted. Go through this by hand if you have to.

And just to let you know, the difference between this version of bubblesort and Peter's version is that his version unconditionally loops N*N times, even if the items are already sorted (where N is the number of items). Nothing wrong with that, as that is how the bubble sort is described in most texts as far as the number of comparisons to be made. This version does the same thing (compares adjacent pairs), with the difference being it knows when to stop sorting by checking a boolean "swapped" value. So it has just a bit of an optimization added to it.

Regards,

Paul McKenzie

[kristyy_mariee]

Check if swapped is true.
Yes -> start bubble sort at the beginning again
set isSwapped to false
call bubblesort starting at item 0.
No -> Just return. Everything is sorted.

if (arrayf[currentitem]=arraysize-1){ //checking for end of array
 if (isswapped==true){
                    
                    isswapped=false;
                    bubblesort(arrayf,0,arraysize,isswapped);
                    }
                    else
                    {
                        if (isswapped==false)
                         return bubblesort(arrayf,currentitem+1,arraysize,isswapped);
                         }
                         
                         }

is the same as?

[ovidiucucu]

[ Moved thread ]

[Paul McKenzie]

No, it is not OK. It also would help if you properly formatted your code.

if (arrayf[currentitem]=arraysize-1)

There are several things wrong. First, why are you comparing the contents of the last item to the sizeof the array - 1? You're supposed to compare the index of the item and see if it is the last one.

What if the last item in the array is -1000, and the number of items in the array is 20? Are you going to compare -1000 to 19? Of course not. You want to compare the index of the current item, i.e. 19 to the number of items-1, i.e. 19.

Second, to compare items, you use ==, not =.

if ( currentitem == arraysize - 1 )

That is what that line is supposed to be.

Now this:

No -> Just return. Everything is sorted.

This should be self-explanatory, but somehow you don't understand. Where do you do a return if everything is sorted? Instead, you do this right away:

          if (isswapped==false)
                     return bubblesort(arrayf,currentitem+1,arraysize,isswapped);
                         }
                         
                         }

Where in the steps is it outlined that if you're on next to the last item, and no items are swapped, to keep calling bubblesort()? You have to follow the steps carefully.

I practically handed you the answer in my last email, but I just didn't write it in C++. There's little I can do more for you -- at this point it should have been very easy to understand the steps (again, you don't need to write a program -- follow the steps by hand with just a few unsorted numbers).

Regards,

Paul McKenzie

[monarch_dodra]

Just a wild question: Is the size of the array you are supposed to sort known when you compile?

Because that is the only explanation that I can find that would make sense of your no loop requirement, and would be implementable in a logical fashion...

In a word: It would change EVERYTHING.