Selection Sort Problem?

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

You didn't do anything we mentioned in your other thread, Need Help with Pointers...

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

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?

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.

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

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

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

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 */

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!

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

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

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]

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.

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.

> 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.