Talk:Selection sort

From Wikipedia, the free encyclopedia

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)

Contents 1 Excessive implementations 2 Implementations 2.1 C 2.2 Java 2.3 Haskell 2.4 Ocaml 2.5 LISP 2.6 Python 3 Diagram?

[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?

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