Talk:Selection sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Computer science (Rated C-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 

selection sort[edit]

Why does the C implementation on the article page include that final for loop that moves all elements to the right? Isn't the correct algorithm meant to just swap data[i] and data[minimum] after it finds the minimum, like it shown below on this page? Seems to me the article is incorrect, and if noone has any objections i'll change it to the C implementation on this page. --Mullacy 02:23, 2 August 2006 (UTC)

Why is the evolved C implementation so bulky and commented? Since this is just an illustration of concept, why don't we just do the minimum value searching and the swapping all within the main loop?

I just removed the "evolved" C implementation and replaced the first implementation with a correct one. The first C implementation wasn't actually selection sort, it was bubble sort. I think the new C implementation addresses your concern. Flatline 02:42, 2005 Apr 5 (UTC)
It looks like the basic implementation is also a bubblesort implementation. I could probably correct it, but since I haven't touched Basic in 15 years, I'd rather let someone with more familiarity with the language take care of it. Flatline 12:00, 2005 Apr 5 (UTC)

An anonymous user deleted the "not" from "Selection sort is not a stable sort." I've reverted it as it made the article self-contradictory, i.e. the implementations here are not stable. If anyone knows of a selection sort implementation that is stable, please share it with the rest of us. -- Smjg 17:17, 5 Apr 2005 (UTC)

Selection sort done on a linked list can be made stable very easily. However, since the discussion of stable vs unstable is done in the context of an array, the selection sort is unstable. Flatline 16:29, 2005 Apr 6 (UTC)

I think this implementation is stable

public static void selectionSort (int[] numbers)
  {
     int min, temp, tempm;
     boolean b;
     for (int index = 0; index < numbers.length-1; index++)
     {b=false;
        min = index;
       for (int i=index;int[i]==int[index];i++){tempm=i}        // ater this change I think it is stable 
       for (int scan = index+1; scan < numbers.length; scan++)
       if (numbers[scan] < numbers[min])  
        {min = scan;b=true;}                                    
       if (b) {for(int i=index;i<tempm;i++)                  //and this
               {temp = numbers[index];
                numbers[index] = numbers[tempm];        
                number[tempm]=temp;}            

} // Swap the values

            temp = numbers[min];
            numbers[min] = numbers[index];
            numbers[index] = temp;
     }
  }


Evzen Fochr (efochr@seznam.cz)

Ignoring for the moment the obvious typos in it, the variant proposed above fails under this input, which for this example has previously been sorted alphabetically and must be stably sorted numerically:
2a 3b 2c 1d  (initial array)
1d 3b 2c 2a  (after pass #1)
1d 2c 3b 2a  (after pass #2)
1d 2c 2a 3b  (after pass #3, and final array)
Peristarkawan 01:42, 1 October 2007 (UTC)

For the purposes of stability, wouldn't it be sufficient to replace the line swap(a[i], a[min]); with if (a[i] != a[min]) swap(a[i], a[min]);, rather than the step mentioned in the Variations section? 137.205.139.228 16:43, 10 June 2007 (UTC)

No, swaps would still have the possibility of destroying the order of elements that haven't yet been selected yet. Consider this run:
2a 2b 1c  (initial array)
1c 2b 2a  (after pass #1, and final array)
Peristarkawan 01:42, 1 October 2007 (UTC)


Excessive implementations[edit]

As quicksort and insertion sort before it, this article is accumulating an excessive number of conceptually identical implementations. I will deal with this in the same way, by creating a separate article for implementations, and sharing a template between that article and this one giving a small number of conceptually different representative implementations. Deco 08:59, 11 December 2005 (UTC)

I've completed this. Please add Template:Selection sort core implementations to your watchlist, as this template is now transcluded in this article. I also added an Ocaml implementation, because the functional version is significantly different (and Ocaml seems to be the most popular functional language among mainstream programmers nowadays). Deco 10:26, 11 December 2005 (UTC)


The suggested stable implementation of selection sort given in this article is in fact just insertion sort! It is stable, but it's no longer selection sort..

Implementations[edit]

C[edit]

This is an implementation of the unstable variant:

int selectionSort(int data[], int count) {
        int i, j;
        int tmp;
        int minimum;
        for (i = 0; i < count - 1; i++) {
                minimum = i; /* current minimum */
                /* find the global minimum */
                for (j = i + 1; j < count; j++) {
                        if (data[minimum] > data[j]) {
                                /* new minimum */
                                minimum = j;
                        }
                }
                /* swap data[i] and data[minimum] */
                tmp = data[i];
                data[i] = data[minimum];
                data[minimum] = tmp;
        }
        return 0;
}

Java[edit]

This is an implementation of the unstable variant:

   public void orderAsc(int vector[]) {
      int i, j, min, x;
      for (i = 0; i < vector.length-1; i++) {
         min=i;
         for (j = i+1; j < vector.length; j++)
            if (vector[j] < vector[min])
               min = j;

         x = vector[i];
         vector[i] = vector[min];
         vector[min] = x;
      }
   }

This is an implementation of the stable variant:

   public void orderAsc(int vector[]) {
      int i, j, min, x;
      for (i = 0; i < vector.length-1; i++){
         min = i;
         for (j = i+1; j < vector.length; j++)
            if (vector[j] < vector[min])
               min = j;
                  
         x = vector[min];
         for (j = min; j > i; j--)
            vector[j] = vector[j - 1];
         vector[i] = x;
     }
  }

Haskell[edit]

This implementation is stable, as selectMinimum always extracts the earliest minimal element. If the comparison in selectMinimum is changed to strict inequality, the sort will be antistable, as the last minimal element will always be chosen.

selectMinimum [x] = (x,[])
selectMinimum (x:xs) =
    let (y,ys) = selectMinimum xs
    in if x <= y
          then (x, xs)
          else (y, x:ys)

selectionSort [] = []
selectionSort (x:xs) =
    let (y,ys) = selectMinimum (x:xs)
    in y : selectionSort ys

For sorting lists that contain many elements which compare equal, the following variant will do better, as it moves all minimal elements to the start of the list in one pass. It is also stable.

selectMinima [x] = ([x],[])
selectMinima (x:xs) =
    let ((m:ms),ys) = selectMinima xs
    in case compare x m of
          LT -> ([x], xs)
          EQ -> (x:m:ms, ys)
          GT -> (m:ms, x:ys)

selectionSort' [] = []
selectionSort' (x:xs) =
    let (ms,ys) = selectMinima (x:xs)
    in ms ++ selectionSort' ys

Ocaml[edit]

(* Gets the minimum element of the list *)
let rec min lst =
    match lst with
       x::[] -> x
     | (x::tl) -> let mintl = min tl in
                    if x < mintl then x else mintl;;

(* Removes a given element from the list *)
let rec remove(x,lst) =
    match lst with
       [] -> []
     | (y::tl) -> if x=y then tl else y::(remove(x,tl));;

(* Sorts a list by repeatedly extracting the minimum *)
let rec selectionSort(lst) =
    match lst with
       [] -> []
     | _  -> let m = min lst in m::(selectionSort(remove(m,lst)));;

LISP[edit]

 (defun select (l)
        (cond ((null (rest l)) (first l))
                  (t (let ((s (select (rest l))))
                         (if (< (first l) s) (first l) s)))))
 
 (defun selectsort (l)
        (cond ((null l) ())
                  (t (let ((s (select l)))
                         (cons s (selectsort (remove s l :count 1)))))))

Python[edit]

def selectionsort(l):
    for passesLeft in range(0,len(l)-1,+1):
        min   = passesLeft        
        for index in range(passesLeft+1,len(l),+1):
            if (l[index]<l[min]):
                min = index
        l[min] , l[passesLeft] = l[passesLeft] , l[min]        
    return l

C++[edit]

The following code sorts an array toSort consisting of nSize elements in increasing Order (bOrder=false) by default or decreasing Order (bOrder=true).

/*
For C++ Objects, overload the >, < and =
*/
 
template <class Type>
void SelectionSort(
	Type *toSort/*array to be sorted*/, 
	unsigned int nSize /* size of the array*/, 
	bool bOrder=false/*Increasing order by default*/
	)
{
	//check for valid values
	if (!toSort && !nSize)
	{
		return;
	}
 
        Type temp;
 
	//start selection sort
	for (unsigned int i=0; i < nSize - 2; i++)
	{
		unsigned int minimum = i;
 
		//find the minimum in the remaining list
		for (unsigned int j = i+1; j < nSize - 1; j++)
		{
			//default Order is increasing 
			if (bOrder?(toSort[minimum] < toSort[j]):(toSort[minimum] > toSort[j]))
			{
				//store the min array value index
				minimum = j;
			}
		} // for inner
 
		//we have the minimum value and current index, swap the values
		if (i != minimum)
		{
			temp = toSort[minimum];
			toSort[minimum] = toSort[i];
			toSort[i] = temp;
		}
	} //for outter
}

Using C++ idioms:

#include <algorithm>
 
template <class Iter>
void selectionSort( Iter begin, Iter end ) {
    for (Iter it = begin; it != end; ++it) {
        std::iter_swap(it, std::min_element(it, end));
    }
}

Diagram?[edit]

{{reqdiagram}} Can anyone make a diagram of this algorithm? --EvaGears 03:03, 6 January 2007 (UTC)

Great idea. It might be instructive to use the "card sorting" metaphor, since cards are often sorted using this algorithm or insertion sort. It also just occurred to me that we don't discussion selection sort on linked lists. Dcoetzee 22:37, 10 June 2007 (UTC)
I made an animated diagram and added it. I hope it's sufficient; I tried to just keep it simple.--Joestape89 (talk) 10:53, 5 December 2007 (UTC)
Please consider static diagrams! http://corte.si/posts/code/visualisingsorting/index.html 84.182.107.93 (talk) 16:56, 9 February 2010 (UTC)

Lie: Selection sort outperforms bubble sort[edit]

By using the bubble sort with 2 imbricated for loops and reversing the second one, we obtain a bubble sort that is faster than selection sort for the worst cases and much faster than the original version of bubble sort. Tests so far have proven this without a doubt. This should become the new bubble sort. Fix these lies wikipedia!

L337 Krew (talk) 13:51, 13 February 2008 (UTC)

You've modified the sort so that it's no longer bubble sort, which is original research, and your measurements are architecture-specific. There is no reason to modify the articles. Also, please don't post in multiple places - see Wikipedia:Talk page guidelines#multi. Dcoetzee 20:05, 13 February 2008 (UTC)

Anonymous 09:33, 10 May 2008 (UTC) That dude above was mentioning a cocktail sort, which is not the same as bubble sort indeed. Not to mention that it is actually not always faster than the original bubble sort. Yes I have a proof which shows that. Also please remove the statement that "selection sort is always faster than gnome_sort" which is again not true in certain situations. Actually in ceratin situations gnome sort may be very much the fastest one. —Preceding unsigned comment added by 83.24.241.212 (talk) 09:35, 10 May 2008 (UTC)

bingo sort[edit]

Does bingo sort merit its own stubby article or should it stay here? MahangaTalk 07:22, 21 February 2008 (UTC)

Code block templates[edit]

Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:36, 7 December 2008 (UTC)

Sorting-algorithms.com external link[edit]

The article has the external link

When I was trimming the ELs down, I left it in because it had a Discussion section and some references. I was indifferent on the animation. That EL is now involved in a minor editor war. One editor restored with the statement that the link contains useful information that is not in the article. I've taken a closer look at the EL, and here's what I see.

  1. There is a list of properties that are similar to the WP info box. The only property not mentioned in the article is "Not adaptive".
  2. There is a discussion section. It notes that SS is not adapative and hence is always quadratic time. That info is implied in the article's infobox. It makes a second observation that SS minimizes the number of swaps. The WP article states that SS uses O(n) swaps compared to insertion sorts O(n2). WP goes on to say cycle sort is better.
  3. There is a list of references, but the only explicit ref on selection sort is a youtube video of a Gypsy folkdance. IIRC, that EL made it into this article and was removed.
  4. The parallel animation shows the operation of four data sets. The animation runs in "lockstep" for SS. The animation would be good for other sorting algorithms that are "adaptive".
  • Remove the link. The link could be good for other sorting algorithms, but the current WP article has the information in the link. Glrx (talk) 16:41, 5 August 2011 (UTC)
  • Weak keep I think it is fairly educational to have some soft of interactive demonstration for each of the sorting algorithms working on various datasets. Clearly this is going to look a bit more trivial for selection sort than other sorting algorithms as you point out, but that is actually the point that you want to get across. It is (currently) technically impossible to develop this ourself and place it in the article or host it on a Wikimedia site, so we're kind of forced to use and external link for this. This particular link is one of the nicest I've come across. —Ruud 21:09, 5 August 2011 (UTC)
  • Remove. The graphics on the EL are helpful, but no more so than the animations that are already on the article as animated gifs. - MrOllie (talk) 23:11, 5 August 2011 (UTC)
    • Really? I only see an animation of a random dataset being sorted. Nearly sorted, reverse sorted and binned datasets are the three most important edge cases that tend to show the big differences between various sorting algorithms. We have no animations of those yet. —Ruud 23:22, 5 August 2011 (UTC)