I'm a beginner in programing so please be understanding with my code.. I'm working on a problem set where I have to implement a selection sort using recursion. I feel like it should work but I get an error message and i can't figure out why.
the problem set consists in that I use a recursive function where i have to look for the largest number in an array, store it in the last position and sort the entire array using this method.
int array[n];
printf ("enter numbers: ");
for (i = 0; i < n; i )
{
scanf ("%i", &array[i]);
}
selection_sort(n, array);
printf ("sorted numbers: ");
for (i = 0; i < n; i )
{
printf ("%i", array[i]);
}
return 0;
here is the recursive function that i'd like to implement. i used curpos to store the position of the largest number, lastpos to store the location of the last element in the array, and a tmp variable to store the largest number.
and this is the error message that i get.
.c:67:34: error: incompatible integer to pointer conversion passing 'int' to parameter of type 'int *'; take the address with & [-Werror,-Wint-conversion]
return selection_sort(n, array[n-1]);
^~~~~~~~~~
&
if (n <= 0)
{
return 1;
}
else
{
for (i = 0; i < n; i )
{
if (tmp <= array[i]) //look for the largest number and update it into tmp
{
tmp = array[i];
curpos = array[i]; //remember the location of the current largestnumber
}
}
lastpos = array[n-1]; // save the last element into a variable before swap
array[n-1] = tmp; // put the largest number into the last element
curpos = lastpos; // put the last element before swap into the changed location.
return selection_sort(n, array[n-1]);
}
}
I hope you can give me a hand to understand the recursion better. thank you so much in advance.
CodePudding user response：
The error message means that in this call
return selection_sort(n, array[n-1]);
you are passing an element of the array of the type int with the index n-1. But the function expects a pointer of the type int *.
Moreover the value of the first parameter is always the same and equal to n.
Also the return type of the function does not make a sense. The function should be declared with the return type void.
Also you need to swap two elements if within the array there is found an element that is greater than the last element.
The function can be declared and defined the following way
void selection_sort( int a[], size_t n )
{
if (!( n < 2 ))
{
size_t i = --n;
for (size_t j = n; j-- != 0; )
{
if (a[i] < a[j]) i = j;
}
if (i != n)
{
int tmp = a[i];
a[i] = a[n];
a[n] = tmp;
}
selection_sort( a, n );
}
}
Here is a demonstration program.
#include <stdio.h>
void selection_sort( int a[], size_t n )
{
if (!( n < 2 ))
{
size_t i = --n;
for (size_t j = n; j-- != 0; )
{
if (a[i] < a[j]) i = j;
}
if (i != n)
{
int tmp = a[i];
a[i] = a[n];
a[n] = tmp;
}
selection_sort( a, n );
}
}
int main( void )
{
int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
const size_t N = sizeof( a ) / sizeof( *a );
for (size_t i = 0; i < N; i )
{
printf( "%d ", a[i] );
}
putchar( '\n' );
selection_sort1( a, N );
for (size_t i = 0; i < N; i )
{
printf( "%d ", a[i] );
}
putchar( '\n' );
}
The program output is
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
CodePudding user response：
The return value is a red herring. You don't use it so your function may as well be void.
if (n <= 0)
{
return 1;
}
The second thing to notice is that you can't pass an array to a function. You are passing a pointer to the beginning of the array. This is good, because otherwise you wouldn't be able to sort it.
else
{
for (i = 0; i < n; i )
{
Right here is an issue. You haven't initialised tmp and curpos. You need to do that before the loop.
if (tmp <= array[i]) //look for the largest number and update it into tmp
{
tmp = array[i];
curpos = array[i]; //remember the location of the current largestnumber
}
}
lastpos = array[n-1]; // save the last element into a variable before swap
array[n-1] = tmp; // put the largest number into the last element
curpos = lastpos; // put the last element before swap into the changed location.
Finally, right here you have the right idea, but the wrong notation. You want to pass the same array, but 1 less element
return selection_sort(n, array[n-1]);
Should be:
return selection_sort(n-1, array);
}
CodePudding user response：
return selection_sort(n, array[n-1]);
Using this line, you pass the value that is stored in the array at position n-1 to the function.
However, obviously, the function requires an array as argument, not a number.
Using the following line, you pass the entire array to the function:
return selection_sort(n, array);
Unlike Java and similar programming languages, C functions cannot read out the size of arrays passed as arguments.
For this reason, there is no difference between passing the first M elements of an array to a function and passing the entire array to a function!
You must pass some additional function argument to the function so the function knows how long the (sub-)array is.
Maybe the first argument (n) can already be used to do this.
Using the following line, you pass a "sub-array" of the array starting at element n-1 to the function:
return selection_sort(n, &(array[n-1]));
or (an alternative notation with the same meaning):
return selection_sort(n, array n-1);
Once again, it does not matter if you want to pass the sub-array containing elements (n-1)...n or the sub-array containing the elements (n-1)...(n 1000).
If I understand your code correctly, changing the line the following way should work:
return selection_sort(n-1, array);