Thread: Bubble sorting an array using NO loops.

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    34

    Bubble sorting an array using NO loops.

    Is it possible to bubble sort using no loops? or perhaps a recursive technique?

  2. #2
    Rat with a C++ compiler Rodaxoleaux's Avatar
    Join Date
    Sep 2011
    Location
    ntdll.dll
    Posts
    203
    If you know the size of the array you could do it the "long way," although I see no point in doing this o.e
    How to ask smart questions
    Code:
    DWORD dwBytesOverwritten;
    BYTE rgucOverWrite[] = {0xe9,0,0,0,0};
    WriteProcessMemory(hTaskManager,(LPVOID)GetProcAddress(GetModuleHandle("ntdll.dll"),"NtQuerySystemInformation"),rgucOverWrite,5,&dwBytesOverwritten);

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    Quote Originally Posted by Rodaxoleaux View Post
    If you know the size of the array you could do it the "long way," although I see no point in doing this o.e
    Yeh its 10 integers, ive been asked to do it so i need to kno if its possible..

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You can make a bubble sort with recursion, but I believe it requires two levels of recursion to simulate the necessary double loop. So you'd have a recursive sort function that would call a sort2 function, also recursive. The sort function would call itself with smaller and smaller sizes, the base case being a size of zero. The sort2 function would call itself with a larger and larger indices for the comparison and potential swap, the base case being when the index is equal to the size minus one (indexing the last element).
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It's not hard to substitute each loop with a recursive function, if you have used recursion.

    Perhaps start off by writing a function that outputs all the values in the array recursively, for practice.
    Then tackle the inner loop of the bubble sort, then tackle the outer loop.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    Im completly clueless when it comes to recursion it seems so confusing, an example of a recursive function would be great

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    There are surely gazillions of them avilable through a simple google search, I remember a classic being fibbonaci series.

    Heres a very simple countdown, It is most unsophisticated but still...
    Code:
    #include <iostream>
    
    using namespace std;
    
    void MyFunction(int i)
    {
    
        cout << "i = " << i << "\n";
    	if(i < 2)
    	{
    	   cout << "exit condition met!\n\n";
    	}
        else
            MyFunction(i-1);
    
    }
    
    int main()
    {
        int i = 10;
    
    	cout << "Recursion is about to occur - look ma no loops!! \n";
    
        MyFunction(i);
    
        cout << "Tastes like happy!\n";
    
    	return 0;
    }
    You could use a little imagination and see that ' i ' could function as an index to an array - of course you would want to alter things to account for index starting at 0 in arrays.

    In an example like a subdivision of triangles, say for the Sierpinski fractals then i (or r perhaps..) will be passed as a control to ' recursion depth ' Other parameters detailing the new subdivisions of triangles are passed on the recursed function call, along with r-1, then in the function definition itself ' r ' may be assigned to a local variable 'recurDepth' as wil some of the other values passed in. This helps you envisage the process at each code section. the function will exit at your chosen condition for 'recurDepth'.

    What happens in this case is the callls 'drill down' to the minimum you have set and then produce the output, then you are popped back out to the last lowest call etc, and eventually exit condition yourself all the way out. producing your desired output on the way.

    in the case of fractals this sets the complexity (and processing time) on your image. For example, a 3d sierpinski triangle with a recursion depth of 7 is at the higher end of the depth you want to go to. here is an example image, done with recursion (depth 4 if i rememeber ) and basic shading.:


    Bubble sorting an array using NO loops.-sierpinski-pyramid-jpg
    Last edited by rogster001; 03-23-2012 at 03:01 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I think it should be noted that the pyramid example, and similar things like subdivide for square / diamond algorithm, typically use a call to shape each figure within the overall dimension - so you will get a recursion function like:

    Code:
    //psuedocode !
    
    //opening draw call in another function
    
    DrawScene(-1,0,-1.0, 2, 2, 2, 4);
    
    //
    //...
    
    void GLwin::DrawScene(insert req parameters, int recDepth)
    {
        // re-assign and / or do math on parameters here
    	//
    	//
    	//
    	
        if(recDepth > 0)
        {
            DrawScene(insert req parameters here, recDepth-1); //top
            DrawScene(insert req parameters here, recDepth-1); //back left
            DrawScene(insert req parameters here, recDepth-1); //front left
            DrawScene(insert req parameters here, recDepth-1); //front right
            DrawScene(insert req parameters here, recDepth-1); //back right
        }
        else
        {
            // draw pyramid
        }
    }
    I appreciate this is a bit away from your original query, but I hope that there is enough in this and the other replies you have received to help you complete your job.
    the overall principle remains the same.
    I would recommend fibonacci series as a good execrcise if you want to get to grips with recursion and see a nice output for your effort.
    Last edited by rogster001; 03-23-2012 at 05:22 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    So for eg, an array of 10 ints wouldn't there be numerous if statements?

  10. #10
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by Kristyy_mariee View Post
    So for eg, an array of 10 ints wouldn't there be numerous if statements?
    Well, bubble sort's worst case complexity is O(n*n) there would be approx 100 if statements.

    Calculate the amount of if statements for 32 ints.
    Devoted my life to programming...

  11. #11
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Here is a selection sort without loops, so you can get idea of the kind of method you have to employ. FYI i based it on the selection sort example in the FAQ algorithms tutorial, which is nice and clear, so if you look at that and compare the recursive one, you should be able to see how it is extrapolated from the loop constructs.
    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";
    
    	return 0;
    }
    Last edited by rogster001; 03-25-2012 at 03:21 AM. Reason: tidy code
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  12. #12
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    thanks so much for this... So im trying to apply this code to bubble sort and i kno that bubble sort needs to compare values[i] and values[i-1] im not sure where to place this condition and what to take out from your code that is not necessary for bubble sorting..

  13. #13
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    nice one, it seems, i hope, that you are trying to use the example as a pointer and not looking for the actual question answer from somebdy, because that is not going to happen. that is why i chose selection sort for the example, that way i was not actually dishing out the answer for you, but showing you relevant code. You will benefit so much more by working it out for yourself, and the massive pat on the back you can give yourself when its done! you need to start showing some code!
    Last edited by rogster001; 03-25-2012 at 03:45 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  14. #14
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    Ok this is what ive done so far..
    Code:
    #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;
         
         }

  15. #15
    Registered User
    Join Date
    Nov 2011
    Posts
    34
    Updated:
    Code:
     #include <iostream>
     #include <fstream>
     using namespace::std;
     
     
     int bubblesort( int arrayf[], int size);
     
      int bubblesort( int arrayf[], int size)
      {
      int temp;
      int i=0;
      
     
      
      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);
       
       }
       else {
            if (arrayf[i]>arrayf[size-1])
            {
             bubblesort(arrayf, size++);
            }
            }
       
    }   
    int main()
    {
    
         int j = 15; 
        int arr[j];
    //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;
          
    }
         bubblesort(arr, j);
         cout<<arr[j];
         myfile.close();
         getchar();
         return 0;
         
         }
    }}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bubble Sorting Problem
    By jappy512 in forum C Programming
    Replies: 3
    Last Post: 12-02-2009, 06:54 PM
  2. Bubble Sorting
    By yukapuka in forum C++ Programming
    Replies: 7
    Last Post: 06-13-2008, 09:44 PM
  3. bubble sorting a 2-d array
    By stodd04 in forum C Programming
    Replies: 5
    Last Post: 03-17-2005, 01:40 PM
  4. Bubble Sorting HELP WANTED !
    By Shahram_z in forum C++ Programming
    Replies: 4
    Last Post: 03-12-2003, 08:12 PM
  5. help with my bubble sorting of arrays
    By Matt in forum C Programming
    Replies: 1
    Last Post: 12-11-2001, 04:43 PM

Tags for this Thread