Thread: Selection sort, not sorting

  1. #1
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688

    Selection sort, not sorting

    Hi, this code compiles ok without any errors, but I am trying to sort an array of 10 integers into order using pointers. But when the output is produced It is printing them out the same as the original order. I looked over my code and cannot for the life of me see what I have done wrong

    Code:
    #include <iostream>
    
    // function prototypes
    void selectionSort ( int *const, const int );
    void swap ( int *const, int *const );
    
    // main function ///////////////////////////////////////////////////////////////
    //
    int main ( void )
    {
       const int arraySize = 10;
       
       int data[ arraySize ] = { 2, 3, 10, 7, 9, 1, 6, 4, 8, 5 };
       
       std::cout << "Orginal array:\n\n";
       
       for ( int i = 0; i < arraySize; i++ )
          std::cout << data[ i ] << " ";
          
       // send to function to sort array
       selectionSort ( data, arraySize );
       
       std::cout << "\n\nSorted array:\n\n";
       
       for ( int j = 0; j < arraySize; j++ )
          std::cout << data[ j ] << " ";
          
       std::cin.get(); // freeze console window output
    	 	 
       return 0; // indicate program terminated sucessfully
    }
    
    // function to sort the passed array
    void selectionSort ( int *const array, const int size )
    {
       int smallest; // insez of smallest element
       
       // loop over size -1 elements
       for ( int i = 0; i < size - 1; i++ )
       {
          smallest = i; // first index of remaining array
          
          // loop to find index of smallest element
          for ( int index = i + 1; index < size; index++ )
          {
             if ( array[ index ] < array[ smallest ] )
                smallest = index;
             
    			// pass address of each array element to awap function   
             swap ( &array[ i ], &array[ smallest ] );
          }
       }
    }
    
    // function to swap values at memoty locations
    // to which element1Ptr and element2Ptr point
    void swap ( int *const element1Ptr, int *const element2Ptr )
    {
       int hold = *element1Ptr;
       *element1Ptr = *element2Ptr;
       *element2Ptr = hold;
    }
    Double Helix STL

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I believe you should do the swap after the inner loop has completed (i.e., you have found the minimum in the unsorted subarray), not within it.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    I have run your code just now! Its working fine!

    OUTPUT GIVEN:-

    Orginal array:

    2 3 10 7 9 1 6 4 8 5

    Sorted array:

    1 2 3 4 5 8 6 9 7 10

    Press Enter to return to Quincy...

  4. #4
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Thanks laserlight, that sorted the problem. I knew I was almost correct. Thanks again

    edit: anirban. I did not get that output first time, what compiler does Quincy use?
    Double Helix STL

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Well, anirban's output is not correct after all. The whole point of selection sort is to move the smallest element of a range to its correct place in one swap, therefore just one swap per outer loop. When you did it in the inner loop, you probably lost track what was the smallest element and moved things around quite randomly.

  6. #6
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    What do u mean by not correct???? The "mingw" compiler has compiled it wrong?

    swgh : It uses mingw compiler...Although the IDE is a very non-professional one. I personally use CODE BLOCKS.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I compiled swgh's original code using the MinGW port of g++ 3.4.2, and my result was:
    1 2 3 4 5 8 6 9 7 10

    Anyway, even if by some chance the output turned out to be correct, it would just be a coincidence. Even a broken clock tells the correct time twice a day.
    Last edited by laserlight; 04-23-2007 at 09:55 AM. Reason: Haha, I wrote down the compiler that I wanted to install, not the one I currently have :p
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    What do u mean by not correct???? The "mingw" compiler has compiled it wrong?
    ... 8 6 9 7 10 does not look particularly well sorted, does it? The compiler is OK, the algorithm is wrong.

  9. #9
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Sorry for not posting again to this thread but I had to run an errand. I sorted the problem by reading my code line by line and going by suggestions made here. The problem was that I had incorrectly placed braces after the final for loop in function selectionSort():

    Code:
    for ( int index = i + 1; index < size; index++ )
          { // removed this
             if ( array[ index ] < array[ smallest ] )
                smallest = index;
             
    			// pass address of each array element to awap function   
             swap ( &array[ i ], &array[ smallest ] );
          } // removed this
    I took away the braces commented above, and the sort algorithm worked perfectly. By taking the swap function call out of the for loop code block, I was able to make the program sort the array correctly. Thanks for all replies.
    Double Helix STL

  10. #10
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Sorry "anon" i did not see the whole output sequence!

  11. #11
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    Yes "swgh" you are right! The algorithm is right now!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Insertion and selection sort
    By Dashing Boy in forum C Programming
    Replies: 4
    Last Post: 08-29-2006, 04:42 PM
  2. Sorting an array of structures with sort()
    By rmullen3 in forum C++ Programming
    Replies: 3
    Last Post: 01-03-2003, 03:02 PM
  3. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM