Bubble sort using recursion

[Voltron160]

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]);
         }
      }
   }
}

[vmanes]

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.

[mrnutty]

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 ".

[Voltron160]

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.

[vmanes]

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.

[lafigueroa]

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.

[lafigueroa]

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

[Voltron160]

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.

[LevyDee]

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