10 Replies - 2253 Views - Last Post: 14 April 2012 - 04:00 PM Rate Topic: -----

#1 Courtney2012  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 50
  • Joined: 16-March 12

selection sort

Posted 11 April 2012 - 08:17 PM

I am taking an online course and have just submitted an assignment on selection sorting. I sored 70% and in the submission box my teacher typed "Too many switches in the selection sort ... switch after you've found the lowest overall value."

I am hoping that someone may be able to inlighten me on what he means by switches. is he talking about the second for statement?

public void selectionSort()
    {   
        for (int i=0; i<x.length-1; i++) {
            
            for (int j=i+1; j<x.length; j++) {
                
                    if (x[i] > x[j]) {
                        
                        int temp = x[i];
                        x[i] = x[j];
                        x[j] = temp;
                    }
            }
        }
        
        for(int i = 0; i < x.length; i++){
            System.out.println(x[i]);
        }
    }


Is This A Good Question/Topic? 0
  • +

Replies To: selection sort

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2250
  • View blog
  • Posts: 5,340
  • Joined: 10-September 10

Re: selection sort

Posted 11 April 2012 - 08:37 PM

The general algorithm for selection sort is:

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

What you've done is closer to a bubble sort, swapping adjacent values each time the next one is less than the previous.
Was This Post Helpful? 1
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: selection sort

Posted 11 April 2012 - 09:09 PM

View PostCourtney2012, on 11 April 2012 - 11:17 PM, said:

I am taking an online course and have just submitted an assignment on selection sorting. I sored 70%

Not bad if the assignment was a selection sort and you submitted a bubble sort :) Yur teacher is really leniant
Was This Post Helpful? 0
  • +
  • -

#4 Courtney2012  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 50
  • Joined: 16-March 12

Re: selection sort

Posted 12 April 2012 - 01:59 PM

Yes pbl, he is a very nice man.

Thank you for your help Greg Brannon.
Was This Post Helpful? 0
  • +
  • -

#5 Courtney2012  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 50
  • Joined: 16-March 12

Re: selection sort

Posted 12 April 2012 - 08:52 PM

View PostGregBrannon, on 11 April 2012 - 08:37 PM, said:

What you've done is closer to a bubble sort, swapping adjacent values each time the next one is less than the previous.


Mr. Brannon, is this any better?

public  void SelectionSort2( int [ ] num )
    {
     int i, j, first, temp;  
     for (i = num.length - 1; i > 0; i--)  
     {
          first = 0;
          for(j = 1; j <= i; j ++)
          {
               if( num[ j ] < num[ first ] )         
                 first = j;
          }
          temp = num[ first ];
          num[ first ] = num[ i ];
          num[ i ] = temp; 
      }           
    }

Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: selection sort

Posted 12 April 2012 - 09:03 PM

If you want it in reverse order yup :^:
Was This Post Helpful? 0
  • +
  • -

#7 Courtney2012  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 50
  • Joined: 16-March 12

Re: selection sort

Posted 12 April 2012 - 10:53 PM

Thats odd... cause it sorts in asending order for me.
Was This Post Helpful? 0
  • +
  • -

#8 Casper1  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 12-April 12

Re: selection sort

Posted 12 April 2012 - 11:13 PM

In selection sorting, you take the first value in the array and compare it with the rest of the values going from the second position to the end. Each time the constant (first) value is bigger than the the value you are currently comparing it with, interchange their positions. In this manner, compare the first value with the rest of the values.

And when that's done, repeat the process for the second value. Compare it with the third, fourth values and so on, i.e. the ones coming after it. Likewise, for every other value apart from the last one. So in this manner, each time you move one value ahead, the number of iterations that the inner loop does decreases by one because it compares with one less value.

For the last value in the array, you don't need to compare it with anything. By the time you reach it, it would already have been the biggest value in your list.

This works if you want your array in ascending order. If what you want is descending order, then you swap if the value at an index is less than any of the values falling after it in the array, i.e. the comparing condition will be reversed.

This works if you want your array in ascending order. If what you want is descending order, then you swap if the value at an index is less than any of the values falling after it in the array, i.e. the comparing condition will be reversed.
Was This Post Helpful? 1
  • +
  • -

#9 Casper1  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 12-April 12

Re: selection sort

Posted 12 April 2012 - 11:18 PM

I think what your instructor meant by "switch" was swap, i.e. interchanging values. Your algorithm describes bubble sort, which is also correct but involves too many swaps and thus consumes a bit more of time and memory.
Was This Post Helpful? 1
  • +
  • -

#10 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2250
  • View blog
  • Posts: 5,340
  • Joined: 10-September 10

Re: selection sort

Posted 13 April 2012 - 01:14 AM

If it works, it works, but at a quick glance it appears that you're moving the least value found during each iteration to the last element in the array. In a typical algorithm, the outer loop would begin at the first element, and the inner loop would begin at the element one index greater than the outer loop, and the pointer, first, would not be required.

Looking at the steps I posted above:

1. Find the minimum value in the list
2. Swap it (the minimum value) with the value in the first position

There are at least 2 ways to do that: 1) go through the whole list, identify the index of the element with the least value, then swap the value at the first index with the value at the index with the least value; or 2) go through the whole list and each time a value is found to be less than the value at the first index, swap them.

The second approach seems to be favored. The setup for the second approach is:

start = 0;
for ( i = start ; i < listLength - 1 ; i++ )
{
   for ( j = i + 1 ; j < listLength ; j++ )
   {
      if ( list[j] < list[i] )
      {
         // swap the values at indices i and j
      }
   }
   start++
}

Edit: I had to dash before I could add:

I have no basis for my "#2 is favored" comment other than an unscientific analysis of a very small sample, but there are differences in the two approaches worth noting.

The first approach will result in the absolute minimum number of swaps. Considering the worst case input, a list with the elements sorted in reverse order, the number of swaps will be the number of elements minus 1. The worst case number of swaps for the second approach will be ( x^2 + x ) / 2 where x = number of elements - 1.

Also, it's worth noting that the recursive potential of the selection sort algorithm in either form is very easy to visualize (for me, anyway). If you haven't learned recursion yet, when you get to it, come back to this problem and consider making it recursive. It may be slightly harder to implement than it is to visualize, but for me the visualization is often the hardest part.

As for one's first impression of the algorithm you posted, you've almost eliminated the need for or purpose of the outer i loop by using the "pointer" variable, first. If you incremented first before each pass through the j loop rather than resetting it to zero, then swapped if num[first] < num[j], you'd make the i loop redundant except as a limit on the number of passes. Setting first to j at line 10 complicates my previous statement, and then the way you do the swap is a bit more complicated than it needs to be (and confusing), but apparently it gets the job done. It's not simple, and it's not elegant, but we've all gotten wrapped around the axle writing more complicated code than was necessary in the pursuit of getting something to work.

This post has been edited by GregBrannon: 13 April 2012 - 03:09 AM

Was This Post Helpful? 3
  • +
  • -

#11 Courtney2012  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 50
  • Joined: 16-March 12

Re: selection sort

Posted 14 April 2012 - 04:00 PM

thanks for all of your help, it's starting to get alot cearer to me now. :smartass: :angel: :clap: :taz:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1