Selection Sort Problem?

This is a discussion on Selection Sort Problem? within the C Programming forums, part of the General Programming Boards category; I'm having a problem with my code that deals with selection sort... For some reason it works for some examples, ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    116

    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

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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
    Last edited by zacs7; 11-05-2008 at 03:02 PM.

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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

  6. #6
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by dcwang3 View Post
    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
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  7. #7
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    yeah if you could post it so I can compare, that would be great. thanks

  8. #8
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by dcwang3 View Post
    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 */
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  9. #9
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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!

  10. #10
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by dcwang3 View Post
    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
    Last edited by Matus; 11-05-2008 at 07:15 PM.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  11. #11
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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);
       }
    }
    Last edited by zacs7; 11-05-2008 at 07:23 PM. Reason: Nevermind, you did it an "odd" way.

  12. #12
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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]
    Last edited by master5001; 11-05-2008 at 07:24 PM.

  13. #13
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    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.

  14. #14
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by master5001 View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  15. #15
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > 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.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 01-17-2009, 09:48 PM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 03:54 AM
  4. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  5. Replies: 0
    Last Post: 02-05-2002, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21