Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: optimized selection sort

  1. #1
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default optimized selection sort

    Hi, I'm reading up on Wikipedia and it uses shaker sort is optimization, are they actually 2 different algorithms. I can't seem to find it when I google for optimized selection sort. I thought shaker sort was bi-directional bubble sort (at each iteration, current largest and current smallest put in their proper place)


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: optimized selection sort

    A bidirectional variant of selection sort, called cocktail sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. This reduces the number of scans of the list by a factor of 2, eliminating some loop overhead but not actually decreasing the number of comparisons or swaps. Note, however, that cocktail sort more often refers to a bidirectional variant of bubble sort.
    Sounds like they're two distinct algorithms.

  3. #3
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: optimized selection sort

    So many dumb names when I looked it up in Wikipedia which makes it confusing, but to make sure I'll use these terms:

    1) bi-directional bubble sort: alternate going thru list from both ends until no swaps needed (a flag)
    2) optimized selection sort: need to find the min and max values so linear time to find both these values, then we put them in their final places, is this right?


    eg of bi-directional bubble sort:
    [2,3,4,5,1]

    pass 1: [2,3,4,1,5] (now start at end of unsorted list towards the front of list/array for next pass, swap needed to move 1 to front of list for pass 2)
    pass 2: [1, 2,3,5] (now start at front of unsorted list towards end of unsorted list for next pass, no swap so done because we have flag reset to no swap currently after pass 1 done (because pass 1 had flag of swap is true) )


    eg of optimized selection sort:
    [2,3,4,5,1], but if I find the min: 1, and find max: 5, am I supposed to put them in the current front and current end of list, because this would be bad because we need to shift other items over unless I'm not understanding optimized seleciton sort properly. Any help appreciated.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: optimized selection sort

    1) bi-directional bubble sort: alternate going thru list from both ends until no swaps needed (a flag)
    2) optimized selection sort: need to find the min and max values so linear time to find both these values, then we put them in their final places, is this right?
    Sounds right to me.

    With your [2,3,4,5,1] example, you could define a special case where the number of indices involved is 3. Keep track of the 3 values, then place the min at the beginning, the max at the end, and the remaining value into the middle index, resulting in [1,3,4,2,5]. The min/max search space then decreases by 2 and repeats.

    There might be a better way to implement the selection sort variant.

Similar Threads

  1. How to call a C sort function to sort a Java Array.
    By Dwere13 in forum Java Native Interface
    Replies: 22
    Last Post: July 12th, 2012, 05:44 PM
  2. [SOLVED] Selection sort not working
    By killer3p0 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: May 7th, 2012, 01:24 PM
  3. Counting basic operations in this Selection Sort
    By Keiran in forum Algorithms & Recursion
    Replies: 2
    Last Post: February 1st, 2012, 07:16 PM
  4. Selection sort code needs reverse
    By steel55677 in forum Algorithms & Recursion
    Replies: 7
    Last Post: September 27th, 2011, 07:40 AM
  5. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 10:44 AM