This program sorts in descending order.
Hey guys, I am wondering if I could get some help with making this bubble sort program
sort recursively. Any help would be appreciated, thanks.

#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <stdlib>

#define TRUE 1
#define FALSE 0

void bubble (int[], int);
void Swap(int &, int &);

void main()    // The main is used every time but slight modifications to function bubble
{
    const int size = 5;
    int arry[size] = {10, 9, 5, 1, 8};
   bubble (arry, size);

   for (int i = 0; i < size; i++)
     cout<<arry[i]<<"  ";
     //printf(" ",&arry[i]);

   getch();
}                                           //End of main



 void Swap(int &a, int &b)
 {
    int hold;
         hold = a;
            a = b;
            b = hold;
 }

 void bubble( int x[], int n )
{
   int j, pass;
   int switched = TRUE;

   for( pass = 0; pass < n - 1 && switched == TRUE; pass++ )
   {
      switched = FALSE;
      for( j = 0; j < n - pass - 1; j++ )
      {
         if( x[j] < x[j+1] )
         {
            switched = TRUE;
            Swap(x[j], x[j+1]);
         }
      }
   }
}

First I would ask, "WHY?" Why take the slowest sort and slow it down further with the overhead of more function calls and additional memory usage? And, you will have a sort that may overflow the stack on sorting a large array.

That said, a quick bit of googling finds this been attacked by others. I didn't look to closely at any posted solutions to ensure they really work.

As with any recursive algorithm, first define your base case - at what subset of the problem do you stop recursing? Then, how do you call the function with a smaller set of the input data? Do you have it sort from index 0 to index limit - 1, or call the function with the next element of the array and process to the end?

Think on that a while. Take a stab and post some code.

Let me emphasize this a little more," First I would ask, "WHY?" Why take the slowest sort and slow it down further with the overhead of more function calls and additional memory usage? And, you will have a sort that may overflow the stack on sorting a large array ".

Let me emphasize this a little more," First I would ask, "WHY?" Why take the slowest sort and slow it down further with the overhead of more function calls and additional memory usage? And, you will have a sort that may overflow the stack on sorting a large array ".

I know this is the slowest method but my lecturer asked that I found a way to use this bubble sort to search recursively. Its just for my learning experience.

On a whim, I tried to do Bubble sort recursively. I'm at a loss how to do it, what I came up with was Insertion sort, sorting the far end of the array first rather than the beginning end as is usual. And it ran about 3x slower than a correct insertion sort.

Maybe with a few tequilas in me, I could imagine a solution to this. Frankly, as a teacher, I think this is a less than optimal use of students' time.

I created a version called bubble2 that perform a recursive bubble sort. I left the comments in so you can "see" how it is working. You basically start at position n-1 and find the smallest or largest element in the list. The recursion comes in by calling bubble2 again with one less element (n, n-1, n-2, etc) each time in the function it finds the smallest or largest element that belongs in position n.

void bubble2( int x[], int n )
{
	cout << "n: " << n << endl;	
	if ( n == 1 ) return;
	//find the correct position for item n and then bubble the next one down
	for (int i=n-2; i >=0 ; i--) {
		cout << "comparing " << x[i] << " against " << x[n-1] << endl;
		if ( x[i] < x[n-1] ) {
			cout << "\t swapping\n";
			Swap(x[i], x[n-1]);
		}
	}
	cout << "\t\tRECURSING ....." << endl;
	bubble2(x, n-1);
}

I sorted in the same order you had in your original bubble sort.

My version feels like insertion sort to me....maybe that is the point of the exercise? In any case.....please note this is a version of INSERTION SORT .....I will keep thinking on it

My version feels like insertion sort to me....maybe that is the point of the exercise? In any case.....please note this is a version of INSERTION SORT .....I will keep thinking on it

Thanks, will review.

Oh, and before anyone else reems you for this, make your main an int type. Just sayin...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.