based upon the bubble sort function below, convert it into a recursive function.
ID: 3693280 • Letter: B
Question
based upon the bubble sort function below, convert it into a recursive function.
template <class ItemType>
void sort (ItemType a[ ], int size)
{
ItemType tmp;
int rightEnd = size - 1; //a[0]…a[rightEnd] is unsorted
for (int pass = 0; pass < size-1; pass++)
{
//in each pass, compare adjacent pairs and swap.
//move largest number to the right…
for (int i = 0; i < rightEnd; i++)
{
if (a[i] > a[i + 1])
{
tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
}
}
rightEnd- -;//a[rightEnd] doesn’t need to be changed…
}
}
Explanation / Answer
Recurssive function:
void sort2(ItemType a[], int first, int last){
if(first < last && last > 0){
if(a[first] > a[first+1]){
ItemType temp = a[first];
a[first] = a[first+1];
a[first+1] = temp;
}
sort2(a, first+1, last);
sort2(a, first, last-1);
}
else
return;
}
void sort (ItemType a[], int size){
sort2(a,0,size-1);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.