Sorting algorithms/Selection sort: Difference between revisions

{{trans|Python}}

 

L(e) lst

V mn = min(L.index .< lst.len, key' x -> @lst[x])

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

selection_sort(&arr)

 

{{out}}

{{trans|PL/I}}

The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible.

SELECSRT CSECT

USING SELECSRT,R13 base register

RK EQU 8 k

RT EQU 9 temp

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program selectionSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ActionScript}}==

//find the i'th element

for (var i:uint = 0; i < input.length; i++) {

}

return input;

 

=={{header|Ada}}==

 

procedure Test_Selection_Sort is

Put (Integer'Image (A (I)) & " ");

end loop;

{{out}}

<pre>

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

 

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

in place selection sort(ref data);

FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);

{{out}}

<pre>

big fjords vex quick waltz nymph

</pre>

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program selectionSort.s */

 

 

 

=={{header|Arturo}}==

 

sorted: new []

tmp: new items

]

 

 

{{out}}

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/topic44657-105.html discussion]

MsgBox % SelecSort("xxx")

MsgBox % SelecSort("3,2,1")

sorted .= "," . a%A_Index%

Return SubStr(sorted,2) ; drop leading comma

 

=={{header|AWK}}==

{

min = gl[gi]

print line[i]

}

 

=={{header|BBC BASIC}}==

FOR I% = 1 TO Size%-1

lowest% = I%

IF I%<>lowest% SWAP data%(I%),data%(lowest%)

NEXT I%

 

=={{header|BASIC}}==

==={{header|GWBASIC}}===

Works with: QBASIC, QuickBASIC, VB-DOS

10 'SAVE"SELSORT",A

20 ' Selection Sort Algorithm

450 PRINT "End of program"

460 END

 

=={{header|BCPL}}==

 

let selectionsort(A, len) be if len > 1

selectionsort(array, length)

writes("Output: ") ; writearray(array, length) ; wrch('*N')

{{out}}

<pre>Input: 52 -5 -20 199 65 -3 190 25 9999 -5342

=={{header|C}}==

 

 

void selection_sort (int *a, int n) {

return 0;

}

{{out}}

<pre>

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

 

public T[] Sort(T[] list) {

int k;

return list;

}

 

Example of usage:

 

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

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

Console.WriteLine(result[i]);

 

{{out}}

Uses C++11. Compile with

g++ -std=c++11 selection.cpp

#include <iterator>

#include <iostream>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

{{out}}

<pre>

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

 

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

(doseq [start-i (range (dec n))]

(move-min! start-i))

 

=={{header|COBOL}}==

UNTIL WB-IX-1 = WC-SIZE.

 

 

F-999.

 

=={{header|Common Lisp}}==

 

