Ive written a long program that should be a bubble sort , unfortunately I cant use loops ...is there any way i can shorten this and make it indeed a bubble sort? Its sorting atm but its not entirely correct.
Code:
#include <stdio.h>
#include <iostream>
#include<fstream>
#include<string>
void swap(int *, int *);
using namespace std;
int main(int argc, char *argv[])
{
int key,a[14],i;
string line;
cout<<"Enter search key";
cin>>key;
//opens file
ifstream myfile ("integers.txt");
if (myfile.is_open())
{
while ( myfile.good() )
{
for(i=0;i<=14;i++){
myfile>>a[i];
cout << a[i] << endl;
}
if (a[0] > a[1]) swap(a, a+1);
if (a[1] > a[2]) swap(a+1, a+2);
if (a[2] > a[3]) swap(a+2, a+3);
if (a[3] > a[4]) swap(a+3, a+4);
if (a[4] > a[5]) swap(a+4, a+5);
if (a[5] > a[6]) swap(a+5, a+6);
if (a[6] > a[7]) swap(a+6, a+7);
if (a[7] > a[8]) swap(a+7, a+8);
if (a[8] > a[9]) swap(a+8, a+9);
if (a[9] > a[10]) swap(a+9, a+10);
if (a[10] > a[11]) swap(a+10, a+11);
if (a[11] > a[12]) swap(a+11, a+12);
if (a[12] > a[13]) swap(a+12, a+13);
if (a[13] > a[14]) swap(a+13, a+14);
if (a[0] > a[1]) swap(a, a+1);
if (a[1] > a[2]) swap(a+1, a+2);
if (a[2] > a[3]) swap(a+2, a+3);
if (a[3] > a[4]) swap(a+3, a+4);
if (a[5] > a[6]) swap(a+5, a+6);
if (a[6] > a[7]) swap(a+6, a+7);
if (a[7] > a[8]) swap(a+7, a+8);
if (a[8] > a[9]) swap(a+8, a+9);
if (a[9] > a[10]) swap(a+9, a+10);
if (a[10] > a[11]) swap(a+10, a+11);
if (a[11] > a[12]) swap(a+11, a+12);
if (a[12] > a[13]) swap(a+12, a+13);
if (a[13] > a[14]) swap(a+13, a+14);
if (a[0] > a[1]) swap(a, a+1);
if (a[1] > a[2]) swap(a+1, a+2);
if (a[2] > a[3]) swap(a+2, a+3);
if (a[3] > a[4]) swap(a+3, a+4);
if (a[5] > a[6]) swap(a+5, a+6);
if (a[6] > a[7]) swap(a+6, a+7);
if (a[7] > a[8]) swap(a+7, a+8);
if (a[8] > a[9]) swap(a+8, a+9);
if (a[9] > a[10]) swap(a+9, a+10);
if (a[10] > a[11]) swap(a+10, a+11);
if (a[11] > a[12]) swap(a+11, a+12);
if (a[12] > a[13]) swap(a+12, a+13);
if (a[13] > a[14]) swap(a+13, a+14);
if (a[0] > a[1]) swap(a, a+1);
if (a[1] > a[2]) swap(a+1, a+2);
if (a[2] > a[3]) swap(a+2, a+3);
if (a[3] > a[4]) swap(a+3, a+4);
if (a[5] > a[6]) swap(a+5, a+6);
if (a[6] > a[7]) swap(a+6, a+7);
if (a[7] > a[8]) swap(a+7, a+8);
if (a[8] > a[9]) swap(a+8, a+9);
if (a[9] > a[10]) swap(a+9, a+10);
if (a[10] > a[11]) swap(a+10, a+11);
if (a[11] > a[12]) swap(a+11, a+12);
if (a[12] > a[13]) swap(a+12, a+13);
if (a[13] > a[14]) swap(a+13, a+14);
cout << "Sorted array : ";
for (int i = 0; i < 14; i++) cout << a[i] << " ";
cout << endl;
}
myfile.close();
}
else cout << "Unable to open file";
system("pause");
return 0;
}
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
its jus what ive been asked to do.. Ive gotten suggestions about recursion but im still a bit lost as to how id implement it with the whole base case condition etc etc
Recursion would be the only practical alternative, although it's unusual to implement a bubble sort using it. Any decent search engine will bring you to a page explaining how to do it.
Its some homework I have to do.. I have googled recursion and tried finding bubble sorts using it but i cant find any that dont have loops or that work so ive come here..
This might get you started. Here is the way to use recursion to print out the contents of a vector, instead of using a loop to do so:
Code:
#include <vector>
#include <iostream>
using namespace std;
// Prints all entries of vector 'vecInt',
// starting at index 'start' and going until the end
void recurse_print(const vector<int>& vecInt, const int start)
{
if (start >= vecInt.size()) return;
cout << vecInt[start] << " ";
recurse_print(vecInt, start+1);
}
int main()
{
// Fill up the vector
vector<int> vecInt;
for (int i=0; i<10; ++i) {
vecInt.push_back(i);
}
recurse_print(vecInt, 0);
cout << endl;
return 0;
}
Instead of explicitly looping over the contents of the vector, we process one entry then call the recursive function again on the remainder of the vector. The base case (when 'start' is past the end of the vector) simply returns.
You will need to do something similar to replace the loops in the bubble sort.
#include <iostream>
using namespace std;
void MyFunction(int a)
{
cout << "i = " << a << "\n";
if(a < 2)
{
cout << "exit condition met!\n\n";
}
else
MyFunction(a-1);
}
int main()
{
int a=10;
cout << "Recursion is about to occur \n";
MyFunction(a);
system("pause");
return 0;
}
Ok i have this simple code which output 10 int just like the above. I understand that it can replace a loop but how i would integrate it in to this bubble sort code I have is beyond me. The recursive code prints 10 numbers in order but how i would switch it up to sort an array ... Im seriously drawing a blank.
Code:
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void bubble(int a[],int n)
{
int i,j,t;
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}//end for 1.
}//end function.
int main()
{
int a[100],n,i;
//clrscr();
printf("\n\n Enter integer value for total no.s of elements to be sorted: ");
scanf("%d",&n);
for( i=0;i<=n-1;i++)
{ printf("\n\n Enter integer value for element no.%d : ",i+1);
scanf("%d",&a[i]);
}
bubble(a,n);
printf("\n\n Finally sorted array is: ");
for( i=0;i<=n-1;i++)
printf("%3d",a[i]);
system("pause");
} //end program.
I would recommend you start by taking the inner loop out and putting it into a new function. This function would need to have three parameters - the array a[], length of array n, and the value of i from the outer loop. Then call this function from the bubble function.
Once you have done this you will have two functions, each with just the one loop.
Ok ive tried, bare with me if theyre any stupid errors
Code:
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void function(int a[],int n.length, int i){
for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void bubble(int a[],int n)
{
int i,j,t;
for(i=n-2;i>=0;i--)
{
function(int a,int n,int i);
}//end for 1.
}//end function.
int main()
{
int a[100],n,i;
//clrscr();
printf("\n\n Enter integer value for total no.s of elements to be sorted: ");
scanf("%d",&n);
for( i=0;i<=n-1;i++)
{ printf("\n\n Enter integer value for element no.%d : ",i+1);
scanf("%d",&a[i]);
}
bubble(a,n);
printf("\n\n Finally sorted array is: ");
for( i=0;i<=n-1;i++)
printf("%3d",a[i]);
system("pause");
} //end program.
I have a recursive selection sort, so im thinking i can make this code into a bubble sort, I'm not exactly sure what i should change or what the REAL difference is in the coding for the 2 types of sorting....
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";
system("pause");
return 0;
}
I know there needs to be a part where values[i] is compared to values[i-1] i jus dont kno where to place this condition... and also what i need to take out..
I know there needs to be a part where values[i] is compared to values[i-1] i jus dont kno where to place this condition... and also what i need to take out..
I think your basic issue is that you more than likely did not work this out on paper first.
Before writing one line of code, you should have had an algorithm worked out recursively that sorts a range of numbers by comparing adjacent items, starting from the first item to the last. That is basically what a bubble sort is. Doing this requires no knowledge of C++, for loop syntax, or anything like that. You could even write the algorithm in English if you had to -- as long as each step is well-defined, that's what you initially needed to do.
If you did that, then the code to do this using C++, and quite honestly, any language that looks like C++ would have been trivial. Right now, you're trying to work this all out by writing a program, which is the wrong way to go about doing this.
As to the psuedo-code -- a bubble sort can be checked for termination by simply setting a boolean and checking if any swaps occurred. If that boolean suggests that no swaps occurred, then you know the list is sorted and its time to quit. If you've reached the end of the list, and the boolean suggests that you made a swap somewhere, then you know you have to go back to the start of the list and go through the list again.
You know that you can't use loops, so the first thing is to write a function that will call itself up until it reaches the end of the list. So to this function, you must pass a variable that denotes the number of items in the list, the current item you're looking at now, and of course, the array itself, and the boolean that tests if you need to keep sorting. You set this boolean to "I am sorted", and then call the swapper recursive function from the first item (item 0).
Then you do some checks in this "swapper" function:
1) If you are at the last item, determine whether you need to start the swapper from item 0 again (check the boolean for "I am not sorted"), or quit swapper because you know that nothing was swapped and you've sorted the list successfully (check the boolean to see if "I am sorted"). If you need to go back to the beginning, then you also need to set the boolean to "I am sorted".
2) If you are not at the last item , determine if you need to swap the item and the one next to it. If so, set the boolean to "I am not sorted", swap the items, and then call the "swapper" recursion with the next item number.
See, no loops -- all I do is call this "swapper" and I return from everything when that boolean determines nothing was swapped, and I went through the entire list.
Now is this right? I don't know for sure -- maybe I missed something. The point is I can go through it by hand, draw it up on paper, and see if it does what I expect it to do by trying a small number of items. Once I make the corrections to the above, then and only then do I consider how to write this using C++.
At least I have some sort of blueprint in front of me that seems to do the job in terms of psuedo-code. Again, the trick is to draw this up on paper without loops.
Regards,
Paul McKenzie
Last edited by Paul McKenzie; March 25th, 2012 at 12:30 PM.
Paul's suggestion to write the recursive algorithm from scratch would obviously work. But given that you already have a working version, but one which uses loops, it is easier to refactor this working version into a form which uses recursion to simulate the loops. This is the approach I was taking when I suggested splitting the original bubble function into two functions, each with one loop. Each of these functions can then be simply refactored to replace the loop with a recursive call to the function itself.
So with that in mind, do you have a version of this code (your initial refactoring) which compiles?
Originally Posted by kristyy_mariee
Code:
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void function(int a[],int n.length, int i){
for(j=0;j<=i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void bubble(int a[],int n)
{
int i,j,t;
for(i=n-2;i>=0;i--)
{
function(int a,int n,int i);
}//end for 1.
}//end function.
int main()
{
int a[100],n,i;
//clrscr();
printf("\n\n Enter integer value for total no.s of elements to be sorted: ");
scanf("%d",&n);
for( i=0;i<=n-1;i++)
{ printf("\n\n Enter integer value for element no.%d : ",i+1);
scanf("%d",&a[i]);
}
bubble(a,n);
printf("\n\n Finally sorted array is: ");
for( i=0;i<=n-1;i++)
printf("%3d",a[i]);
system("pause");
} //end program.
Once you do you can replace the loops in both 'function' and 'bubble' with recursive calls.
This is a brief outline as to how this is done.
Suppose we have this (pseudo)code:
where init_loop_variable, check_loop_variable and update_loop_variable are appropriate expressions for the relevant parts of the for statement, and 'arguments' is whatever arguments the function takes. I have put a ? mark after loop_variable in the argument list for stuff_to_do as it may or may not be needed in any particular case.
This is equivalent to:
We now have code which is exactly equivalent to the original version, which had a for loop, but which uses recursion to simulate the for loop.
This procedure can be done on any function which consists of a single loop - I used a for loop for the example but while loops and do/while loops can be turned into for loops so are also covered.
Reply With Quote
But I'll do my best.
Originally Posted by kristyy_mariee
Bookmarks