Selection Sort Problem?

This is a discussion on Selection Sort Problem? within the C Programming forums, part of the General Programming Boards category; Code: size_t find_min(int *array, size_t lastIndex) { size_t i; int min = INT_MAX; for(i = 0; i <= lastIndex; ++i, ...

  1. #16
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Code:
    size_t find_min(int *array, size_t lastIndex)
    {
      size_t i;
      int min = INT_MAX;
    
      for(i = 0; i <= lastIndex; ++i, ++array)
        if(*array < min)
          min = *array;
    
      return min;
    }
    Then incorporate calls to this function where you set "smallest"

  2. #17
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by zacs7 View Post
    > sorting algorithm optimization
    The easiest optimization is to ditch this O(N^2) sort and go for something faster. Perhaps quick-sort or merge-sort.
    True, but the OP has to use the sorting algorithm that the teacher demanded of the class.

  3. #18
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Then perhaps a merge-selection-sort is in order :-)

  4. #19
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Touche. It would be better and still be a selection-sort Good thinking.

  5. #20
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by master5001 View Post
    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
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  6. #21
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by zacs7 View Post
    Then perhaps a merge-selection-sort is in order :-)
    Ya, i just read wht u had, makes sense got it!
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  7. #22
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Parts of the original post omitted ...
    Quote Originally Posted by Matus View Post
    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.
    Last edited by iMalc; 11-06-2008 at 12:39 AM.

  8. #23
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by iMalc View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  9. #24
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Matus View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #25
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    >> 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).

  11. #26
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by master5001 View Post
    >> 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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  12. #27
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    What specifically are you trying to do? Friends don't give friends O(2n^2) code.

  13. #28
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by master5001 View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  14. #29
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Feel free to look at Malcolm's site. When it comes to sorting methods he really is one of the most knowledgeable on this forum. And indeed he did see the thread here. If anything you can always start your own. Threads about sorting algorithms capture his attention as if a moth near a flood light.

  15. #30
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by iMalc View Post
    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!
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 01-17-2009, 10:48 PM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 05:03 AM
  3. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  4. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  5. Replies: 0
    Last Post: 02-05-2002, 07:44 PM

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