Selection Sort Problem?

**dcwang3** · 11-05-2008

I'm having a problem with my code that deals with selection sort...
For some reason it works for some examples, but it does not work for others, check below:

It satisfies some test examples...This is the example the professor gave us...

6, 3, 7, 86, 2 ----> output is 2, 3, 6, 7, 86 (So this works)

But some other test examples don't work and some do like

100, 2, 24, 86, 1 -----> output is 1, 2, 86, 24, 100 (does not work)

-30, 5, 23, -2, 100, -65 ----> output is -65, -30, -2, 5, 23, 100 (works)

-100, 65, 2, -42, 16 -----> output is -100, 2, 16, -42, 65 (does not work)

So I cannot see where there is a problem in my code. It seems like it is sort of random...

Code:

#include<stdio.h>
#define N 20

void sort(int* const p, int len);
void swap(int* const p, int a, int b);

void sort(int* const p, int len)
{
  int i, x, y, index_of_min;

  for(x=0; x<len; x++)
    {
      index_of_min = x;

      for(y=x; y<len; y++)
        {
          if(*(p+index_of_min) > *(p+y))
            index_of_min = y;

          swap(p, x, index_of_min);
        }
    }

  printf("\nThe sorted elements of array are:\n");

  for(i=0; i<len; i++)
    {
      printf("%d, ", *(p+i));
    }

}

void swap(int* const p, int x, int index_of_min)
{
  int temp;

  temp = *(p+x);

  *(p+x) = *(p + index_of_min);

  *(p + index_of_min) = temp;

}

int main(void)
{

  int i, length;
  int array[N] = {0};

  printf("\nInput the length of array: ");
  scanf("%d", &length);

  printf("Input the elements of array\n");

  for(i=0; i< length; i++)
    {
      printf("\nElement %d:  ", i);
      scanf("%d", &array[i]);
    }

  printf("\nThe input elements of the array are:\n");

  for(i=0; i< length; i++)
    {
      printf("%d", array[i]);
      printf(", ");
    }

  sort(array, length);

  printf("\n\n");

  return(0);

}

Thanks

Also, the assignment calls for the index address of the pointers not be modified thus that is why the parameters in the functions are the way they are: int* const p

**zacs7** · 11-05-2008

You didn't do anything we mentioned in your other thread, http://cboard.cprogramming.com/showthread.php?t=108848

There should be N-1 swaps, where N is the number of elements in your array to be sorted.

So far you have a retarded bubble/selection sort

**dcwang3** · 11-05-2008

well, if you look at my other post, I'm trying to switch over to using real pointers. But as of right now, I'm trying to fix that part of the code in this way, then I'm going to try and translate it into pointers (and not using *(p+i) notation)....

I tried changing the swaps, but it doesn't work. It either puts it at the very front for some numbers or it doesn't swap at all... I don't know, it is weird.

Any suggestions in fixing?

**tabstop** · 11-05-2008

Then you need to try changing the swaps in the way we suggested: NOT inside the y for-loop, but after it, still inside the x for-loop.

**dcwang3** · 11-05-2008

i got it working now...here is my code

Code:

#include<stdio.h>
#define N 20

void sort(int* const p, int* const pend);
void swap(int* const p, int* const pmin);

void sort(int* const p, int* const pend)
{
  int *pp = p;

  for( ; pp < (pend - 1); pp++)
    {
      int *q, *pmin = pp;

      for( q = pp + 1; q < pend; q++)
        {
          if (*pmin > *q)
            pmin = q;
        }

      swap(pp, pmin);
    }

}

void swap(int* const p, int* const pmin)
{
  int temp;

  temp = *p;

  *p = *pmin;

  *pmin = temp;

}

int main(void)
{

  int i, length;
  int array[N] = {0};

  printf("\nInput the length of array: ");
  scanf("&#37;d", &length);

  printf("Input the elements of array\n");

  for(i=0; i< length; i++)
    {
      printf("\nElement %d:  ", i);
      scanf("%d", &array[i]);
    }

  printf("\nThe input elements of the array are:\n");

  for(i=0; i< length; i++)
    {
      printf("%d", array[i]);
      printf(", ");
    }

  sort(array, array+length);

  printf("\nThe sorted elements of array are:\n");

  for(i=0; i<length; i++)
    {
      printf("%d, ", array[i]);
    }

  printf("\n\n");

  return(0);

}

thanks anyways

**Matus** · 11-05-2008

Originally Posted by dcwang3

i got it working now...here is my code

thanks anyways

