Selection Sort

This is a discussion on Selection Sort within the C++ Programming forums, part of the General Programming Boards category; If you had this array to do a selection sort G B A H C the first pass would be ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Selection Sort

    If you had this array to do a selection sort G B A H C
    the first pass would be ABGHC
    the 2nd pass would be ABGHC
    the 3rd pass would be ABCHG
    the 4th pass would be ABCGH

    Why is the first and second pass the same?

  2. #2
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Is there any code associated with your post?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    No code

    I am just trying to figure out how the sort works

  4. #4
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Okay, then how do you know that each pass will be how you said they would? You must be using something to get that data.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    yes It was in my notes as a example but I do not understand how it is working

    yes I do not understand how it is working

  6. #6
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Do your notes say anything else about selection sorts? Personally, I don't know what they are. Maybe if you explained it to me a little I would understand.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  7. #7
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    No

    No

  8. #8
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Could you tell me ANY context information here? What kind of notes does the passage appear in? What is the general topic? How exactly is the data set out?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  9. #9
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    I googled for selection sorting, and I found out the algorithm. The data sequence you showed does not match the selection sort algorithm. Are you sure you copied the data correctly?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  10. #10
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    selection sort is one of the simplest sorts there is. The concept is simply find the min, store it, find the min, store it and so on. Your example doesn't change in a couple steps because the min already lives in the front of the searched area.

    GBAHC
    A*BGHC
    AB*GHC
    ABC*HG
    ABCG*H

    The asterisk represents a divider between the final area and the searched area. If you know what the algorithm is supposed to do, you can see why it doesn't change between a couple steps
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  11. #11
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    That's the right algorithm FYB, but the data still doesn't follow it. It SHOULD go like this:

    GBAHC
    A*GBHC
    AB*GHC
    ABC*GH
    ABCG*H
    ABCGH

    Drew's data seems to be doing more than just selection sorting.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  12. #12
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    Originally posted by bennyandthejets
    I googled for selection sorting, and I found out the algorithm. The data sequence you showed does not match the selection sort algorithm. Are you sure you copied the data correctly?
    It does actually. You may have found a linked list version of the algorithm? There is not a need to "swap" in the linked list version.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  13. #13
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    yes, based on your output, bennyandthejets I would say that you've found a linked list version. It's quicker to swap then it is to move the entire array down in the array version.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  14. #14
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Could you explain further the swapping method? I still don't see how consecutive swapping could get us these results.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  15. #15
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    Okay, I get it now. It's not consecutive, it just swaps the next min value with the first value left in the array. That's pretty ingenious.

    Problem solved I guess.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

Page 1 of 2 12 LastLast
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. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 07:27 PM
  3. Selection Sort help
    By Twigstar in forum C++ Programming
    Replies: 5
    Last Post: 06-26-2005, 08:39 PM
  4. Selection Sort
    By Bleueyes515 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2002, 08:33 PM
  5. selection sort records of chars
    By hew in forum C++ Programming
    Replies: 8
    Last Post: 04-23-2002, 03:49 PM

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