Talk:Selection sort
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions. | |
| ??? | This article has not yet received a rating on the assessment scale. | |
| ??? | This article has not yet received an importance rating on the assessment scale. | |
Contents |
[edit] 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)
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)
[edit] 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..
[edit] Implementations
[edit] 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;
}
[edit] 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;
}
}
[edit] 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
[edit] 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)));;
[edit] 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)))))))
[edit] Python
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
[edit] Diagram?
 |
It is requested that a diagram or diagrams be included in this article to improve its quality. For more information, refer to discussion on this page and/or the listing at Wikipedia:Requested images. |
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)
[edit] 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)
[edit] bingo sort
Does bingo sort merit its own stubby article or should it stay here? MahangaTalk 07:22, 21 February 2008 (UTC)
