Thread: recursive selection sort..

how to fix the min function?

i tried to implement it again with the fixed minimum function
it not sorting it
??

Code:

#include <stdio.h>
void recSelSort(int array[],int length);
void selSort(int array[], int i ,int length);
void swap(int num[],int i,int j);
int recFindMin(int array[], int index);

int main()
{
    int array[4] = {2, 1, 3,0};

	recSelSort(array,4);
    printf("%d,%d,%d,%d\n", array[0],array[1],array[2],array[3]);

    return 0;
}

 void recSelSort(int array[],int length)
{
	selSort(array,0,length);
} 

// sort array from i (till i is sorted and min)
 void selSort(int array[], int i ,int length)
{    
		if (i<length)
             {
				 swap(array,i,recFindMin(array,i));
				 selSort(array,i+1,length); 
		} 
}	 


int recFindMin (int array[], int index)
{
    int local;
    if (index == 0)
    {
        return array[index];
    }

    local = recFindMin(array, index - 1);
    if (array[index] > local)
    {
        return local;
    }
    else
    {
        return array[index];
    }
}

void swap(int num[],int i,int j)
{
int temp;
temp=num[i];
num[i]=num[j];
num[j]=temp;
}

what is the problem in the void selSort(int array[], int i ,int length) algorithm
??

Do you really think it will swap when you are comparing array indices instead of the values in the function that calls swap(); and btw there's no ned for recSelSort().

thats how the algorithm was presented to me

what is the correct algorithm

my code is exactly like these words
The algorithm works as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)

it start from index 0 etc..
where is the problem

i sorted it
but there is a line i am corcerned abou
i marked it by "// what about this line " comment
,i need to return the index of local not local itself??
how to return its index
??

Code:

#include <stdio.h>
void recSelSort(int array[],int length);
void selSort(int array[], int i ,int length);
void swap(int num[],int i,int j);
int recFindMin(int array[], int index);

int main()
{
    int array[4] = {2, 1, 3,0};

	recSelSort(array,4);
    printf("%d,%d,%d,%d\n", array[0],array[1],array[2],array[3]);

    return 0;
}

 void recSelSort(int array[],int length)
{
	selSort(array,0,length);
} 

// sort array from i (till i is sorted and min)
 void selSort(int array[], int i ,int length)
{    
		if (i<length)
             {
				 swap(array,i,recFindMin(array,i));
				 selSort(array,i+1,length); 
		} 
}	 


int recFindMin (int array[], int index)
{
    int local;
    if (index == 0)
    {
        return index;
    }

    local = recFindMin(array, index - 1);
    if (array[index] > local)
    {
        return local;  // what about this line 
    }
    else
    {
        return index;
    }
}

void swap(int num[],int i,int j)
{
int temp;
temp=num[i];
num[i]=num[j];
num[j]=temp;
}

Originally Posted by transgalactic2

my code is exactly like these words
The algorithm works as follows:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)

it start from index 0 etc..
where is the problem

If this is your algorithm you have to use recursion then you also need a loop to walk along the array starting from index 0, incrementing at each stage after min is found.

i solved it look
at post #23
is it ok?

i found an example for which my previous code is not working
so i changed it to
and its still doesnt sort

Code:

#include <stdio.h>
void recSelSort(int array[],int length);
void selSort(int array[], int i ,int length);
void swap(int num[],int i,int j);
int recFindMin(int array[], int index);

int main()
{
    int array[4] = {2, 1, 3,0};

	recSelSort(array,3);
    printf("%d,%d,%d,%d\n", array[0],array[1],array[2],array[3]);

    return 0;
}

 void recSelSort(int array[],int length)
{
	selSort(array,0,length);
} 

// sort array from i (till i is sorted and min)
 void selSort(int array[], int i ,int length)
{    
		if (i<length)
             {
				 swap(array,i,recFindMin(array,i));
				 selSort(array,i+1,length); 
		} 
}	 


int recFindMin (int array[], int index)
{
    int local;
    if (index == 0)
    {
        return index;
    }

    local = recFindMin(array, index - 1);
    if (array[index] >array[local])
    {
        return local;  // what about this line 
    }
    else
    {
        return index;
    }
}

void swap(int num[],int i,int j)
{
int temp;
temp=num[i];
num[i]=num[j];
num[j]=temp;
}

is it from the assignment by zion siksik ?

Originally Posted by transgalactic2

i solved it look
at post #23
is it ok?

so does it work or not? imo it's not complicated despite its recursive twist and the fact that recursive function calls have to be used as a substitute for the loop index.

it doesnt work

i dont know where is the problem

i changed it
iits not sorting at all

Code:

#include <stdio.h>
void recSelSort(int array[],int length);
void selSort(int array[], int i ,int length);
void swap(int num[],int i,int j);
int recFindMin(int array[], int index);

int main()
{
    int array[4] = {2, 1, 3,0};

	recSelSort(array,3);
    printf("%d,%d,%d,%d\n", array[0],array[1],array[2],array[3]);

    return 0;
}

 void recSelSort(int array[],int length)
{
	selSort(array,length-1,length);
} 

// sort array from i (till i is sorted and min)
 void selSort(int array[], int i ,int length)
{    
		if (i<length)
             {
				 swap(array,i,recFindMin(array,i));
				 selSort(array,i-1,length); 
		} 
}	 


int recFindMin (int array[], int index)
{
    int local;
    if (index == 0)
    {
        return index;
    }

    local = recFindMin(array, index - 1);
    if (array[index] >array[local])
    {
        return local;  // what about this line 
    }
    else
    {
        return index;
    }
}

void swap(int num[],int i,int j)
{
int temp;
temp=num[i];
num[i]=num[j];
num[j]=temp;
}