Sorting algorithms/Selection sort

From Rosetta Code
Jump to: navigation, search
Task
Sorting algorithms/Selection sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.

For other sorting algorithms, see Category:Sorting Algorithms, or:
O(n logn) Sorts
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble sort | Cocktail sort | Comb sort | Gnome sort | Insertion sort | Selection sort | Strand sort
Other Sorts
Bead sort | Bogosort | Counting sort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge 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(n2) 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.

Contents

[edit] 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;
}

[edit] 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;

Sample output:

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

[edit] 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
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))

Output:

     abcdefghiijklmnopqrstuvwxyz
big fjords vex quick waltz nymph

[edit] AutoHotkey

ahk forum: discussion

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
}

[edit] 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]
}
}

[edit] BBC BASIC

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

[edit] 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;
}
 

[edit] C++

Uses C++11. Compile with

g++ -std=c++11 selection.cpp
#include <algorithm>
#include <iterator>
#include <iostream>
 
template<typename ForwardIterator> void selection_sort(ForwardIterator begin,
ForwardIterator end) {
for(auto i = begin; i != end; ++i) {
std::iter_swap(i, std::min_element(i, end));
}
}
 
int main() {
int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
selection_sort(std::begin(a), std::end(a));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}

Output:

-199 -52 2 3 33 56 99 100 177 200

[edit] C#

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

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

Example of usage:

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

Output:

a
generic
is
of
selection
sort
test
this


[edit] Clojure

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

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

[edit] 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.

[edit] Common 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))))

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)

[edit] D

The actual function is very short.

import std.stdio, std.algorithm, std.array, std.traits;
 
enum AreSortableArrayItems(T) = isMutable!T &&
__traits(compiles, T.init < T.init) &&
!isNarrowString!(T[]);
 
void selectionSort(T)(T[] data) if (AreSortableArrayItems!T) {
foreach (immutable i, ref d; data)
data.drop(i).minPos[0].swap(d);
} unittest {
int[] a0;
a0.selectionSort;
 
auto a1 = [1];
a1.selectionSort;
assert(a1 == [1]);
 
auto a2 = ["a", "b"];
a2.selectionSort;
assert(a2 == ["a", "b"]);
 
auto a3 = ["b", "a"];
a3.selectionSort;
assert(a3 == ["a", "b"]);
 
auto a4 = ['a', 'b'];
static assert(!__traits(compiles, a4.selectionSort));
 
dchar[] a5 = ['b', 'a'];
a5.selectionSort;
assert(a5 == "ab"d);
 
import std.typecons;
alias Nullable!int N;
auto a6 = [N(2), N(1)];
a6.selectionSort; // Not nothrow.
assert(a6 == [N(1), N(2)]);
 
auto a7 = [1.0+0i, 2.0+0i]; // To be deprecated.
static assert(!__traits(compiles, a7.selectionSort));
 
import std.complex;
auto a8 = [complex(1), complex(2)];
static assert(!__traits(compiles, a8.selectionSort));
 
static struct F {
int x;
int opCmp(F f) { // Not pure.
return x < f.x ? -1 : (x > f.x ? 1 : 0);
}
}
auto a9 = [F(2), F(1)];
a9.selectionSort;
assert(a9 == [F(1), F(2)]);
}
 
void main() {
auto a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2];
a.selectionSort;
a.writeln;
}
Output:
[1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]

[edit] Delphi

[edit] Array sort

Dynamic array is a 0-based array of variable length

Static array is an arbitrary-based array of fixed length

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.

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

[edit] String sort

// string is 1-based variable-length array of Char

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;
// in : S = 'the quick brown fox jumps over the lazy dog'
// out: S = '        abcdeeefghhijklmnoooopqrrsttuuvwxyz'

[edit] 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))
}
}
}

[edit] 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})

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"
}

[edit] F#

 
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
 

[edit] 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

[edit] Fortran

Works with: Fortran version 95 and later
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

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

[edit] GAP

SelectionSort := function(v)
local i, j, k, n, m;
n := Size(v);
for i in [1 .. n] do
k := i;
m := v[i];
for j in [i + 1 .. n] do
if v[j] < m then
k := j;
m := v[j];
fi;
od;
v[k] := v[i];
v[i] := m;
od;
end;
 
v := List([1 .. 100], n -> Random([1 .. 100]));
SelectionSort(v);
v;

[edit] 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]
}
}

More generic version that sorts anything that implements sort.Interface:

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

[edit] Haskell

selSort :: (Ord a) => [a] -> [a]
selSort [] = []
selSort xs = let x = maximum xs in x : selSort (remove x xs)
where remove _ [] = []
remove a (x:xs)
| x == a = xs
| otherwise = x : remove a xs
 

[edit] 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;
}
}
}

[edit] 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)

[edit] Icon and Unicon

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

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)

[edit] 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.

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
)

In an email discussion, Roger_Hui presented the following tacit code:

