bubble sorting recursively

[kmg2012]

This is a recursive selection sort i would like to be able to change this code without the use of loops into a bubble sort for my assignnment. Ive been trying for an extremelyy long time and im also fairly new to c++ and im struggling. any help would be great...

            #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;
                }

[TrustyTony]

I would not use this code as base but think logic fresh, looks like machine translation of loops to recursion, yak :(!

• What is the base case you know to sort?
• How you reduce the size of problem to ultimately this base case by recursing?

[mike_2000_17]

Don't use recursion when you expect a linear recursion depth (or more). In your code, for an array of size N, your recursive function will eventually be called N times. When you use recursion, in the real world, you have to be vigilant about the depth of the recursion because too much depth will fill the stack very quickly and lead to stack-overflow errors. Normally, recursion is only used for log(N) calls, for example, you can implement a merge-sort with recursive calls because the depth is limited by O(log(N)). Similarly, people often implement quicksort algorithms with recursion, with best-case depth of log(N), but because the worst-case depth is linear, the basic quicksort algorithm is not used in practice, instead, people use introsort or similar variants that make sure to put a hard limit on the depth of recursion. Most algorithms that are more naturally expressed as recursions have log(N) depth, like "good" sorting algorithms, binary searches, etc.

All naive sorting algorithms, like bubble-sort, selection-sort, insertion-sort, etc., which are all O(N^2), will lead to a linear recursion depth, and they are usually just as easy to implement as a loop. For these two reasons, you will never see or hear about recursive implementations of these algorithms.

There are ways in which you can use recursion even with an expected linear depth. This involves what is called "tail recursions" which is a way to program the function such that the recursion will not lead to a filling of the stack. Basically, the idea is that the recursive function has no footprint on the stack frame. Doing this reliably requires inspecting the assembly code produced by your compiler to make sure the stack won't be filling up as the recursions progress. In general, it is not worth the trouble.

All this said, if you are being asked to implement a bubble-sort algorithm recursively, then you can certainly do so. I might add that your prof is an idiot, giving you the assignment of writing one of the worst sorting algorithms in the worst possible way. I hate when profs get the idea that since recursions are harder to understand and implement, that they should constantly give that as a "challenge" to their students, even when it makes absolutely no sense at all.

The problem here is that all you have posted is a recursive selection sort algorithm, and you are asking us about a bubble-sort algorithm. My intuition is that you didn't write that code, and simply didn't manage to find a recursive bubble-sort. If you have been working for a long time on the recursive bubble-sort algorithm, why didn't you post that code you are working on, not some other unrelated piece of code. Furthermore, if you managed to get this selection-sort done, I wonder how you could seriously have trouble with bubble-sort, which is way easier to do, even recursively.

[kmg2012]

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;

             }

[TrustyTony]

lines 10 and 12 do not msle sense, you should pass the place of buble and swapped status.