Sorting algorithms/Selection sort

In this task, the goal is to sort an array (or list) of elements using the Selection sort algorithm. It works as follows:

First find the smallest element in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted. Its asymptotic complexity is O(n²) making it inefficient on large arrays. Its primary purpose is for when writing data is very expensive (slow) when compared to reading, eg writing to flash memory or EEPROM. No other sorting algorithm has less data movement.

For more information see the article on Wikipedia.

ActionScript

<lang ActionScript>function selectionSort(input: Array):Array { //find the i'th element for (var i:uint = 0; i < input.length; i++) { //set minIndex to an arbitrary value var minIndex:uint=i; //find the smallest number for (var j:uint = i; j < input.length; j++) { if (input[j]<input[minIndex]) { minIndex=j; } } //swap the smallest number into place var tmp:Number=input[i]; input[i]=input[minIndex]; input[minIndex]=tmp; } return input; }</lang>

Ada

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Selection_Sort is

  type Integer_Array is array (Positive range <>) of Integer;
  procedure Sort (A : in out Integer_Array) is
     Min  : Positive;
     Temp : Integer;
  begin
     for I in A'First..A'Last - 1 loop
        Min := I;
        for J in I + 1..A'Last loop
           if A (Min) > A (J) then
              Min := J;
           end if;
        end loop;
        if Min /= I then
           Temp    := A (I);
           A (I)   := A (Min);
           A (Min) := Temp;
        end if;
     end loop;
  end Sort;

  A : Integer_Array := (4, 9, 3, -2, 0, 7, -5, 1, 6, 8);

begin

  Sort (A);
  for I in A'Range loop
     Put (Integer'Image (A (I)) & " ");
  end loop;

end Test_Selection_Sort;</lang> Sample output:

-5 -2  0  1  3  4  6  7  8  9

ALGOL 68

Translation of: Ada

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang algol68>MODE DATA = REF CHAR;

PROC in place selection sort = (REF[]DATA a)VOID: BEGIN

  INT min;
  DATA temp;
  FOR i FROM LWB a TO UPB a DO
     min := i;
     FOR j FROM i + 1 TO UPB a DO
        IF a [min] > a [j] THEN
           min := j
        FI
     OD;
     IF min /= i THEN
        temp    := a [i];
        a [i]   := a [min];
        a [min] := temp
     FI
  OD

END # in place selection sort #;

[32]CHAR data := "big fjords vex quick waltz nymph"; [UPB data]DATA ref data; FOR i TO UPB data DO ref data[i] := data[i] OD; in place selection sort(ref data); FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line); print((data))</lang> Output:

     abcdefghiijklmnopqrstuvwxyz
big fjords vex quick waltz nymph

AutoHotkey

ahk forum: discussion <lang AutoHotkey>MsgBox % SelecSort("") MsgBox % SelecSort("xxx") MsgBox % SelecSort("3,2,1") MsgBox % SelecSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")

SelecSort(var) { ; SORT COMMA SEPARATED LIST

  StringSplit a, var, `,                ; make array, size = a0

  Loop % a0-1 {
     i := A_Index, mn := a%i%, j := m := i
     Loop % a0-i {                      ; find minimum
         j++
         If (a%j% < mn)
            mn := a%j%, m := j
     }
     t := a%i%, a%i% := a%m%, a%m% := t ; swap first with minimum
  }
  Loop % a0                             ; construct string from sorted array
     sorted .= "," . a%A_Index%
  Return SubStr(sorted,2)               ; drop leading comma

}</lang>

AWK

<lang awk>function getminindex(gl, gi, gs) {

 min = gl[gi]
 gm = gi
 for(gj=gi; gj <= gs; gj++) {
   if ( gl[gj] < min ) {
     min = gl[gj]
     gm = gj
   }
 }
 return gm

}

{

 line[NR] = $0

} END { # sort it with selection sort

 for(i=1; i <= NR; i++) {
   mi = getminindex(line, i, NR)
   t = line[i]
   line[i] = line[mi];
   line[mi] = t
 }
 #print it
 for(i=1; i <= NR; i++) {
   print line[i]
 }

}</lang>

BBC BASIC

<lang BBCBASIC>DEF PROC_SelectionSort(Size%) FOR I% = 1 TO Size%-1

  lowest% = I%
  FOR J% = (I% + 1) TO Size%
     IF data%(J%) < data%(lowest%) lowest% = J%
  NEXT J%
  IF I%<>lowest% SWAP data%(I%),data%(lowest%)

NEXT I% ENDPROC</lang>

C

<lang c> void selection_sort (int *a, int n) {

   int i, j, m, t;
   for (i = 0; i < n; i++) {
       for (j = i, m = i; j < n; j++) {
           if (a[j] < a[m])
               m = j;
       }
       t = a[i];
       a[i] = a[m];
       a[m] = t;
   }

}

int main () {

   int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
   int n = sizeof a / sizeof a[0];
   selection_sort(a, n);
   return 0;

} </lang>

C++

Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7))

<lang cpp>#include <algorithm>

include <iterator>

template<typename ForwardIterator> void selectionSort(ForwardIterator begin, ForwardIterator end) {

   for(ForwardIterator i = begin; i != end; ++i)
       std::iter_swap(i, std::min_element(i, end));

}</lang>

C#

This is a generic implementation that works with any type that implements the IComparable interface

<lang csharp>class SelectionSort<T> where T : IComparable {

   public T[] Sort(T[] list) {
       int k;
       T temp;

       for (int i = 0; i < list.Length; i++) {
           k = i;
           for (int j=i + 1; j < list.Length; j++) {
               if (list[j].CompareTo(list[k]) < 0) {
                   k = j;
               }
           }
           temp = list[i];
           list[i] = list[k];
           list[k] = temp;
       }

       return list;
   }

}</lang>

Example of usage: <lang csharp>String[] str = { "this", "is", "a", "test", "of", "generic", "selection", "sort" };

SelectionSort<String> mySort = new SelectionSort<string>();

String[] result = mySort.Sort(str);

for (int i = 0; i < result.Length; i++) {

   Console.WriteLine(result[i]);

}</lang>

Output:

a
generic
is
of
selection
sort
test
this

Clojure

This is an implementation that mutates a Java arraylist in place.

<lang lisp>(import 'java.util.ArrayList)

(defn arr-swap! [#^ArrayList arr i j]

 (let [t (.get arr i)]
   (doto arr
     (.set i (.get arr j))
     (.set j t))))

(defn sel-sort!

 ([arr] (sel-sort! compare arr))
 ([cmp #^ArrayList arr]
    (let [n (.size arr)]
      (letfn [(move-min!

[start-i] (loop [i start-i] (when (< i n) (when (< (cmp (.get arr i) (.get arr start-i)) 0) (arr-swap! arr start-i i)) (recur (inc i)))))] (doseq [start-i (range (dec n))] (move-min! start-i)) arr))))</lang>

COBOL

<lang COBOL> PERFORM E-SELECTION VARYING WB-IX-1 FROM 1 BY 1

                              UNTIL WB-IX-1 = WC-SIZE.

...

      E-SELECTION SECTION.
      E-000.
          SET WC-LOWEST   TO WB-IX-1.
          ADD 1 WC-LOWEST GIVING WC-START

          PERFORM F-PASS VARYING WB-IX-2 FROM WC-START BY 1
                         UNTIL WB-IX-2 > WC-SIZE.

          IF WB-IX-1 NOT = WC-LOWEST
             MOVE WB-ENTRY(WC-LOWEST) TO WC-TEMP
             MOVE WB-ENTRY(WB-IX-1)   TO WB-ENTRY(WC-LOWEST)
             MOVE WC-TEMP             TO WB-ENTRY(WB-IX-1).

      E-999.
          EXIT.

      F-PASS SECTION.
      F-000.
          IF WB-ENTRY(WB-IX-2) < WB-ENTRY(WC-LOWEST)
             SET WC-LOWEST TO WB-IX-2.

      F-999.
          EXIT.</lang>

Common Lisp

<lang lisp>(defun selection-sort-vector (array predicate)

 (do ((length (length array))
      (i 0 (1+ i)))
     ((eql i length) array)
   (do ((mindex i)
        (min (aref array i))
        (j i (1+ j)))
       ((eql j length)
        (rotatef (aref array i) (aref array mindex)))
     (when (funcall predicate (aref array j) min)
       (setf min (aref array j)
             mindex j)))))

(defun selection-sort-list (list predicate)

 (flet ((min-first (list)
          (do ((before-min nil)
               (min (first list))
               (prev list (rest prev))
               (curr (rest list) (rest curr)))
              ((endp curr)
               (if (null before-min) list
                 (let ((min (cdr before-min)))
                   (rplacd before-min (cdr min))
                   (rplacd min list)
                   min)))
            (when (funcall predicate (first curr) min)
              (setf before-min prev
                    min (first curr))))))
   (let ((result (min-first list)))
     (do ((head result (rest head)))
         ((endp (rest head)) result)
       (rplacd head (min-first (rest head)))))))

(defun selection-sort (sequence predicate)

 (etypecase sequence
   (list (selection-sort-list sequence predicate))
   (vector (selection-sort-vector sequence predicate))))</lang>

Example use:

> (selection-sort (list 8 7 4 3 2 0 9 1 5 6) '<)
(0 1 2 3 4 5 6 7 8 9)

> (selection-sort (vector 8 7 4 3 2 0 9 1 5 6) '>)
#(9 8 7 6 5 4 3 2 1 0)

D

<lang d>import std.stdio, std.algorithm;

void selectionSort(T)(T[] data) {

   foreach (i; 0 .. data.length) {
       auto minIndex = i;
       foreach (j; i + 1 .. data.length)
           if (data[j] < data[minIndex])
               minIndex = j;
       swap(data[i], data[minIndex]);
   }

}

void main() {

   auto foo = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2];
   selectionSort(foo);
   writeln(foo);

}</lang> Output:

[1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]

Delphi

Array sort

Dynamic array is a 0-based array of variable length

Static array is an arbitrary-based array of fixed length <lang Delphi>program TestSelectionSort;

{$APPTYPE CONSOLE}

{.$DEFINE DYNARRAY} // remove '.' to compile with dynamic array

type

 TItem = Integer;   // declare ordinal type for array item

{$IFDEF DYNARRAY}

 TArray = array of TItem;          // dynamic array

{$ELSE}

 TArray = array[0..15] of TItem;   // static array

{$ENDIF}

procedure SelectionSort(var A: TArray); var

 Item: TItem;
 I, J, M: Integer;

begin

 for I:= Low(A) to High(A) - 1 do begin
   M:= I;
   for J:= I + 1 to High(A) do
     if A[J] < A[M] then M:= J;
   Item:= A[M];
   A[M]:= A[I];
   A[I]:= Item;
 end;

end;

var

 A: TArray;
 I: Integer;

begin {$IFDEF DYNARRAY}

 SetLength(A, 16);

{$ENDIF}

 for I:= Low(A) to High(A) do
   A[I]:= Random(100);
 for I:= Low(A) to High(A) do
   Write(A[I]:3);
 Writeln;
 SelectionSort(A);
 for I:= Low(A) to High(A) do
   Write(A[I]:3);
 Writeln;
 Readln;

end.</lang> Output:

  0  3 86 20 27 67 31 16 37 42  8 47  7 84  5 29
  0  3  5  7  8 16 20 27 29 31 37 42 47 67 84 86

String sort

// string is 1-based variable-length array of Char <lang Delphi>procedure SelectionSort(var S: string); var

 Lowest: Char;
 I, J, M, L: Integer;

begin

 L:= Length(S);
 for I:= 1 to L - 1 do begin
   M:= I;
   for J:= I + 1 to L do
     if S[J] < S[M] then M:= J;
   Lowest:= S[M];
   S[M]:= S[I];
   S[I]:= Lowest;
 end;

end;</lang>

// in : S = 'the quick brown fox jumps over the lazy dog'
// out: S = '        abcdeeefghhijklmnoooopqrrsttuuvwxyz'

E

<lang e>def selectionSort := {

 def cswap(c, a, b) {
   def t := c[a]
   c[a]  := c[b]
   c[b]  := t
   println(c)
 }
 
 def indexOfMin(array, first, last) {
   var min := array[first]
   var mini := first
   for i in (first+1)..last {
     if (array[i] < min) {
       min := array[i]
       mini := i
     }
   }
   return mini
 }

 /** Selection sort (in-place). */
 def selectionSort(array) {
   def last := (array.size()-1)
   for i in 0..(last - 1) {
     cswap(array, i, indexOfMin(array, i + 1, last))
   }
 }

}</lang>

Euphoria

<lang euphoria>function selection_sort(sequence s)

   object tmp
   integer m
   for i = 1 to length(s) do
       m = i
       for j = i+1 to length(s) do
           if compare(s[j],s[m]) < 0 then
               m = j
           end if
       end for
       tmp = s[i]
       s[i] = s[m]
       s[m] = tmp
   end for
   return s

end function

include misc.e constant s = {4, 15, "delta", 2, -31, 0, "alfa", 19, "gamma", 2, 13, "beta", 782, 1}

puts(1,"Before: ") pretty_print(1,s,{2}) puts(1,"\nAfter: ") pretty_print(1,selection_sort(s),{2})</lang>

Output:

Before: {
  4,
  15,
  "delta",
  2,
  -31,
  0,
  "alfa",
  19,
  "gamma",
  2,
  13,
  "beta",
  782,
  1
}
After: {
  -31,
  0,
  1,
  2,
  2,
  4,
  13,
  15,
  19,
  782,
  "alfa",
  "beta",
  "delta",
  "gamma"
}

F#

<lang fsharp> let rec ssort = function

   [] -> []
   | x::xs -> 
       let min, rest =
           List.fold_left (fun (min,acc) x ->
                            if h<min then (h, min::acc)
                            else (min, h::acc))
             (x, []) xs
       in min::ssort rest

</lang>

Forth

<lang forth>defer less? ' < is less?

least ( start end -- least )

 over cell+ do
   i @ over @ less? if drop i then
 cell +loop ;

selection ( array len -- )

 cells over + tuck ( end start end )
 cell- swap do   ( end )
   i over least ( end least )
   i @ over @ i ! swap !
 cell +loop drop ;

create array 8 , 1 , 4 , 2 , 10 , 3 , 7 , 9 , 6 , 5 ,

array 10 selection array 10 cells dump</lang>

Fortran

Works with: Fortran version 95 and later

<lang fortran>PROGRAM SELECTION

 IMPLICIT NONE

 INTEGER :: intArray(10) = (/ 4, 9, 3, -2, 0, 7, -5, 1, 6, 8 /)

 WRITE(*,"(A,10I5)") "Unsorted array:", intArray
 CALL Selection_sort(intArray)
 WRITE(*,"(A,10I5)") "Sorted array  :", intArray

CONTAINS

 SUBROUTINE Selection_sort(a)
   INTEGER, INTENT(IN OUT) :: a(:)
   INTEGER :: i, minIndex, temp

   DO i = 1, SIZE(a)-1
      minIndex = MINLOC(a(i:), 1) + i - 1
      IF (a(i) > a(minIndex)) THEN
         temp = a(i)
         a(i) = a(minIndex)
         a(minIndex) = temp
      END IF
   END DO
 END SUBROUTINE Selection_sort

END PROGRAM SELECTION</lang> Output:

Unsorted array:    4    9    3   -2    0    7   -5    1    6    8
Sorted array  :   -5   -2    0    1    3    4    6    7    8    9

Go

<lang go>package main

import "fmt"

var a = []int{170, 45, 75, -90, -802, 24, 2, 66}

func main() {

   fmt.Println("before:", a)
   selectionSort(a)
   fmt.Println("after: ", a)

}

func selectionSort(a []int) {

   last := len(a) - 1
   for i := 0; i < last; i++ {
       aMin := a[i]
       iMin := i
       for j := i + 1; j < len(a); j++ {
           if a[j] < aMin {
               aMin = a[j]
               iMin = j
           }
       }
       a[i], a[iMin] = aMin, a[i]
   }

}</lang>

More generic version that sorts anything that implements sort.Interface: <lang go>package main

import (

 "sort"
 "fmt"

)

var a = []int{170, 45, 75, -90, -802, 24, 2, 66}

func main() {

   fmt.Println("before:", a)
   selectionSort(sort.IntSlice(a))
   fmt.Println("after: ", a)

}

func selectionSort(a sort.Interface) {

   last := a.Len() - 1
   for i := 0; i < last; i++ {
       iMin := i
       for j := i + 1; j < a.Len(); j++ {
           if a.Less(j, iMin) {
               iMin = j
           }
       }
       a.Swap(i, iMin)
   }

}</lang>

Haskell

<lang haskell>import Data.List (unfoldr)

selectionSort = unfoldr selectionSort' where

  selectionSort' [] = Nothing
  selectionSort' (first:lst) = Just $ foldl f (first, []) lst
  f (small, output) x | x < small = (x, small:output)
                      | otherwise = (small, x:output)</lang>

HaXe

<lang HaXe>static function selectionSort(arr:Array<Int>) { var len = arr.length; for (index in 0...len) { var minIndex = index; for (remainingIndex in (index+1)...len) { if (arr[minIndex] > arr[remainingIndex]) { minIndex = remainingIndex; } } if (index != minIndex) { var temp = arr[index]; arr[index] = arr[minIndex]; arr[minIndex] = temp; } } }</lang>

Io

<lang io>List do (

   selectionSortInPlace := method(
       size repeat(idx,
           swapIndices(idx, indexOf(slice(idx, size) min))
       )
   )

)

l := list(-1, 4, 2, -9) l selectionSortInPlace println # ==> list(-9, -1, 2, 4)</lang>

Icon and Unicon

<lang Icon>procedure main() #: demonstrate various ways to sort a list and string

  demosort(selectionsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

procedure selectionsort(X,op) #: return sorted list ascending(or descending) local i,m

  op := sortop(op,X)                                   # select how and what we sort
  every i := 1 to *X-1 do {
     m := i 
     every j := i + 1 to *X do
        if op(X[j],X[m]) then m := j                   # find X that belongs @i low (or high)
     X[m ~= i] :=: X[m]
     }
  return X

end</lang>

Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

Abbreviated sample output:

Sorting Demo using procedure selectionsort
  on list : [ 3 14 1 5 9 2 6 3 ]
    with op = &null:         [ 1 2 3 3 5 6 9 14 ]   (0 ms)
  ...
  on string : "qwerty"
    with op = &null:         "eqrtwy"   (0 ms)

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

Create the following script and load it to a J session. <lang j>selectionSort=: verb define

 data=. y
 for_xyz. y do.
   temp=. xyz_index }. data
   nvidx=. xyz_index + temp i. <./ temp
   data=. ((xyz_index, nvidx) { data) (nvidx, xyz_index) } data
 end.
 data

)</lang>

In an email discussion, Roger_Hui presented the following tacit code: <lang j>ix=: C.~ <@~.@(0, (i. <./)) ss1=: ({. , $:@}.)@ix^:(*@#)</lang>

To validate: <lang j> [data=. 6 15 19 12 14 19 0 17 0 14 6 15 19 12 14 19 0 17 0 14

  selectionSort data

0 0 6 12 14 14 15 17 19 19

  ss1 data

0 0 6 12 14 14 15 17 19 19</lang>

Java

This algorithm sorts in place. The call sort(array) will rearrange the array and not create a new one. <lang java>public static void sort(int[] nums){ for(int currentPlace = 0;currentPlace<nums.length-1;currentPlace++){ int smallest = Integer.MAX_VALUE; int smallestAt = currentPlace+1; for(int check = currentPlace; check<nums.length;check++){ if(nums[check]<smallest){ smallestAt = check; smallest = nums[check]; } } int temp = nums[currentPlace]; nums[currentPlace] = nums[smallestAt]; nums[smallestAt] = temp; } }</lang>

Liberty BASIC

<lang lb> itemCount = 20

   dim A(itemCount)
   for i = 1 to itemCount
       A(i) = int(rnd(1) * 100)
   next i

   print "Before Sort"
   gosub [printArray]

'--- Selection sort algorithm

   for i = 1 to itemCount-1
       jMin = i
       for j = i+1 to itemCount
           if A(j) < A(jMin) then jMin = j
       next
       tmp = A(i)
       A(i) = A(jMin)
       A(jMin) = tmp
   next

'--- end of (Selection sort algorithm)

   print "After Sort"
   gosub [printArray]

end

[printArray]

   for i = 1 to itemCount
       print using("###", A(i));
   next i
   print

return

</lang>

Lua

<lang lua>function SelectionSort( f )

   for k = 1, #f-1 do    
       local idx = k    
       for i = k+1, #f do
           if f[i] < f[idx] then 
               idx = i
           end    
       end
       f[k], f[idx] = f[idx], f[k]
   end

end

f = { 15, -3, 0, -1, 5, 4, 5, 20, -8 }

SelectionSort( f )

for i in next, f do

   print( f[i] )

end</lang>

Mathematica

Procedural solution with custom min function:

<lang Mathematica>SelectSort[x_List] := Module[{n = 1, temp, xi = x, j},

 While[n <= Length@x,
  temp = xin;
  For[j = n, j <= Length@x, j++,
   If[xij < temp, temp = xij];
   ];
  xin ;; = {temp}~Join~
    Delete[xin ;;, First@Position[xin ;;, temp] ];
  n++;
  ];
 xi
 ]</lang>

Recursive solution using a pre-existing Min[] function:

<lang Mathematica>SelectSort2[x_List]:= Flatten[{Min@x, If[Length@x > 1, SelectSort2@Drop[x, First@Position[x, Min@x]], {}] }];</lang>

Validate by testing the ordering of a random number of randomly-sized random lists:

<lang Mathematica>{And @@ Table[l = RandomInteger[150, RandomInteger[1000]];

  Through[And[Length@# == Length@SelectSort@# &, OrderedQ@SelectSort@# &]@l],
  {RandomInteger[150]}],
Block[{$RecursionLimit = Infinity},
 And @@ Table[l = RandomInteger[150, RandomInteger[1000]];
   Through[And[Length@# == Length@SelectSort2@# &, OrderedQ@SelectSort2@# &]@l],
   {RandomInteger[150]}]
 ]}</lang>

Validation Result:

{True, True}

MATLAB

<lang MATLAB>function list = selectionSort(list)

   listSize = numel(list);
   
   for i = (1:listSize-1)

       minElem = list(i);
       minIndex = i;
       
       %This for loop can be vectorized, but there will be no significant
       %increase in sorting efficiency.
       for j = (i:listSize)    
           if list(j) <= minElem
               minElem = list(j);
               minIndex = j;
           end                              
       end
       
       if i ~= minIndex
           list([minIndex i]) = list([i minIndex]); %Swap
       end
       
   end %for

end %selectionSort</lang>

Sample Usage: <lang MATLAB>>> selectionSort([4 3 1 5 6 2])

ans =

    1     2     3     4     5     6</lang>

MAXScript

<lang maxscript>fn selectionSort arr = (

   local min = undefined
   for i in 1 to arr.count do
   (
       min = i
       for j in i+1 to arr.count do
       (
           if arr[j] < arr[min] then
           (
               min = j
           )
       )
       swap arr[i] arr[min]
   )
   arr

)

data = selectionSort #(4, 9, 3, -2, 0, 7, -5, 1, 6, 8) print data</lang>

Nemerle

Translation of: C#

<lang Nemerle>using System; using System.Console;

module Selection {

   public static Sort[T](this a : array[T]) : void
     where T : IComparable
   {
       mutable k = 0;
       def lastindex = a.Length - 1;
       
       foreach (i in [0 .. lastindex])
       {
           k = i;
           foreach (j in [i .. lastindex])
               when (a[j].CompareTo(a[k]) < 0) k = j;
           a[i] <-> a[k];
       }
   }
   
   Main() : void
   {
       def arr = array[6, 2, 8, 3, 9, 4, 7, 3, 9, 1];
       arr.Sort();
       foreach (i in arr) Write($"$i  ");
   }

}</lang>

NetRexx

<lang NetRexx>/* NetRexx */ options replace format comments java crossref savelog symbols binary

import java.util.List

placesList = [String -

   "UK  London",     "US  New York",   "US  Boston",     "US  Washington" -
 , "UK  Washington", "US  Birmingham", "UK  Birmingham", "UK  Boston"     -

]

lists = [ -

   placesList -
 , selectionSort(String[] Arrays.copyOf(placesList, placesList.length)) -

]

loop ln = 0 to lists.length - 1

 cl = lists[ln]
 loop ct = 0 to cl.length - 1
   say cl[ct]
   end ct
   say
 end ln

return

method selectionSort(a = String[]) public constant binary returns String[]

 rl = String[a.length]
 al = List selectionSort(Arrays.asList(a))
 al.toArray(rl)

 return rl

method selectionSort(a = List) public constant binary returns ArrayList

 ra = ArrayList(a)
 n  = ra.size

 iPos = int
 iMin = int

 loop iPos = 0 to n - 1
   iMin = iPos
   loop i_ = iPos + 1 to n - 1
     if (Comparable ra.get(i_)).compareTo(Comparable ra.get(iMin)) < 0 then do
       iMin = i_
       end
     end i_
   if iMin \= iPos then do
     swap = ra.get(iPos)
     ra.set(iPos, ra.get(iMin))
     ra.set(iMin, swap)
     end
   end iPos

 return ra

</lang>

Output

UK  London
US  New York
US  Boston
US  Washington
UK  Washington
US  Birmingham
UK  Birmingham
UK  Boston

UK  Birmingham
UK  Boston
UK  London
UK  Washington
US  Birmingham
US  Boston
US  New York
US  Washington

OCaml

<lang ocaml>let rec selection_sort = function

   [] -> []
 | first::lst ->
     let rec select_r small output = function
         [] -> small :: selection_sort output
       | x::xs when x < small -> select_r x (small::output) xs
       | x::xs                -> select_r small (x::output) xs
     in
     select_r first [] lst</lang>

Oz

Although lists are much more used in Oz than arrays, this algorithm seems more natural for arrays. <lang oz>declare

 proc {SelectionSort Arr}
    proc {Swap K L}
       Arr.K := (Arr.L := Arr.K)
    end
    Low = {Array.low Arr}
    High = {Array.high Arr}
 in
    %% for every index I of the array
    for I in Low..High do

%% find the index of the minimum element %% with an index >= I Min = {NewCell Arr.I}

       MinIndex = {NewCell I}
    in
       for J in I..High do
 	 if Arr.J < @Min then

Min := Arr.J MinIndex := J

end

end %% and put that minimum element to the left {Swap @MinIndex I}

    end
 end
 
 A = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}

in

 {SelectionSort A}
 {Show {Array.toRecord unit A}}</lang>

PARI/GP

<lang parigp>selectionSort(v)={

 for(i=1,#v-1,
   my(mn=i,t);
   for(j=i+1,#v,
     if(v[j]<v[mn],mn=j)
   );
   t=v[mn];
   v[mn]=v[i];
   v[i]=t
 );
 v

};</lang>

Perl

Translation of: Tcl

<lang perl>sub selection_sort

 {my @a = @_;
  foreach my $i (0 .. $#a - 1)
     {my $min = $i + 1;
      $a[$_] < $a[$min] and $min = $_ foreach $min .. $#a;
      $a[$i] > $a[$min] and @a[$i, $min] = @a[$min, $i];}
  return @a;}</lang>

Perl 6

<lang perl6>sub selection_sort ( @a is copy ) {

   for 0 ..^ @a.end -> $i {
       my $min = [ $i+1 .. @a.end ].min: { @a[$_] };
       @a[$i, $min] = @a[$min, $i] if @a[$i] > @a[$min];
   }
   return @a;

}

my @data = 22, 7, 2, -5, 8, 4; say 'input = ' ~ @data; say 'output = ' ~ @data.&selection_sort; </lang>

Output:

input  = 22 7 2 -5 8 4
output = -5 2 4 7 8 22

PHP

Iterative: <lang php>function selection_sort(&$arr) {

   $n = count($arr);
   for($i = 0; $i < count($arr); $i++) {
       $min = $i;
       for($j = $i + 1; $j < $n; $j++){
           if($arr[$j] < $arr[$min]){
               $min = $j;
           }
       }
       list($arr[$i],$arr[$min]) = array($arr[$min],$arr[$i]);
   }

}</lang> Recursive: <lang php>function selectionsort($arr,$result=array()){

   if(count($arr) == 0){
       return $result;
   }
   $nresult = $result;
   $nresult[] = min($arr);
   unset($arr[array_search(min($arr),$arr)]);
   return selectionsort($arr,$nresult);

}</lang>

PicoLisp

<lang PicoLisp>(de selectionSort (Lst)

  (map
     '((L) (and (cdr L) (xchg L (member (apply min @) L))))
     Lst )
  Lst )</lang>

PowerShell

<lang PowerShell>Function SelectionSort( [Array] $data ) { $datal=$data.length-1 0..( $datal - 1 ) | ForEach-Object { $min = $data[ $_ ] $mini = $_ ( $_ + 1 )..$datal | ForEach-Object { if( $data[ $_ ] -lt $min ) { $min = $data[ $_ ] $mini = $_ } } $temp = $data[ $_ ] $data[ $_ ] = $min $data[ $mini ] = $temp } $data }

$l = 100; SelectionSort( ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } ) )</lang>

PureBasic

<lang PureBasic>Procedure selectionSort(Array a(1))

 Protected i, j, lastIndex, minIndex
 
 lastIndex = ArraySize(a())
 For i = 0 To lastIndex - 1
   minIndex = i
   For j = i + 1 To lastIndex
     If a(minIndex) > a(j)
       minIndex = j
     EndIf
   Next
   Swap a(minIndex), a(i)
 Next

EndProcedure</lang>

Python

<lang python>def selectionSort(lst):

   for i in range(0,len(lst)-1):
       mn = min(range(i,len(lst)), key=lst.__getitem__)
       lst[i],lst[mn] = lst[mn],lst[i]
   return lst</lang>

R

For loop: <lang r>selectionsort.loop <- function(x) {

  lenx <- length(x)
  for(i in seq_along(x))
  {
     mini <- (i - 1) + which.min(x[i:lenx])
     start_ <- seq_len(i-1)
     x <- c(x[start_], x[mini], x[-c(start_, mini)])
  }
  x

}</lang> Recursive:

(A prettier solution, but, you may need to increase the value of options("expressions") to test it. Also, you may get a stack overflow if the length of the input vector is more than a few thousand.) <lang r>selectionsort.rec <- function(x) {

  if(length(x) > 1)
  {
     mini <- which.min(x)
     c(x[mini], selectionsort(x[-mini]))
  } else x

}</lang>

Qi

Translation of: sml

<lang qi>(define select-r

 Small []     Output -> [Small | (selection-sort Output)]
 Small [X|Xs] Output -> (select-r X Xs [Small|Output]) where (< X Small)
 Small [X|Xs] Output -> (select-r Small Xs [X|Output]))

(define selection-sort

 []          -> []
 [First|Lst] -> (select-r First Lst []))

(selection-sort [8 7 4 3 2 0 9 1 5 6]) </lang>

REXX

<lang rexx> /*REXX program sorts an array using the selection-sort method. */

call gen@ /*generate array elements. */ call show@ 'before sort' /*show before array elements*/ call selectionSort highItem /*invoke the selection sort.*/ call show@ ' after sort' /*show after array elements*/ exit

/*─────────────────────────────────────SELECTIONSORT subroutine────*/ selectionSort: procedure expose @.; parse arg n

 do j=1 for n-1
 _=@.j;  p=j

       do k=j+1 to n
       if @.k<_ then do;  _=@.k;  p=k;  end
       end

if p==j then iterate
_=@.j;  @.j=@.p;  @.p=_
end

return

/*─────────────────────────────────────GEN@ subroutine─────────────*/ gen@: @.= /*assign default value. */

@.1='---The seven hills of Rome:---' @.2='==============================' @.3='Caelian' @.4='Palatine' @.5='Capitoline' @.6='Virminal' @.7='Esquiline' @.8='Quirinal' @.9='Aventine'

 do highItem=1 while @.highItem\==  /*find how many entries.    */
 end

highItem=highItem-1 /*adjust highItem slightly. */ return

/*─────────────────────────────────────SHOW@ subroutine────────────*/ show@: widthH=length(highItem) /*maximum width of any line.*/

 do j=1 for highItem
 say 'element' right(j,widthH) arg(1)":" @.j
 end

say copies('─',80) /*show a seperator line. */ return </lang> Output:

element 1 before sort: ---The seven hills of Rome:---
element 2 before sort: ==============================
element 3 before sort: Caelian
element 4 before sort: Palatine
element 5 before sort: Capitoline
element 6 before sort: Virminal
element 7 before sort: Esquiline
element 8 before sort: Quirinal
element 9 before sort: Aventine
────────────────────────────────────────────────────────────────────────────────
element 1  after sort: ---The seven hills of Rome:---
element 2  after sort: ==============================
element 3  after sort: Aventine
element 4  after sort: Caelian
element 5  after sort: Capitoline
element 6  after sort: Esquiline
element 7  after sort: Palatine
element 8  after sort: Quirinal
element 9  after sort: Virminal
────────────────────────────────────────────────────────────────────────────────

Ruby

Translation of: Tcl

<lang ruby>class Array

 def selectionsort!
   0.upto(length - 2) do |i|
     (min_idx = i + 1).upto(length - 1) do |j|
       if self[j] < self[min_idx]
         min_idx = j
       end
     end
     if self[i] > self[min_idx]
       self[i], self[min_idx] = self[min_idx], self[i]
     end
   end
   self
 end

end ary = [7,6,5,9,8,4,3,1,2,0] ary.selectionsort!

=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>

Scala

<lang scala>def swap(a: Array[Int], i1: Int, i2: Int) = { val tmp = a(i1); a(i1) = a(i2); a(i2) = tmp }

def selectionSort(a: Array[Int]) =

 for (i <- 0 until a.size - 1) 
   swap(a, i, (i + 1 until a.size).foldLeft(i)((currMin, index) => 
     if (a(index) < a(currMin)) index else currMin))</lang>

This version avoids the extra definition by using a function literal:

<lang scala>def selectionSort(a: Array[Int]) = for (i <- 0 until a.size - 1) (

 { (i1: Int, i2: Int) => val tmp = a(i1); a(i1) = a(i2); a(i2) = tmp }
 ) (i, (i + 1 until a.size).foldLeft(i)((currMin, index) => if (a(index) < a(currMin)) index else currMin) )</lang>

Seed7

<lang seed7>const proc: selectionSort (inout array elemType: arr) is func

 local
   var integer: i is 0;
   var integer: j is 0;
   var integer: min is 0;
   var elemType: help is elemType.value;
 begin
   for i range 1 to length(arr) - 1 do
     min := i;
     for j range i + 1 to length(arr) do
       if arr[j] < arr[min] then
         min := j;
       end if;
     end for;
     help := arr[min];
     arr[min] := arr[i];
     arr[i] := help;
   end for;
 end func;</lang>

Original source: [1]

Standard ML

<lang sml>fun selection_sort [] = []

 | selection_sort (first::lst) =
   let
     val (small, output) = foldl
       (fn (x, (small, output)) =>
           if x < small then 
             (x, small::output)
           else
             (small, x::output)
       ) (first, []) lst
   in
     small :: selection_sort output
   end</lang>

Tcl

Library: Tcllib (Package: struct::list)

<lang tcl>package require Tcl 8.5 package require struct::list

proc selectionsort {A} {

   set len [llength $A]
   for {set i 0} {$i < $len - 1} {incr i} {
       set min_idx [expr {$i + 1}]
       for {set j $min_idx} {$j < $len} {incr j} {
           if {[lindex $A $j] < [lindex $A $min_idx]} {
               set min_idx $j
           }
       }
       if {[lindex $A $i] > [lindex $A $min_idx]} {
           struct::list swap A $i $min_idx
       }
   }
   return $A

}

puts [selectionsort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>

TI-83 BASIC

Store input into L₁ and prgmSORTSLCT will store the sorted output into L₂.

:L₁→L₂
:dim(L₂)→I
:For(A,1,I)
:A→C
:0→X
:For(B,A,I)
:If L₂(B)<L₂(C)
:Then
:B→C
:1→X
:End
:End
:If X=1
:Then
:L₂(C)→B
:L₂(A)→L₂(C)
:B→L₂(A)
:End
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar I
:DelVar X
:Return

Ursala

The selection_sort function is parameterized by a relational predicate p. There are no arrays in Ursala so it uses a list, and the selected item is deleted from the list and inserted into another on each iteration rather than swapped with a preceding item of the same list. <lang Ursala>#import std

selection_sort "p" = @iNX ~&l->rx ^(gldif ==,~&r)^/~&l ^|C/"p"$- ~&</lang> This is already a bad way to code a sorting algorithm in this language, but with only a bit more work, we can get a bigger and slower version that more closely simulates the operations of repeatedly reordering an array. <lang Ursala>selection_sort "p" = ~&itB^?a\~&a ^|JahPfatPRC/~& ~=-~BrhPltPClhPrtPCTlrTQrS^D/"p"$- ~&</lang> Here is a test program sorting by the partial order relation on natural numbers. <lang Ursala>#import nat

cast %nL

example = selection_sort(nleq) <294,263,240,473,596,392,621,348,220,815></lang> output:

<220,240,263,294,348,392,473,596,621,815>