Thread: Selection Sort Problem?

Then perhaps a merge-selection-sort is in order :-)

Originally Posted by master5001

Touche. It would be better and still be a selection-sort Good thinking.

Aha, well what i was saying was do the same selection sort but find high and low values and swap them in that one loop. I know there are other methods, but this was just a thing to modify selectionsort and make it a bit better

Originally Posted by zacs7

Then perhaps a merge-selection-sort is in order :-)

Ya, i just read wht u had, makes sense got it!

Parts of the original post omitted ...

Originally Posted by Matus

This is my Version of the selectionsort

Code:

   for ( x = 0; x < length - 1; x++ ) {
      smallest = x;   /* first index of remaining array */
        
      /* loop to find lowest value element */
      
      for ( z = x + 1; z < length; z++ ){
         if ( array[ z ] < array[ smallest ] )   {    
                
        swap( &array[z],&array[smallest] ); /* swap smallest element */

        numSwaps++; // increment num of swaps everytime it occurs
        
        } // end if
      } // end inner for
   } /* end for */

Unfortunately that's not Selection Sort, you've got an item swap inside the inner loop. It's what I've seen called "Simple Sort".
The idea of Selection Sort is that you select the lowest or highest item each time without moving any items in the process, and then only when you've found that lowest or highest item, do you actually swap anything.
It's supposed to be similiar to what you'd do if you had to say, physically line up a whole lot of vehicles in order of weight. You really don't want to move any vechicles more than you have to. This is where the strength of Selection Sort lies.

The easiest way to go from an O(n*n) sorting algorithm to something almost as simple as Bubble Sort, yet much better in terms of Big-Oh-Notation, is undoubtedly to choose Comb Sort.
Whether I'd recommend using anything better than that though depends on how many items you're sorting for starters.

Originally Posted by iMalc

Parts of the original post omitted ...

The easiest way to go from an O(n*n) sorting algorithm to something almost as simple as Bubble Sort, yet much better in terms of Big-Oh-Notation, is undoubtedly to choose Comb Sort.
Whether I'd recommend using anything better than that though depends on how many items you're sorting for starters.

ok call it that, however my idea was to have two swaps at the same time. Simple sort is supposed to be O(n-1) right, but what i wanted was to make it something that makes two comparisons at the same time, i looked at the merge sort but its not really what i wanted. Id be breaking into two and so on, the idea behind this was to identify the highest and lowest values and swap in one loop both items.

Originally Posted by Matus

ok call it that, however my idea was to have two swaps at the same time. Simple sort is supposed to be O(n-1) right, but what i wanted was to make it something that makes two comparisons at the same time, i looked at the merge sort but its not really what i wanted. Id be breaking into two and so on, the idea behind this was to identify the highest and lowest values and swap in one loop both items.

All the basic sorts like Bubble, Selection, Insertion, Shaker, Odd-Even-Transposition and this one, are O(n*n).
When you get upwards of say 10000 items, it really hurts performance using such an algorithm.

Originally Posted by master5001

>> the idea behind this was to identify the highest and lowest values and swap in one loop both items.

So you are wanting to sort from highest to lowest, simulataneously with lowest to highest? Right? Again, this is iMalc's specialty moreso than mine but I don't think you would be gaining anything since you would fundamentally be O(2n^2).

Ya never mind the question, its for extra points thats what my class is on right now, digging extra points. Hence im close to finishing.

Originally Posted by master5001

What specifically are you trying to do? Friends don't give friends O(2n^2) code.

ya i know, we've gone over quicksort too which is way better. Like i had said the idea was to pick out first and last elemente with each low and high points. Loop around, and everytime it encounters one bigger and smaller in the array on ints swap them. So instead of having one swap like in selection sort one would have two swaps. Hence the prof name " a little improved selectionsort called "two tail sort". Dnt know if it makes anysense.

Originally Posted by iMalc

All the basic sorts like Bubble, Selection, Insertion, Shaker, Odd-Even-Transposition and this one, are O(n*n).
When you get upwards of say 10000 items, it really hurts performance using such an algorithm.

Hey thanks to Matt found ur site, pretty awesome, saw ur executable for the dif algorithms, pretty neat indeed. Posted in our Class Blogs so the others can see, u got credits for it too so dw!