I got a way shorter version, does the same and the code aint that complicated, involves simple two swaping, let me know if u want a look

**dcwang3** · 11-05-2008

yeah if you could post it so I can compare, that would be great. thanks

**Matus** · 11-05-2008

Originally Posted by dcwang3

yeah if you could post it so I can compare, that would be great. thanks

This is my Version of the selectionsort, along with a swap function: The rest on how ud call it etc i leave up to you:

Code:

By: A . Matus


void selectionSort( int array[], int length )
{
   int smallest;        //lowest value element
   int x;              //used in for loop
   int z;             //used in for loop
   int numSwaps=0;    //count number of swaps
    
   /* loop over length - 1 elements */
   
   for ( x = 0; x < length - 1; x++ ) {
      smallest = x;   /* first index of remaining array */
        
      /* loop to find lowest value element */
      
      for ( z = x + 1; z < length; z++ ){
         if ( array[ z ] < array[ smallest ] )   {    
                
        swap( &array[z],&array[smallest] ); /* swap smallest element */

        numSwaps++; // increment num of swaps everytime it occurs
        
        } // end if
      } // end inner for
   } /* end for */
   
   printf("Number of swaps is %d\n",numSwaps);

} /* end function selectionSort */


void swap( int *_1stPtr, int *_2ndPtr )
{
   int hold = *_1stPtr;
   *_1stPtr = *_2ndPtr;
   *_2ndPtr = hold;
   
} /* end function swap */

**dcwang3** · 11-05-2008

your's is sort of like mine, it's just my code has some additional things to satisfy the requirements in my assignments.

thanks for posting!

**Matus** · 11-05-2008

Originally Posted by dcwang3

your's is sort of like mine, it's just my code has some additional things to satisfy the requirements in my assignments.

thanks for posting!

Haha ok no prob man. Me n matts gona have a discussion on this algorithm in a while, feel free to join us in a bit. Try to make it faster and better Actually yea ur code is, sorry man didnt really go over it, i just saw the thread and responded, my bad

**zacs7** · 11-05-2008

Why use int instead of size_t?

As-if this isn't 99x easier to read:

Code:

void selection_sort(int * array, size_t n)
{
   size_t   i = 0,
            min = 0;
   
   for(i = 0; i < n - 1; i++)
   {
      min = find_min(array, n, i);
      swap(array, min, i);
   }
}

**~~master5001~~** · 11-05-2008

My brain can comprehend properly indented code better. Matus, can you check out the PM I sent... Ayuda?

Code:

void selectionSort( int array[], int length )
{
   int smallest, x, z, numSwaps;

   --length;
    
   for (numSwaps = 0, x = 0; x < length;)
   {
      smallest = x;
        
      for ( z = ++x; z < length; ++z)
      {
         if ( array[ z ] < array[ smallest ] )
         {                  
            swap( &array[z],&array[smallest] );
            ++numSwaps;
         }
      }
   }
   
   printf("Number of swaps is &#37;d\n",numSwaps);

}

[edit]I don't like other people's comments either... [/edit]

**~~master5001~~** · 11-05-2008

That isn't the best nor most efficient sort. But it sorts, and it fits the criteria for what the OP was wanting. Though I must say iMalc is the goto guy for sorting algorithm optimization.

**Matus** · 11-05-2008

Originally Posted by master5001

My brain can comprehend properly indented code better. Matus, can you check out the PM I sent... Ayuda?

[code]

[edit]I don't like other people's comments either... [/edit]

haha ok, i know my indentation isnt the best. Umm ill read on what u have, ill make corrections if any is needed. Meanwhile i was gona talk bout the selectionsort in this way, identify the lowest value which is done there, but why not identify the last value as the highest go about looping down the array until a higher element is found and then swap again, but at the same time swapping the lowest values instead. Prof calls it two tails sort, hence, while that is done ull have two swaps occuring at the same time, hence minimizing number of swaps in a way and time. I have the idea, i tried including the statements additional in the for, but the to swap i had a bit of confusion. Would like to hear ur ideas on how ud go about doin it.

**zacs7** · 11-05-2008

> sorting algorithm optimization
The easiest optimization is to ditch this O(N^2) sort and go for something faster. Perhaps quick-sort or merge-sort.

Thread: Selection Sort Problem?

Thread Tools

Search Thread

Display

Selection Sort Problem?

Similar Threads

linked list sort with variable struct selection field

Straight Insertion Sort function problem

heap sort problem

Sorting problem.. well actually more of a string problem

need suggestions for problem involving selection based on file read