Algorithm Implementation/Sorting/Selection sort
Appearance
This article describes implementations of the selection sort sorting algorithm in a variety of real-world programming languages.
BASIC
[edit | edit source]For i = 1 To n - 1
min = i
For j = i + 1 To n
If x(min) > x(j) Then
min = j
End If
Next j
temp = x(i)
x(i) = x(min)
x(min) = temp
Next
C/C++
[edit | edit source]void selection(int *array, int length)
{
int max, i, temp;
while (length > 0)
{
max = 0;
for (i = 1; i < length; i++)
if (array[i] > array[max])
max = i;
temp = array[length-1];
array[length-1] = array[max];
array[max] = temp;
length--;
}
}
C
[edit | edit source]This is an implementation of the unstable variant:
int selectionSort(int data[], int count)
{
int i, j;
int tmp;
int minimum;
for (i = 0; i < count - 1; i++)
{
minimum = i; /* current minimum */
/* find the global minimum */
for (j = i + 1; j < count; j++)
if (data[minimum] > data[j])
minimum = j; /* new minimum */
/* swap data[i] and data[minimum] */
tmp = data[i];
data[i] = data[minimum];
data[minimum] = tmp;
}
return 0;
}
This is an implementation of the stable variant:
void selectionSort(int data[], int count)
{
int i, j, m, mi;
for (i = 0; i < count - 1; i++)
{
/* find the minimum */
mi = i;
for (j = i + 1; j < count; j++)
if (data[j] < data[mi])
mi = j;
m = data[mi];
/* move elements to the right */
for (j = mi; j > i; j--)
data[j] = data[j-1];
data[i] = m;
}
}
C++
[edit | edit source]#include <algorithm> // for: std::iter_swap, std::min_element
template <typename Iterator>
void selection_sort(Iterator begin, Iterator end)
{
Iterator min;
while (begin != end)
{
min = std::min_element(begin, end);
std::iter_swap(begin, min);
++begin;
}
}
C#
[edit | edit source]public void sortArray(int[] intArray)
{
int min, temp;
for (int i = 0; i < intArray.Length - 1; i++)
{
min = i;
for (int j = i + 1; j < intArray.Length; j++)
if (intArray[j] < intArray[min])
min = j;
// swap the values
temp = intArray[i];
intArray[i] = intArray[min];
intArray[min] = temp;
}
}
Java
[edit | edit source]An iterative implementation:
public static int[] selectionsort(int[] numbers)
{
for (int i = 0; i < numbers.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < numbers.length; j++)
if (numbers[j] < numbers[index]) //Finds smallest number
index = j;
int smallerNumber = numbers[index]; //Swap
numbers[index] = numbers[i];
numbers[i] = smallerNumber;
}
return numbers;
}
A recursive implementation:
public static int findMin(int[] array, int index)
{
int min = index - 1;
if (index < array.length - 1)
min = findMin(array, index + 1);
if (array[index] < array[min])
min = index;
return min;
}
public static void selectionSort(int[] array)
{
selectionSort(array, 0);
}
public static void selectionSort(int[] array, int left)
{
if (left < array.length - 1)
{
swap(array, left, findMin(array, left));
selectionSort(array, left+1);
}
}
public static void swap(int[] array, int index1, int index2)
{
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
function selectionSort (sortMe)
{
var i, j, tmp, tmp2;
for (i = 0; i < sortMe.length - 1; i++)
{
tmp = i;
for (j = i + 1; j < sortMe.length; j++){
if (sortMe[j] < sortMe[tmp]){
tmp = j;
}
}
if(tmp!=i){
tmp2 = sortMe[tmp];
sortMe[tmp] = sortMe[i];
sortMe[i] = tmp2;
}
}
}
ML
[edit | edit source](* Selection sort is modified slightly for use on linked lists (which are the only inbuilt array-like structures in ML)
in a functional programming language *)
fun selection_sort [] = []
| selection_sort (first::lst) =
let
fun select_r small ([], output) = small::(selection_sort output)
| select_r small (x::xs, output) =
if (x< small) then
select_r x (xs, small::output)
else
select_r small (xs, x::output)
in
select_r first (lst, [])
end
;
Ocaml
[edit | edit source](* Gets the minimum element of the list *)
let rec min lst =
match lst with
x::[] -> x
| (x::tl) -> let mintl = min tl in
if x < mintl then x else mintl;;
(* Removes a given element from the list *)
let rec remove(x,lst) =
match lst with
[] -> []
| (y::tl) -> if x=y then tl else y::(remove(x,tl));;
(* Sorts a list by repeatedly extracting the minimum *)
let rec selectionSort(lst) =
match lst with
[] -> []
| _ -> let m = min lst in m::(selectionSort(remove(m,lst)));;
Phix
[edit | edit source]function selection_sort(sequence s)
integer m
for i=1 to length(s) do
m = i
for j=i+1 to length(s) do
if s[j]<s[m] then
m = j
end if
end for
{s[i],s[m]} = {s[m],s[i]}
end for
return s
end function
PHP
[edit | edit source]function selectionSort(&$a)
{
$n = count($a);
for ($i = 0; $i < $n - 1; $i++)
{
$min = $i;
for ($j = $i + 1; $j < $n; $j++)
if ($a[$j] < $a[$min])
$min = $j;
list($a[$i], $a[$min]) = array($a[$min], $a[$i]);
}
}
newList = [6,7,4,5,1]
for outer in range(len(newList)):
minimum = min(newList[outer:]) #find minimum element
minIndex = newList[outer:].index(minimum) #find index of minimum element
newList[outer + minIndex] = newList[outer] #replace element at minIndex with first element
newList[outer] = minimum #replace first element with min element
print newList
Ruby
[edit | edit source] def sort!(keys)
for i in 0..keys.size-2
min = i
for j in i+1..keys.size-1
min = j if keys[j] < keys[min]
end
keys[i], keys[min] = keys[min], keys[i]
end
keys
end