ix=: C.~ <@~.@(0, (i. <./)) 
ss1=: ({. , $:@}.)@ix^:(*@#)

To validate:

   [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

[edit] Java

This algorithm sorts in place. The call sort(array) will rearrange the array and not create a new one.

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

[edit] Liberty BASIC

    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
 

[edit] 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

[edit] Mathematica

Procedural solution with custom min function:

SelectSort[x_List] := Module[{n = 1, temp, xi = x, j},
While[n <= Length@x,
temp = xi[[n]];
For[j = n, j <= Length@x, j++,
If[xi[[j]] < temp, temp = xi[[j]]];
];
xi[[n ;;]] = {temp}~Join~
Delete[xi[[n ;;]], First@Position[xi[[n ;;]], temp] ];
n++;
];
xi
]

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

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

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

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

Validation Result:

{True, True}

[edit] MATLAB / Octave

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

Sample Usage:

>> selectionSort([4 3 1 5 6 2])
 
ans =
 
1 2 3 4 5 6

[edit] Maxima

selection_sort(v) := block([k, m, n],
n: length(v),
for i: 1 thru n do (
k: i,
m: v[i],
for j: i + 1 thru n do
if v[j] < m then (k: j, m: v[j]),
v[k]: v[i],
v[i]: m
))$
 
v: makelist(random(199) - 99, i, 1, 10); /* [52, -85, 41, -70, -59, 88, 19, 80, 90, 44] */
selection_sort(v)$
v; /* [-85, -70, -59, 19, 41, 44, 52, 80, 88, 90] */

[edit] 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

[edit] Nemerle

Translation of: C#
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 ");
}
}

[edit] 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
 
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

[edit] Nimrod

proc selectionSort[T](a: var openarray[T]) =
let n = a.len
for i in 0 .. <n:
var m = i
for j in i .. <n:
if a[j] < a[m]:
m = j
swap a[i], a[m]
 
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
selectionSort a
echo a

Output:

@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

[edit] 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

[edit] ooRexx

/*REXX ****************************************************************
* program sorts an array using the selection-sort method.
* derived from REXX solution
* Note that ooRexx can process Elements of the stem argument (Use Arg)
* 06.10.2010 Walter Pachl
**********************************************************************/

call generate /*generate the array elements. */
call show 'before sort' /*show the before array elements,*/
call selectionSort x. /*invoke the selection sort. */
call show 'after sort' /*show the after array elements.*/
exit /*stick a fork in it, we're done.*/
 
selectionSort: Procedure
Use Arg s. /* gain access to the argument */
do j=1 To s.0-1
t=s.j;
p=j;
do k=j+1 to s.0
if s.k<t then do;
t=s.k;
p=k;
end
end
if p=j then
iterate
t=s.j;
s.j=s.p;
s.p=t
end
return
 
show:
Parse Arg heading
Say heading
Do i=1 To x.0
Say i' 'x.i
End
say copies('-',79)
Return
return
 
generate:
x.1='---The seven hills of Rome:---'
x.2='=============================='
x.3='Caelian'
x.4='Palatine'
x.5='Capitoline'
x.6='Virminal'
x.7='Esquiline'
x.8='Quirinal'
x.9='Aventine'
x.0=9
return

[edit] Oz

Although lists are much more used in Oz than arrays, this algorithm seems more natural for arrays.

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

[edit] PARI/GP

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

[edit] Pascal

See Delphi

[edit] Perl

Translation of: Tcl
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;}

[edit] Perl 6

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;
 
Output:
input  = 22 7 2 -5 8 4
output = -5 2 4 7 8 22

[edit] PHP

Iterative:

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

Recursive:

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

[edit] PicoLisp

(de selectionSort (Lst)
(map
'((L) (and (cdr L) (xchg L (member (apply min @) L))))
Lst )
Lst )

[edit] PL/I

 
Selection: procedure options (main); /* 2 November 2013 */
 
declare a(10) fixed b inary initial (
5, 7, 3, 98, 4, -3, 25, 20, 60, 17);
 
put edit (trim(a)) (a, x(1));
 
call Selection_Sort (a);
 
put skip edit (trim(a)) (a, x(1));
 
Selection_sort: procedure (a);
declare a(*) fixed binary;
declare t fixed binary;
declare n fixed binary;
declare (i, j, k) fixed binary;
 
n = hbound(a,1);
do j = 1 to n;
k = j; t = a(j);
do i = j+1 to n;
if t > a(i) then do; t = a(i); k = i; end;
end;
a(k) = a(j); a(j) = t;
end;
end Selection_Sort;
 
end Selection;
 

Results:

5 7 3 98 4 -3 25 20 60 17
-3 3 4 5 7 17 20 25 60 98

[edit] 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 ) } ) )

[edit] Prolog

Works with SWI-Prolog 6.3.11 (needs nth0/4).

 
selection_sort([], []).
selection_sort([H | L], [H1 | L2]) :-
exchange(H, L, H1, L1),
selection_sort(L1, L2).
 
 
exchange(H, [], H, []).
 