(do ((length (length array))

(i 0 (1+ i)))

(etypecase sequence

(list (selection-sort-list sequence predicate))

 

Example use:

=={{header|Crystal}}==

This sorts the array in-place.

(0...array.size-1).each do |i|

nextMinIndex = i

end

end

 

=={{header|D}}==

The actual function is very short.

 

enum AreSortableArrayItems(T) = isMutable!T &&

a.selectionSort;

a.writeln;

{{out}}

<pre>[1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9]</pre>

 

=={{header|Delphi}}==

 

Static array is an arbitrary-based array of fixed length

 

{$APPTYPE CONSOLE}

Writeln;

Readln;

{{out}}

<pre>

===String sort===

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

var

Lowest: Char;

S[I]:= Lowest;

end;

<pre>

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

=={{header|E}}==

 

def cswap(c, a, b) {

def t := c[a]

}

}

 

=={{header|EasyLang}}==

 

.

.

data[] = [ 29 4 72 44 55 26 27 77 92 5 ]

 

=={{header|EchoLisp}}==

===List sort===

;; recursive version (adapted from Racket)

(lib 'list) ;; list-delete

→ (0 1 2 3 4 5 6 7 8 9 10 11 12)

===Array sort===

;; sort an array in place

(define (sel-sort a (amin) (imin))

(sel-sort a)

→ #( 2 3 4 5 6 8 9)

 

=={{header|Eiffel}}==

 

class

SELECTION_SORT [G -> COMPARABLE]

 

end

Test:

class

APPLICATION

 

end

{{out}}

<pre>

 

=={{header|Elena}}==

import system'routines;

var copy := self.clone();

{

int k := i;

{

if (copy[j] < copy[k])

console.printLine("before:",list.asEnumerable());

console.printLine("after:",list.selectionSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def selection_sort(list) when is_list(list), do: selection_sort(list, [])

selection_sort(List.delete(list, max), [max | sorted])

end

 

Example:

 

=={{header|Erlang}}==

-module(solution).

-import(lists,[delete/2,max/1]).

Ans=selection_sort([1,5,7,8,4,10],[]),

print_array(Ans).

 

=={{header|Euphoria}}==

object tmp

integer m

pretty_print(1,s,{2})

puts(1,"\nAfter: ")

 

{{out}}

 

=={{header|F Sharp|F#}}==

let rec ssort = function

[] -> []

let min, rest =

List.fold (fun (min,acc) x ->

(x, []) xs

in min::ssort rest

 

=={{header|Factor}}==

 

: select ( m n seq -- )

 

: selection-sort! ( seq -- seq' )

Example use

 

--- Data stack:

 

=={{header|Forth}}==

 

: least ( start end -- least )

array 10 selection

 

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

 

IMPLICIT NONE

END SUBROUTINE Selection_sort

 

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsort 1 -7 -5 -4 6 5 -3 4 2 0 3 -6 -2 7 -1

 

=={{header|Gambas}}==

siLow As Short = -99 'Set the lowest value number to create

siHigh As Short = 99 'Set the highest value number to create

Return siList

 

 

Output:

 

=={{header|GAP}}==

local i, j, k, n, m;

n := Size(v);

v := List([1 .. 100], n -> Random([1 .. 100]));

SelectionSort(v);

 

=={{header|Go}}==

 

import "fmt"

a[i], a[iMin] = aMin, a[i]

}

 

More generic version that sorts anything that implements <code>sort.Interface</code>:

 

import (

a.Swap(i, iMin)

}

 

=={{header|Haskell}}==

 

selSort :: (Ord a) => [a] -> [a]

selSort [] = []

selSort xs = selSort (delete x xs) ++ [x]

 

=={{header|Haxe}}==

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

=={{header|Icon}} and {{header|Unicon}}==

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

end

}

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| 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.

 

=={{header|Io}}==

selectionSortInPlace := method(

size repeat(idx,

 

l := list(-1, 4, 2, -9)

 

=={{header|J}}==

{{eff note|J|/:~}}

Create the following script and load it to a J session.

data=. y

for_xyz. y do.

end.

data

 

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

 

To validate:

6 15 19 12 14 19 0 17 0 14

selectionSort data

0 0 6 12 14 14 15 17 19 19

ss1 data

 

=={{header|Java}}==

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

for(int currentPlace = 0;currentPlace<nums.length-1;currentPlace++){

int smallest = Integer.MAX_VALUE;

nums[smallestAt] = temp;

}

 

=={{header|JavaScript}}==

This algorithm sorts array of numbers.

var len = nums.length;

for(var i = 0; i < len; i++) {

}

return nums;

 

=={{header|jq}}==

The following implementation does not impose any restrictions on the types of entities that may appear in the array to be sorted. That is, the array may include any collection of JSON entities.

 

def selection_sort:

def swap(i;j): if i == j then . else .[i] as $tmp | .[i] = .[j] | .[j] = $tmp end;

)) as $ans

| swap( $currentPlace; $ans[0] )

[1, 3.3, null, 2, null, [1,{"a":1 }] ] | selection_sort

{{Out}}

<pre>

{{works with|Julia|0.6}}

 

len = length(arr)

if len < 2 return arr end

 

v = rand(-10:10, 10)

 

{{out}}

=={{header|Kotlin}}==

{{trans|C#}}

for (i in 0..size - 2) {

var k = i

c.selection_sort()

println(c.joinToString())

{{out}}

<pre>-5, -2, 0, 1, 3, 4, 6, 7, 8, 9

 

=={{header|Liberty BASIC}}==

dim A(itemCount)

for i = 1 to itemCount

print

return

 

=={{header|LSE}}==

(*

** Tri par Sélection

BOUCLER

FIN PROCEDURE

 

=={{header|Lua}}==

for k = 1, #f-1 do

local idx = k

for i in next, f do

print( f[i] )

 

=={{header|Maple}}==

len := numelems(arr):

for i to len-1 do

end if:

end do:

{{Out|Output}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

Procedural solution with custom min function:

 

While[n <= Length@x,

temp = xi[[n]];

];

xi

 

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

 

 

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

 

Through[And[Length@# == Length@SelectSort@# &, OrderedQ@SelectSort@# &]@l],

{RandomInteger[150]}],

Through[And[Length@# == Length@SelectSort2@# &, OrderedQ@SelectSort2@# &]@l],

{RandomInteger[150]}]

 

Validation Result:

=={{header|MATLAB}} / {{header|Octave}}==

 

 

listSize = numel(list);

end %for

 

Sample Usage:

 

ans =

 

 

=={{header|Maxima}}==

n: length(v),

for i: 1 thru n do (

v: makelist(random(199) - 99, i, 1, 10); /* [52, -85, 41, -70, -59, 88, 19, 80, 90, 44] */

selection_sort(v)$

 

=={{header|MAXScript}}==

(

local min = undefined

 

data = selectionSort #(4, 9, 3, -2, 0, 7, -5, 1, 6, 8)

 

=={{header|N/t/roff}}==

..

.de array

..

.sort myArray

 

===Output===

0

0

212

483

 

=={{header|Nanoquery}}==

{{trans|Java}}

 

def sort(nums)

end

return nums

 

=={{header|Nemerle}}==

{{trans|C#}}

using System.Console;

 

foreach (i in arr) Write($"$i ");

}

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

 

return ra

{{out}}

<pre>

 

=={{header|Nim}}==

let n = a.len

for i in 0 ..< n:

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

selectionSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|OCaml}}==

[] -> []

| first::lst ->

| x::xs -> select_r small (x::output) xs

in

 

=={{header|Oforth}}==

 

| b j i k s |

l size ->s

k i b at b put i swap b put

]

 

=={{header|ooRexx}}==

 

* program sorts an array using the selection-sort method.

* derived from REXX solution

x.9='Aventine'

x.0=9

 

=={{header|Oz}}==

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

proc {SelectionSort Arr}

proc {Swap K L}

in

{SelectionSort A}

 

=={{header|PARI/GP}}==

for(i=1,#v-1,

my(mn=i,t);

);

v

 

=={{header|Pascal}}==

=={{header|Perl}}==

{{trans|Tcl}}

{my @a = @_;

foreach my $i (0 .. $#a - 1)

$a[$_] < $a[$min] and $min = $_ foreach $min .. $#a;

$a[$i] > $a[$min] and @a[$i, $min] = @a[$min, $i];}

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">selection_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)))</span>

{{out}}

<pre>

=={{header|PHP}}==

Iterative:

$n = count($arr);

for($i = 0; $i < count($arr); $i++) {

list($arr[$i],$arr[$min]) = array($arr[$min],$arr[$i]);

}

Recursive:

if(count($arr) == 0){

return $result;

unset($arr[array_search(min($arr),$arr)]);

return selectionsort($arr,$nresult);

 

=={{header|PicoLisp}}==

(map

'((L) (and (cdr L) (xchg L (member (apply min @) L))))

Lst )

 

=={{header|PL/I}}==

Selection: procedure options (main); /* 2 November 2013 */

 

 

end Selection;

Results:

<pre>

 

=={{header|PowerShell}}==

{

$datal=$data.length-1

}

 

 

=={{header|Prolog}}==

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

selection_sort([], []).

selection_sort([H | L], [H1 | L2]) :-

nth0(Ind, L, H1, L2),

nth0(Ind, L1, H, L2)).

 

=={{header|PureBasic}}==

Protected i, j, lastIndex, minIndex

Swap a(minIndex), a(i)

Next

 

=={{header|Python}}==

 

for i, e in enumerate(lst):

mn = min(range(i,len(lst)), key=lst.__getitem__)

lst[i], lst[mn] = lst[mn], e

 

=={{header|Qi}}==

{{trans|sml}}

Small [] Output -> [Small | (selection-sort Output)]

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

 

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

 

=={{header|Quackery}}==

 

behead swap

witheach

[] 20 times [ 10 random join ]

dup echo cr

 

{{out}}

=={{header|R}}==

For loop:

{

lenx <- length(x)

}

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

{

if(length(x) > 1)

c(x[mini], selectionsort(x[-mini]))

} else x

 

=={{header|Ra}}==

class SelectionSort

**Sort a list with the Selection Sort algorithm**

list[i] := list[minCandidate]

list[minCandidate] := temp

 

=={{header|Racket}}==

#lang racket

(define (selection-sort xs)

[else (define x0 (apply min xs))

(cons x0 (selection-sort (remove x0 xs)))]))

 

=={{header|Raku}}==

(formerly Perl 6)

Solution 1:

for 0 ..^ @a.end -> $i {

my $min = [ $i+1 .. @a.end ].min: { @a[$_] };

say 'input = ' ~ @data;

say 'output = ' ~ @data.&selection_sort;

 

{{out}}

 

Solution 2:

for ^@tmp -> $i {

my $min = $i; @tmp[$i, $_] = @tmp[$_, $i] if @tmp[$min] > @tmp[$_] for $i^..^@tmp;

return @tmp;

}

 

{{out}}

 

=={{header|REXX}}==

call init /*assign some values to an array: @. */

call show 'before sort' /*show the before array elements. */

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|:}}

<pre>

 

=={{header|Ring}}==

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

see sortList(aList)

next

return list

 

=={{header|Ruby}}==

# a relatively readable version - creates a distinct array

 

puts "sequential_sort_with_swapping([7,6,5,9,8,4,3,1,2,0]): #{sequential_sort_with_swapping([7,6,5,9,8,4,3,1,2,0])}"

# prints: sequential_sort_with_swapping([7,6,5,9,8,4,3,1,2,0]): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

=={{header|Run BASIC}}==

dim srdData(siz)

for i = 1 to siz

for i = 1 to siz

print i;chr$(9);srtData(i)

<pre>1 20.5576419

2 32.4299311

 

=={{header|Rust}}==

fn selection_sort(array: &mut [i32]) {

 

println!(" The sorted array is {:?}", array);

}

 

=={{header|Scala}}==

 

def selectionSort(a: Array[Int]) =

for (i <- 0 until a.size - 1)

swap(a, i, (i + 1 until a.size).foldLeft(i)((currMin, index) =>

 

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

 

{ (i1: Int, i2: Int) => val tmp = a(i1); a(i1) = a(i2); a(i2) = tmp }

 

Functional way:

def remove(e: T, list: List[T]): List[T] =

list match {

}

}

 

=={{header|Seed7}}==

local

var integer: i is 0;

arr[i] := help;

end for;

 

Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#selectionSort]

=={{header|Sidef}}==

{{trans|Ruby}}

method selectionsort {

for i in ^(self.end) {

 

var strs = ["John", "Kate", "Zerg", "Alice", "Joe", "Jane"];

 

=={{header|Standard ML}}==

| selection_sort (first::lst) =

let

in

small :: selection_sort output

 

=={{header|Stata}}==

function selection_sort(real vector a) {

real scalar i, j, k, n

}

}

 

=={{header|Swift}}==

var min:Int

}

}

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}

 

 

=={{header|TI-83 BASIC}}==

 

=={{header|uBasic/4tH}}==

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

=={{header|Ursala}}==

is deleted from the list and inserted into another on each iteration

rather than swapped with a preceding item of the same list.

 

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.

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

numbers.

#cast %nL

 

{{out}}

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

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

 

sub swap( byref a, byref b)

dim tmp

selectionSort = a

end function

 

=={{header|VBScript}}==

arr = Split(s,",")

For i = 0 To UBound(arr)

WScript.StdOut.Write "3,2,5,4,1" & vbTab & Selection_Sort("3,2,5,4,1")

WScript.StdOut.WriteLine

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Go}}

var last = a.count - 1

for (i in 0...last) {

}

 

System.print("Before: %(a)")

selectionSort.call(a)

System.print("After : %(a)")

System.print()

 

{{out}}

Alternatively we can just call a library method.

{{libheader|Wren-sort}}

 

System.print("Before: %(a)")

Sort.selection(a)

System.print("After : %(a)")

System.print()

 

{{out}}

 

=={{header|XPL0}}==

string 0; \use zero-terminated strings

 

SelSort(Str, StrLen(Str));

Text(0, Str); CrLf(0);

 

{{out}}

 

=={{header|zkl}}==

copy,r:=list.copy(),List();

while(copy){

}

r

{{out}}

<pre>