Sorting algorithms/Selection sort: Difference between revisions

 

;Task:

 

 

 

Its primary purpose is for when writing data is very expensive (slow) when compared to reading, eg. writing to flash memory or EEPROM.

 

 

<br><br>

 

=={{header|360 Assembly}}==

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

</pre>

 

 

=={{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|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|C}}==

 

 

void selection_sort (int *a, int n) {

return 0;

}

{{out}}

<pre>

4 65 2 -31 0 99 2 83 782 1

-31 0 1 2 2 4 65 83 99 782

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

test

this</pre>

 

=={{header|Clojure}}==

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:

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

#(9 8 7 6 5 4 3 2 1 0)</pre>

 

=={{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|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>

Unsorted: 1 27 32 99 1 -7 3 5 7

Sorted: -7 1 1 3 5 7 27 32 99

</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:

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

</pre>

 

=={{header|Euphoria}}==

object tmp

integer m

pretty_print(1,s,{2})

puts(1,"\nAfter: ")

 

{{out}}

 

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

let rec ssort = function

[] -> []

| x::xs ->

let min, rest =

(x, []) xs

in min::ssort rest

 

=={{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>

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

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

</pre>

 

=={{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 [] = []

 

=={{header|Haxe}}==

 

 

 

=={{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.

on string : "qwerty"

with op = &null: "eqrtwy" (0 ms)</pre>

 

=={{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>

]

</pre>

=={{header|Julia}}==

for i in 1:len-1

end

end

end

 

 

{{out}}

 

 

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

dim A(itemCount)

for i = 1 to itemCount

print

return

 

=={{header|Lua}}==

for k = 1, #f-1 do

local idx = k

for i in next, f do

print( f[i] )

 

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

var m = i

if a[j] < a[m]:

m = j

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

 

s loop: i [

i dup ->k b at

]

 

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

 

{{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|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|REXX}}==

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

call selectionSort # /*invoke selection sort (and # items). */

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

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

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

<pre>

element 1 before sort: ---The seven hills of Rome:---

 

=={{header|Ring}}==

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

see sortList(aList)

next

return list

 

=={{header|Ruby}}==

end

end

end

end

 

=={{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

9 95.4280853

10 98.8323211</pre>

 

=={{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 {

}

}

}

}

var nums = [7,6,5,9,8,4,3,1,2,0];

say nums.selectionsort;

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

 

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

| selection_sort (first::lst) =

let

in

small :: selection_sort output

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

The selection_sort function is parameterized by a relational predicate p.

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>

3,2,5,4,1 1,2,3,4,5

c,e,b,a,d a,b,c,d,e

</pre>

 

=={{header|XPL0}}==

string 0; \use zero-terminated strings

 

SelSort(Str, StrLen(Str));

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

 

{{out}}

.Pabcdeefghiiijklmnoooqrstuuvwxyz

</pre>

 

{{omit from|GUISS}}