Selection sorting algorithm

This is a discussion on Selection sorting algorithm within the C++ Programming forums, part of the General Programming Boards category; Selection sort scans an array of ints to find the smallest, then replaces the first element with the smallest. When(if) ...

  1. #1
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640

    Selection sorting algorithm

    Selection sort scans an array of ints to find the smallest, then replaces the first element with the smallest. When(if) that happens, the routine continues again but this time excluding the first element(which is now the smallest), and so on.

    When I run the program, I get this:
    Code:
    { 3 4 6 5 8 8 65 13 66 748 }
    the code:
    Code:
    #include <iostream>
    using namespace std;
    const int MAX_ELEMENTS = 10;
    void selsort(int [], int);
    int main()
    {
        int unsorted[MAX_ELEMENTS] = {5,3,748,6,8,65,8,66,4,13};
                                    //3,4,5,6,8,8,13,65,66,748
        selsort(unsorted, 0);
        cout << "{ ";
        for (int i=0; i<MAX_ELEMENTS; i++)
        {
            cout << unsorted[i] << " ";
        }
        cout << "}" << endl;
        cin >> unsorted[0];
        return 0;
    }
    
    void selsort(int array[], int loc)
    {
        if (loc == (MAX_ELEMENTS-1))
            return;
        int tmp = 0;
        for (int i=loc; i<MAX_ELEMENTS; i++)
        {
            if (array[i] < array[loc])
            {
                tmp = array[loc];
                array[loc] = array[i];
                array[i] = tmp;
                selsort(array, loc + 1);
            }
        }
        //if (locsmall == 0)
        //    return;
    }
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  2. #2
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Why did you change it? It was right except for one small thing (I pointed to the line with the problem as a hint in the other thread).

  3. #3
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    There was no need for the locsmall, so it doesn't matter now, I just took it out. What is the problem with locsmall being set to 0?
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  4. #4
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Since you initially set small to the value at array[loc], then you should have initially set locsmall to loc. When I did that with your original code, the data was sorted correctly.

    The first algorithm was: Look at all values after the passed in location and find the smallest remaining value. Then, swap the current location with the smallest remaining that was just found. Recurse on the next location. I don't know if that's selection sort, but it works.

    The new algorithm is: For each element after the current location, if that element is smaller, immediately swap it and then recursively sort the rest of the array. The problem with that is that after two positions have been compared, its possible that different values can get swapped into the positions that are no longer in the correct order (I believe that is what is happening here). Here are the swaps I get for your new code:

    5, 3, 748, 6, 8, 65, 8, 66, 4, 13
    3, 5, 748, 6, 8, 65, 8, 66, 4, 13
    3, 4, 748, 6, 8, 65, 8, 66, 5, 13
    3, 4, 6, 748, 8, 65, 8, 66, 5, 13
    3, 4, 6, 8, 748, 65, 8, 66, 5, 13
    3, 4, 6, 8, 65, 748, 8, 66, 5, 13
    3, 4, 6, 8, 65, 8, 748, 66, 5, 13
    3, 4, 6, 8, 65, 8, 66, 748, 5, 13
    3, 4, 6, 8, 65, 8, 66, 5, 748, 13
    3, 4, 6, 8, 65, 8, 66, 5, 13, 748
    3, 4, 6, 8, 65, 8, 13, 5, 66, 748
    3, 4, 6, 8, 65, 5, 13, 8, 66, 748
    3, 4, 6, 8, 65, 5, 8, 13, 66, 748
    3, 4, 6, 8, 8, 5, 65, 13, 66, 748
    3, 4, 6, 5, 8, 8, 65, 13, 66, 748

    Notice how in the fourth row, the third spot (6) is now less than the fourth spot (748). Later, 5 gets moved into the fourth spot, but the algorithm has already compared the third and fourth spots and so it assumes they are still in order, leaving the 5 after the 6 in the array.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting Algorithm Help
    By cjwenigma in forum C++ Programming
    Replies: 8
    Last Post: 11-02-2007, 02:04 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. which sorting algorithm for GBs of data?
    By Sargnagel in forum C Programming
    Replies: 4
    Last Post: 06-05-2003, 08:43 AM
  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

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