Talk:Selection sort

selection sort

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)

I see another problem with "C" implementation shown on a page is that C unlike C++ does not have references so swap() function cannot be the way it is. Bot parameters of swap() should be pointer if it is "C" like swap(&a[i], &a[jMin]); -Alexei (talk) 18:11, 22 December 2022 (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

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

C

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

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

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

(* 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

 (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)))))))

Perl

sub selection_sort {
    my ($arr) = @_;
    my $size = scalar(@{$arr});
    for my $i (0 .. $size-1) {
        my $min_index = $i;
        for my $j ($i + 1 .. $size-1) {
            if ($arr->[$min_index] > $arr->[$j]) {
                $min_index = $j;
            }
        }
        ($arr->[$i], $arr->[$min_index]) = ($arr->[$min_index], $arr->[$i]);
    }
}

Python

def selectionsort(lst):
    for i in range(len(lst) - 1):
        min_index = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[min_index], lst[i] = lst[i], lst[min_index]

C++

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));
    }
}

Raku

sub selection-sort(@arr) {
    for 0 ..^ @arr.elems -> $i {
        my $min-idx = $i;
        for $i ^..^ @arr.elems -> $j {
            $min-idx = $j if @arr[$min-idx] > @arr[$j];
        }
        (@arr[$i], @arr[$min-idx]) = @arr[$min-idx], @arr[$i];
    }
}

Diagram?

{{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

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

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

Code block templates

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

The article has the external link

• http://www.sorting-algorithms.com/selection-sort

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(n²). 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)

Straight selection sort

I found a variant that does not search the minimum element, but swaps whenever an item is found that is less than the one at the current index. Sometimes this, sometimes the given variant is refered to as "straight select(ion) sort". I think, this variant (wich also has some parallels to bubble sort) should be mentioned, here, as well.

A German page names this variant "Ripple Sort" (http://www.tinohempel.de/info/info/ti/ripplesort.htm) - whilest BiDiBubble Sort also is known under "Ripple Sort" (German Wikipedia). — Preceding unsigned comment added by 217.191.2.245 (talk) 20:02, 8 February 2015 (UTC)

"Mathematical definition"

I deleted the "Mathematical definition" section, since it was just plain wrong. It confused the concepts of set, multiset and sequence, resulting in nonsense. A set is a fundamentally unordered object so a sorting routine cannot be defined as inputting and outputting a set. It makes no sense to say "remove one instance of some element from a set" because sets have no multiplicities. Dricherby (talk) 21:17, 3 March 2015 (UTC)

Cocktail selection sort performs less comparisons

The section about the cocktail selection sort says that it is « not actually decreasing the number of comparisons or swaps », but this isn't true: finding the min element of a list of size $n$ takes $n-1$ comparisons; finding the max element also takes $n-1$ comparison. However, finding both in one pass (like std::minmax_element in C++) only takes ${\frac {3}{2}}(n-1)$ comparisons instead of $2(n-1)$ for the naive method. Provided a cocktail selection sort uses such an algorithm, it effectively performs less comparisons than a simple selection sort. 92.135.21.237 (talk) 21:33, 15 October 2015 (UTC)

Plz rename page

to "Selection sorting" (and other pages - also) — Preceding unsigned comment added by 130.180.212.50 (talk) 09:41, 11 March 2017 (UTC)

The term "selection sort" is treated as a noun phrase -- it is essentially the name of this sorting algorithm. Perhaps that should be clarified in some way? Perhaps only on sorting algorithm though. nhinchey (talk) 08:16, 22 May 2019 (UTC)

What's with all the Θs (thetas)?

I am familiar with O() notation, but I've never seen it with Θ before. Can someone please elucidate that?

(Foreword: this is not really the place for this question, but I'll answer it anyway.) As you know, O() is an upper bound description of growth. If growth can be described linearly, then it can be described as O(n) because there is a linear function that can provide an upper bound. But isn't O(n!) also an upper bound? Likewise, a function with linear growth can be described with a lower bounding function Ω(n), but isn't Ω(1) also a lower bound? We do not always know the lower and upper bounds, but when we do and when they are the same, we can describe them with theta. If an algorithm has growth described by O(n) and Ω(n), then it is also Θ(n). This is the most concise and accurate description of growth. I would like to reiterate that we do not always know the smallest O() of a function or the largest Ω(n). There are computer scientists who dedicate their research to this, and, for instance, it was only proved in March 2019 that multiplication can be performed in O(n log n) time, but even that (massively complicated) paper left many questions unanswered about the nature of something so "simple" as multiplication! For more about Θ(), check out this subsection of Big O Notation: Related Asymptotic Notations.Wurtech (talk) 17:36, 23 May 2019 (UTC)

Edit: It occurred to me that you probably meant elucidate it in the article. I'll consider that, but Θ() is a basic idea so I think it is best to link to the Big O Notation article as I did above.Wurtech (talk) 17:36, 23 May 2019 (UTC)

Selection sort does not have the minimum number of swaps

Selection sort does not always have the minimum number of swaps. For example, with [7, 1, 3, 4, 5], it will swap the 7 four times. Cycle sort requires zero swaps, as it will take [7, 1, 3, 4, 5] and rotate it to [1, 3, 4, 5, 7] by using a single temporary variable rather than swaps. The importance of this is that it may be expensive in some way to write to the list to be sorted, and writing each element exactly once to its final place is cheaper than writing the 7 four times and the others one time each. Chai T. Rex (talk) 07:14, 9 November 2022 (UTC)