Is it possible to bubble sort using no loops? or perhaps a recursive technique?
Printable View
Is it possible to bubble sort using no loops? or perhaps a recursive technique?
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
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).
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.
Im completly clueless when it comes to recursion it seems so confusing, an example of a recursive function would be great
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...
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.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;
}
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.:
Attachment 11573
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:
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.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
}
}
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.
So for eg, an array of 10 ints wouldn't there be numerous if statements?
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;
}
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..
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!
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;
}
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;
}
}}