exchange(H, L, H1, L1) :-
min_list(L, H2),
( H < H2
-> H1 = H, L1 = L
; H1 = H2,
% does the exchange of the number H
% and the min of the list
nth0(Ind, L, H1, L2),
nth0(Ind, L1, H, L2)).
 

[edit] 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

[edit] 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

[edit] R

For loop:

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
}

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

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

[edit] Qi

Translation of: sml
(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])
 

[edit] Racket

 
#lang racket
(define (selection-sort xs)
(cond [(empty? xs) '()]
[else (define x0 (apply min xs))
(cons x0 (selection-sort (remove x0 xs)))]))
 

[edit] REXX

/*REXX program sorts an  array  using  the  selection-sort  method.     */
@.='' /*assign a default value to stem.*/
@.1='---The seven hills of Rome:---'
@.2='=============================='
@.3='Caelian'
@.4='Palatine'
@.5='Capitoline'
@.6='Virminal'
@.7='Esquiline'
@.8='Quirinal'
@.9='Aventine'
do items=1 until @.items=='' /*find # items.*/
end
items=items-1 /*adjust the # of items slightly.*/
call show@ 'before sort' /*show the before array elements,*/
call selectionSort items /*invoke the selection sort. */
call show@ ' after sort' /*show the after array elements.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────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 /*k*/
if p==j then iterate
_=@.j; @.j=@.p; @.p=_
end /*j*/
return
/*──────────────────────────────────SHOW@ subroutine────────────────────*/
show@: w=length(items); do i=1 for items
say 'element' right(i,w) arg(1)":" @.i
end /*i*/
say copies('─',79) /*show a nice separator line. */
return

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

[edit] Ruby

Translation of: Tcl
class Array
def selectionsort!
for i in 0..length-2
min_idx = i
for j in (i+1)...length
min_idx = j if self[j] < self[min_idx]
end
self[i], self[min_idx] = self[min_idx], self[i]
end
self
end
end
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.selectionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[edit] Run BASIC

siz = 10
dim srdData(siz)
for i = 1 to siz
srtData(i) = rnd(0) * 100
next i
 
FOR i = 1 TO siz-1
lo = i
FOR j = (i + 1) TO siz
IF srtData(j) < srtData(lo) lo = j
NEXT j
if i <> lo then
temp = srtData(i)
srtData(i) = srtData(lo)
srtData(lo) = temp
end if
NEXT i
 
for i = 1 to siz
print i;chr$(9);srtData(i)
next i
1	20.5576419
2	32.4299311
3	48.345375
4	54.135847
5	63.1427764
6	67.8079128
7	85.2134895
8	91.3576602
9	95.4280853
10	98.8323211

[edit] 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))

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

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

[edit] 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;

Original source: [1]

[edit] Standard ML

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

[edit] Tcl

Library: Tcllib (Package: struct::list)
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

[edit] TI-83 BASIC

Store input into L1 and prgmSORTSLCT will store the sorted output into L2.

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

[edit] 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.

#import std
 
selection_sort "p" = @iNX ~&l->rx ^(gldif ==,~&r)^/~&l ^|C/"p"$- ~&

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.

selection_sort "p" = ~&itB^?a\~&a ^|JahPfatPRC/~& ~=-~BrhPltPClhPrtPCTlrTQrS^D/"p"$- ~&

Here is a test program sorting by the partial order relation on natural numbers.

#import nat
#cast %nL
 
example = selection_sort(nleq) <294,263,240,473,596,392,621,348,220,815>

output:

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

[edit] VBA

I shameless stole the swap function from the bubblesort VBscript implementation.

 
sub swap( byref a, byref b)
dim tmp
tmp = a
a = b
b = tmp
end sub
 
function selectionSort (a)
for i = 0 to ubound(a)
k = i
for j=i+1 to ubound(a)
if a(j) < a(i) then
swap a(i), a(j)
end if
next
next
selectionSort = a
end function
 

[edit] XPL0

include c:\cxpl\codes;          \intrinsic 'code' declarations
string 0; \use zero-terminated strings
 
proc SelSort(A, N); \Selection sort
char A; \address of array
int N; \number of elements in array (size)
int I, J, S, JS, T;
[for I:= 0 to N-2 do
[S:= (~0)>>1;
for J:= I to N-1 do \find smallest element
if A(J) < S then [S:= A(J); JS:= J];
T:= A(I); A(I):= A(JS); A(JS):= T;
];
];
 
func StrLen(Str); \Return number of characters in an ASCIIZ string
char Str;
int I;
for I:= 0 to -1>>1-1 do
if Str(I) = 0 then return I;
 
char Str;
[Str:= "Pack my box with five dozen liquor jugs.";
SelSort(Str, StrLen(Str));
Text(0, Str); CrLf(0);
]

Output:

       .Pabcdeefghiiijklmnoooqrstuuvwxyz
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox