recursive selection sort..

i built this code exactly like in the theory
the min function works

where is the problem
why its not sorting
??

Code:

---

#include <stdio.h>
int min( int num[], int i, int j );
void swap(int num[],int i,int j);
void selection_sort(int arr[], int size);
void selSort(int array[], int i,int length);

int main()
{
        int array[3];
        array[0]=2;
        array[1]=6;
        array[2]=3;
    selection_sort(array,3);
    printf("%d,%d,%d\n",array[0],array[1],array[2]);

 

  return 0;
}



 
void selection_sort(int arr[], int size){
  selSort(arr,0,size);
}

void selSort(int array[], int i,int length)
{

        if (i<length)
            {                                 
                        swap(array,i,min(array,0,i));
                        selSort(array,i+1,length);
                }

}
 

 int min( int num[], int i, int j )
{
  if ( i > 0 )
{
  if ( num[i-1] < j )
{
  return min( num, i-1, num[i-1] );
}
else
{
  return min( num, i-1, j);
}
}
else
{
  return j;
}
}

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

---

Instead of going through so many hoops; the recursive min() you have is enough to sort the array provided you hand out pieces of it inside a for loop.

i cant use a for loop

only recurtion

when calling min inside min - the last parameter is an array value

when calling min inside sel_sort - the last parameter is an array index

this will not work together

you should think about better names for parameters than i,j

the min function works
i tried it
so i dont need to look inside it

the question is whether i implemented the algorithm of the main selection_sort(int arr[], int size)
and selsort
??

Quote:

---

Originally Posted by transgalactic2

the min function works
i tried it
so i dont need to look inside it

the question is whether i implemented the algorithm of the main selection_sort(int arr[], int size)
and selsort
??

---

it works when used correcly

you are using it incorrectly

how am i supposed to use it in this algorithm?
the minimum function find the minimum from the starting index to the end index

thats what i did

where is the problem in the implementation of the algorithm
??

i did it like it was told here

http://en.wikipedia.org/wiki/Selection_sort

If I'm not mistaken you should find the minimum item in the unsorted part of the array, that is between num[i]...num[length], not num[0]...num[i].

And the minimum function appears to be wrong for reasons others have noted.

my min function is fine
this is an example of its working fine

Code:

---

#include <stdio.h>
int min( int num[], int i, int j );


int main()
{
        int array[3];
       
        array[0]=2;
        array[1]=6;
        array[2]=3;
   

printf("%d\n",min(array, 3,3));

 

  return 0;
}


//j is the last member in the array
//i is the number of cells
 
 int min( int num[], int i, int j )
{
if ( i > 0 )
{
if ( num[i-1] < j )
{
return min( num, i-1, num[i-1] );
} else {
return min( num, i-1, j);
}
} else {
return j;
}
}

---

i changed it to

Code:

---

swap(array,i,min(array,length,i));

---

but it keeps the array as it is

it does nothing with the array

Code:

---

#include <stdio.h>
int min( int num[], int i, int j );
void swap(int num[],int i,int j);
void selection_sort(int arr[], int size);
void selSort(int array[], int i,int length);

int main()
{
        int array[3];
        array[0]=2;
        array[1]=6;
        array[2]=3;
    selection_sort(array,3);
    printf("%d,%d,%d\n",array[0],array[1],array[2]);

 

  return 0;
}



 
void selection_sort(int arr[], int size){
  selSort(arr,0,size);
}

void selSort(int array[], int i,int length)
{

        if (i<length)
            {                                 
                        swap(array,i,min(array,length,i));
                        selSort(array,i+1,length);
                }

}
 

 int min( int num[], int i, int j )
{
  if ( i > 0 )
{
  if ( num[i-1] < j )
{
  return min( num, i-1, num[i-1] );
}
else
{
  return min( num, i-1, j);
}
}
else
{
  return j;
}
}

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

---

Try tracing the program with a debugger.

i did
it just doesnt swap anything

why?

And what will happen if you call it like

Code:

---

int main()
{
        int array[3];
       
        array[0]=2;
        array[1]=6;
        array[2]=3;
   

printf("%d\n",min(array, 3,0));

 

  return 0;
}

---

The min function is not correct. Sometimes the third argument is an index, other times it is an array value. You compare array values with indices. Also it appears like it would find the min in the entire array whereas it needs to do that only for the unsorted part of the array.

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;
}

---

Quote:

---

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 ?

Quote:

---

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;
}

---

You don't need recSelSort() and your swap() is misplaced. swap() belongs inside recFindMin() and selSort() should be used to move the min element forward but instead you're decrementing it.

Code:

---

selSort(array,i-1,length); /* i will never reach length which is the top level condition */

---

ok ill try to implement it

IMO the only functions you need to get the entire job done using only recursion are listed below with minor changes as in

Code:

---

void selSort(int array[], int i ,int length);
void swap(int num[],int i,int j);
int recFindMin(int array[], int index, int length);

---

selSort() is the top level function; its index i increments while length remains the same.
In recFindMin() index i remains the same while length decrements.

In case you are interested here's a pretty good guide to recursion http://faq.cprogramming.com/cgi-bin/...&id=1073086407
Any luck nailing down the current recursion sort?

i solved it :)

Quote:

---

Originally Posted by transgalactic2

i solved it :)

---

just curious to see what the final solution looks like?