Why is my logic wrong for my recursive sort program?
So my recursion selection sort calls the two functions max_index and swap and at the same time it should change things recursively, but for some reason it seems to break and explode on fire for certain arrays like the one I set Basically, does anyone know why this is so? Can someone explain and show me why this is not working?
int max_index(int arr[], int start, int end)
{
if ( start >= end ) {
return 0;
}
else if ( end - start == 1 ) {
return start;
}
else {
int greatest = max_index(arr, start + 1, end);
if( arr[start] > arr[greatest])
{
return start;
}
else
{
return greatest;
}
}
}
void swap(int arr[], int i, int j) {
int temp;
temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
void rec_ssort(int arr[], int len) {
int start = 0;
int last = len - 1;
//int n = len;
int maxindex = max_index(arr, start, last);
//if(arr[maxindex]>0 || arr[maxindex]<n)
{
if(arr[maxindex]>arr[last])
{
swap(arr, maxindex, last);
return rec_ssort(arr, last);
}
if(arr[maxindex] == arr[last])
{
return rec_ssort(arr, last);
}
}
}
int main(void)
{
int i = 0;
int arr[7] = {2,3,4,1,5,6,7};
int start = 0;
int end = 7;
int stuff = 5;
rec_ssort(arr, end);
for(i = 0; i<7; i++)
printf("%d\n", arr[i]);
}
+3
source to share
1 answer
All recursive methods need a base register (to exit the recursion). It also helps if you see progress on the recursion occurring at each step. Note that you didn't return when maxindex pointed to a value less than the latter.
This is one way to fix your problems in rec_ssort
:
void rec_ssort(int arr[], int len) {
// base case: if we're looking at an empty array we're done.
if (len <= 0) return;
int last = len - 1;
int maxindex = max_index(arr, 0, last);
if (arr[maxindex] > arr[last]) {
swap(arr, maxindex, last);
}
// recursively call with a shorter len
rec_ssort(arr, last);
}
+2
source to share