Need help writing a bubble sort with no loops
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 25

Thread: Need help writing a bubble sort with no loops

  1. #1
    Join Date
    Nov 2011
    Posts
    10

    Need help writing a bubble sort with no loops

    Ive written a long program that should be a bubble sort , unfortunately I cant use loops ...is there any way i can shorten this and make it indeed a bubble sort? Its sorting atm but its not entirely correct.
    Code:
    #include <stdio.h>
    #include <iostream>
    #include<fstream>
    #include<string>
     
    void swap(int *, int *);
     
    using namespace std;
    int main(int argc, char *argv[])
    {
        int key,a[14],i;
        string line;
         cout<<"Enter search key";
         cin>>key;
    //opens file
      ifstream myfile ("integers.txt");
       
      if (myfile.is_open())
      {
        while ( myfile.good() )
        {
              for(i=0;i<=14;i++){
            myfile>>a[i];                    
           
          cout << a[i] << endl;
           
        }
     
     if (a[0] > a[1]) swap(a, a+1);
    if (a[1] > a[2]) swap(a+1, a+2);
    if (a[2] > a[3]) swap(a+2, a+3);
    if (a[3] > a[4]) swap(a+3, a+4);
    if (a[4] > a[5]) swap(a+4, a+5);
    if (a[5] > a[6]) swap(a+5, a+6);
    if (a[6] > a[7]) swap(a+6, a+7);
    if (a[7] > a[8]) swap(a+7, a+8);
    if (a[8] > a[9]) swap(a+8, a+9);
    if (a[9] > a[10]) swap(a+9, a+10);
    if (a[10] > a[11]) swap(a+10, a+11);
    if (a[11] > a[12]) swap(a+11, a+12);
    if (a[12] > a[13]) swap(a+12, a+13);
    if (a[13] > a[14]) swap(a+13, a+14);
     
     
    if (a[0] > a[1]) swap(a, a+1);
    if (a[1] > a[2]) swap(a+1, a+2);
    if (a[2] > a[3]) swap(a+2, a+3);
    if (a[3] > a[4]) swap(a+3, a+4);
    if (a[5] > a[6]) swap(a+5, a+6);
    if (a[6] > a[7]) swap(a+6, a+7);
    if (a[7] > a[8]) swap(a+7, a+8);
    if (a[8] > a[9]) swap(a+8, a+9);
    if (a[9] > a[10]) swap(a+9, a+10);
    if (a[10] > a[11]) swap(a+10, a+11);
    if (a[11] > a[12]) swap(a+11, a+12);
    if (a[12] > a[13]) swap(a+12, a+13);
    if (a[13] > a[14]) swap(a+13, a+14);
     
     
     
    if (a[0] > a[1]) swap(a, a+1);
    if (a[1] > a[2]) swap(a+1, a+2);
    if (a[2] > a[3]) swap(a+2, a+3);
    if (a[3] > a[4]) swap(a+3, a+4);
    if (a[5] > a[6]) swap(a+5, a+6);
    if (a[6] > a[7]) swap(a+6, a+7);
    if (a[7] > a[8]) swap(a+7, a+8);
    if (a[8] > a[9]) swap(a+8, a+9);
    if (a[9] > a[10]) swap(a+9, a+10);
    if (a[10] > a[11]) swap(a+10, a+11);
    if (a[11] > a[12]) swap(a+11, a+12);
    if (a[12] > a[13]) swap(a+12, a+13);
    if (a[13] > a[14]) swap(a+13, a+14);
     
    if (a[0] > a[1]) swap(a, a+1);
    if (a[1] > a[2]) swap(a+1, a+2);
    if (a[2] > a[3]) swap(a+2, a+3);
    if (a[3] > a[4]) swap(a+3, a+4);
    if (a[5] > a[6]) swap(a+5, a+6);
    if (a[6] > a[7]) swap(a+6, a+7);
    if (a[7] > a[8]) swap(a+7, a+8);
    if (a[8] > a[9]) swap(a+8, a+9);
    if (a[9] > a[10]) swap(a+9, a+10);
    if (a[10] > a[11]) swap(a+10, a+11);
    if (a[11] > a[12]) swap(a+11, a+12);
    if (a[12] > a[13]) swap(a+12, a+13);
    if (a[13] > a[14]) swap(a+13, a+14);
     
      
    cout << "Sorted array : ";
     
    for (int i = 0; i < 14; i++) cout << a[i] << " ";
     
    cout << endl;
     
     
     
     
     
         
        }
        myfile.close();
      }
     
      else cout << "Unable to open file";
    system("pause");
    return 0;
    }
    void swap(int *x, int *y) {
     
    int temp = *x;
     
    *x = *y;
     
    *y = temp;
     
    }

  2. #2
    Join Date
    Aug 2009
    Posts
    437

    Re: Need help writing a bubble sort with no loops

    Why can't you use loops? I suppose you could use recursion here.

  3. #3
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    its jus what ive been asked to do.. Ive gotten suggestions about recursion but im still a bit lost as to how id implement it with the whole base case condition etc etc

  4. #4
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    11,980

    Re: Need help writing a bubble sort with no loops

    Who asked you to do this and why?

    Recursion would be the only practical alternative, although it's unusual to implement a bubble sort using it. Any decent search engine will bring you to a page explaining how to do it.

  5. #5
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    Its some homework I have to do.. I have googled recursion and tried finding bubble sorts using it but i cant find any that dont have loops or that work so ive come here..

  6. #6
    Join Date
    Jan 2009
    Posts
    596

    Re: Need help writing a bubble sort with no loops

    This might get you started. Here is the way to use recursion to print out the contents of a vector, instead of using a loop to do so:
    Code:
    #include <vector>
    #include <iostream>
    using namespace std;
    
    // Prints all entries of vector 'vecInt', 
    // starting at index 'start' and going until the end
    void recurse_print(const vector<int>& vecInt, const int start)
    {
    	if (start >= vecInt.size()) return;
    	cout << vecInt[start] << " ";
    	recurse_print(vecInt, start+1);
    }
    
    int main()
    {
    	// Fill up the vector
    	vector<int> vecInt;
    	for (int i=0; i<10; ++i) {
    		vecInt.push_back(i);
    	}
    
    	recurse_print(vecInt, 0);
    	cout << endl;
    
    	return 0;
    }
    Instead of explicitly looping over the contents of the vector, we process one entry then call the recursive function again on the remainder of the vector. The base case (when 'start' is past the end of the vector) simply returns.

    You will need to do something similar to replace the loops in the bubble sort.

  7. #7
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    Code:
    #include <iostream>
     
    using namespace std;
     
    void MyFunction(int a)
    {
     
        cout << "i = " << a << "\n";
        if(a < 2)
        {
           cout << "exit condition met!\n\n";
        }
        else
            MyFunction(a-1);
    
    }
     
    int main()
    {
        int a=10;
     
        cout << "Recursion is about to occur \n";
     
        MyFunction(a);
     
      
     system("pause");
        return 0;
    }
    Ok i have this simple code which output 10 int just like the above. I understand that it can replace a loop but how i would integrate it in to this bubble sort code I have is beyond me. The recursive code prints 10 numbers in order but how i would switch it up to sort an array ... Im seriously drawing a blank.
    Code:
    #include<stdio.h>  
    #include<conio.h>
    #include<iostream.h>  
      
      void bubble(int a[],int n)  
      {  
            int i,j,t;  
             for(i=n-2;i>=0;i--)  
             {  
                for(j=0;j<=i;j++)  
      
                      {  
                        if(a[j]>a[j+1])  
                                        {  
                                          t=a[j];  
                                         a[j]=a[j+1];  
                                         a[j+1]=t;  
                                        }  
                       }  
             
      
               }//end for 1.  
      
      }//end function.  
      
      
      int main()  
      {  
      
          int a[100],n,i;  
      
          //clrscr();  
      
          printf("\n\n Enter integer value for total no.s of elements to be sorted: ");  
          scanf("&#37;d",&n);  
      
          for( i=0;i<=n-1;i++)  
                { printf("\n\n Enter integer value for element no.%d : ",i+1);  
                  scanf("%d",&a[i]);  
                }  
      
           bubble(a,n);  
      
           printf("\n\n Finally sorted array is: ");  
           for( i=0;i<=n-1;i++)  
           printf("%3d",a[i]);  
      system("pause");
      } //end program.

  8. #8
    Join Date
    Jan 2009
    Posts
    596

    Re: Need help writing a bubble sort with no loops

    OK, I've just had a bit of fun refactoring your bubble sort and replacing the iteration with recursion.

    Giving advice on this is a bit tricky without effectively doing it for you But I'll do my best.

    The first thing you should do is split the bubble sort function into several, so you can disentangle the two loops.

    Here is your code:
    Code:
    void bubble(int a[],int n)
    {
      for(int i=n-2;i>=0;i--) {
        for(int j=0;j<=i;j++) {
          if(a[j]>a[j+1]) {
            int t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
          }
        }
      }
    }
    I would recommend you start by taking the inner loop out and putting it into a new function. This function would need to have three parameters - the array a[], length of array n, and the value of i from the outer loop. Then call this function from the bubble function.

    Once you have done this you will have two functions, each with just the one loop.

    Then I'll give you tips on removing the loops...

  9. #9
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    Ok ive tried, bare with me if theyre any stupid errors
    Code:
    #include<stdio.h>  
    #include<conio.h>
    #include<iostream.h>  
    
      void function(int a[],int n.length, int i){
           
           for(j=0;j<=i;j++)  
      
                      {  
                        if(a[j]>a[j+1])  
                                        {  
                                          t=a[j];  
                                         a[j]=a[j+1];  
                                         a[j+1]=t;  
                                        }  
                       }  
             
             
      void bubble(int a[],int n)  
      {  
            int i,j,t;  
             for(i=n-2;i>=0;i--)  
             {  
                function(int a,int n,int i);
      
               }//end for 1.  
      
      }//end function.  
      
      
      int main()  
      {  
      
          int a[100],n,i;  
      
          //clrscr();  
      
          printf("\n\n Enter integer value for total no.s of elements to be sorted: ");  
          scanf("&#37;d",&n);  
      
          for( i=0;i<=n-1;i++)  
                { printf("\n\n Enter integer value for element no.%d : ",i+1);  
                  scanf("%d",&a[i]);  
                }  
      
           bubble(a,n);  
      
           printf("\n\n Finally sorted array is: ");  
           for( i=0;i<=n-1;i++)  
           printf("%3d",a[i]);  
      system("pause");
      } //end program.

  10. #10
    Join Date
    Jan 2009
    Posts
    596

    Re: Need help writing a bubble sort with no loops

    It's best to check it compiles and works properly at each stage of the refactoring

    Tidying up the indentation would be nice too...

  11. #11
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    I have a recursive selection sort, so im thinking i can make this code into a bubble sort, I'm not exactly sure what i should change or what the REAL difference is in the coding for the 2 types of sorting....
    Code:
    #include <iostream>
     
    using namespace std;
     
    const int MAX = 10;
     
    void InnerLoop(int values[10], int& min, int j)
    {
     
        if(j != MAX)
        {
            if(values[min] > values[j])
            {
                min = j;
            }
           InnerLoop(values, min, j+1);
        }
     
    }
     
    void OuterLoop(int values[10], int i)
    {
        int min = i;
        int tempVal = 0;
        if(i != MAX)
        {
            int j = i;
            InnerLoop(values, min, j);
            tempVal = values[i];
            values[i] = values[min];
            values[min] = tempVal;
            OuterLoop(values, i+1);
        }
    }
     
    int main()
    {
        int i = 0;
        int values[10] = { 25, 3, 17, 12, 9, 22, 4, 16, 8, 56 };
     
        cout << "Recursive selection sort \n\n";
     
        cout << "values unsorted:\n";
        for(int i = 0; i < MAX; i++)
        cout << values[i] << "\n";
     
        cout << "\nvalues sorted\n";
     
        OuterLoop(values, i);
        for(int i = 0; i < MAX; i++)
        cout << values[i] << "\n";
     
        cout << "\nDone\n";
     system("pause");
        return 0;
    }

  12. #12
    Join Date
    Nov 2011
    Posts
    10

    Re: Need help writing a bubble sort with no loops

    I know there needs to be a part where values[i] is compared to values[i-1] i jus dont kno where to place this condition... and also what i need to take out..

  13. #13
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Need help writing a bubble sort with no loops

    Quote Originally Posted by kristyy_mariee View Post
    I know there needs to be a part where values[i] is compared to values[i-1] i jus dont kno where to place this condition... and also what i need to take out..
    I think your basic issue is that you more than likely did not work this out on paper first.

    Before writing one line of code, you should have had an algorithm worked out recursively that sorts a range of numbers by comparing adjacent items, starting from the first item to the last. That is basically what a bubble sort is. Doing this requires no knowledge of C++, for loop syntax, or anything like that. You could even write the algorithm in English if you had to -- as long as each step is well-defined, that's what you initially needed to do.

    If you did that, then the code to do this using C++, and quite honestly, any language that looks like C++ would have been trivial. Right now, you're trying to work this all out by writing a program, which is the wrong way to go about doing this.

    Regards,

    Paul McKenzie

  14. #14
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Need help writing a bubble sort with no loops

    As to the psuedo-code -- a bubble sort can be checked for termination by simply setting a boolean and checking if any swaps occurred. If that boolean suggests that no swaps occurred, then you know the list is sorted and its time to quit. If you've reached the end of the list, and the boolean suggests that you made a swap somewhere, then you know you have to go back to the start of the list and go through the list again.

    You know that you can't use loops, so the first thing is to write a function that will call itself up until it reaches the end of the list. So to this function, you must pass a variable that denotes the number of items in the list, the current item you're looking at now, and of course, the array itself, and the boolean that tests if you need to keep sorting. You set this boolean to "I am sorted", and then call the swapper recursive function from the first item (item 0).

    Then you do some checks in this "swapper" function:

    1) If you are at the last item, determine whether you need to start the swapper from item 0 again (check the boolean for "I am not sorted"), or quit swapper because you know that nothing was swapped and you've sorted the list successfully (check the boolean to see if "I am sorted"). If you need to go back to the beginning, then you also need to set the boolean to "I am sorted".

    2) If you are not at the last item , determine if you need to swap the item and the one next to it. If so, set the boolean to "I am not sorted", swap the items, and then call the "swapper" recursion with the next item number.

    See, no loops -- all I do is call this "swapper" and I return from everything when that boolean determines nothing was swapped, and I went through the entire list.

    Now is this right? I don't know for sure -- maybe I missed something. The point is I can go through it by hand, draw it up on paper, and see if it does what I expect it to do by trying a small number of items. Once I make the corrections to the above, then and only then do I consider how to write this using C++.

    At least I have some sort of blueprint in front of me that seems to do the job in terms of psuedo-code. Again, the trick is to draw this up on paper without loops.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 25th, 2012 at 12:30 PM.

  15. #15
    Join Date
    Jan 2009
    Posts
    596

    Re: Need help writing a bubble sort with no loops

    Paul's suggestion to write the recursive algorithm from scratch would obviously work. But given that you already have a working version, but one which uses loops, it is easier to refactor this working version into a form which uses recursion to simulate the loops. This is the approach I was taking when I suggested splitting the original bubble function into two functions, each with one loop. Each of these functions can then be simply refactored to replace the loop with a recursive call to the function itself.

    So with that in mind, do you have a version of this code (your initial refactoring) which compiles?
    Quote Originally Posted by kristyy_mariee View Post
    Code:
    #include<stdio.h>  
    #include<conio.h>
    #include<iostream.h>  
    
      void function(int a[],int n.length, int i){
           
           for(j=0;j<=i;j++)  
      
                      {  
                        if(a[j]>a[j+1])  
                                        {  
                                          t=a[j];  
                                         a[j]=a[j+1];  
                                         a[j+1]=t;  
                                        }  
                       }  
             
             
      void bubble(int a[],int n)  
      {  
            int i,j,t;  
             for(i=n-2;i>=0;i--)  
             {  
                function(int a,int n,int i);
      
               }//end for 1.  
      
      }//end function.  
      
      
      int main()  
      {  
      
          int a[100],n,i;  
      
          //clrscr();  
      
          printf("\n\n Enter integer value for total no.s of elements to be sorted: ");  
          scanf("%d",&n);  
      
          for( i=0;i<=n-1;i++)  
                { printf("\n\n Enter integer value for element no.%d : ",i+1);  
                  scanf("%d",&a[i]);  
                }  
      
           bubble(a,n);  
      
           printf("\n\n Finally sorted array is: ");  
           for( i=0;i<=n-1;i++)  
           printf("%3d",a[i]);  
      system("pause");
      } //end program.
    Once you do you can replace the loops in both 'function' and 'bubble' with recursive calls.

    This is a brief outline as to how this is done.
    Suppose we have this (pseudo)code:
    Code:
    void func(arguments)
    {
      for (init_loop_variable; check_loop_variable; update_loop_variable) {
        stuff_to_do(arguments, loop_variable(?));
      }
    }
    where init_loop_variable, check_loop_variable and update_loop_variable are appropriate expressions for the relevant parts of the for statement, and 'arguments' is whatever arguments the function takes. I have put a ? mark after loop_variable in the argument list for stuff_to_do as it may or may not be needed in any particular case.
    This is equivalent to:
    Code:
    void func(arguments)
    {
      init_loop_variable;
      for (;check_loop_variable;) {
        stuff_to_do(arguments, loop_variable(?));
        update_loop_variable;
      }
    }
    We now need to split this into two functions
    Code:
    void func(arguments)
    {
      init_loop_variable;
      func2(arguments, loop_variable);
    }
    
    void func2(arguments, loop_variable)
    {
      for (;check_loop_variable;) {
        stuff_to_do(arguments, loop_variable(?));
        update_loop_variable;
      }
    }
    The new function (func2) can then be refactored to replace the loop with recursive calls to func2 itself:
    Code:
    void func2(arguments, loop_variable)
    {
      if (check_loop_variable) {
        stuff_to_do(arguments, loop_variable(?));
        update_loop_variable;
        func2(arguments, loop_variable);
      }
    }
    We now have code which is exactly equivalent to the original version, which had a for loop, but which uses recursion to simulate the for loop.

    This procedure can be done on any function which consists of a single loop - I used a for loop for the example but while loops and do/while loops can be turned into for loops so are also covered.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center