Selection sort
From CodeCodex
| Related content: |
|
| Image:Wikipedia-logo.png | See Wikipedia's Article for Selection sort. |
Selection sort is a sorting algorithm, a comparison sort that works as follows:
- find the minimum value in the list
- swap it with the value in the first position
- sort the remainder of the list (excluding the first value)
It is probably the most intuitive sort algorithm to invent.
This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time. Among simple O(n2) algorithms, it is generally outperformed by insertion sort, but still tends to outperform contenders such as bubble sort and gnome sort.
Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), this algorithm is stable (but slower). Selection sort is an in-place algorithm.
Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum.
A bidirectional variant of selection sort, called shaker sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. Note, however, that shaker sort more often refers to a bidirectional variant of bubble sort.
Contents |
[edit] Implementations
[edit] C
void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;
for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
Original source: [1]
[edit] D
D version 1.x:
import std.stdio: writefln;
void selectionSort(T)(T[] items) {
foreach(i, xi; items[0 .. $-1]) {
int min = i;
for (int j = i+1; j < items.length; j++)
if (items[j] < items[min])
min = j;
items[i] = items[min];
items[min] = xi;
}
}
void main() {
auto a1 = "31415code9265codex358";
selectionSort(a1);
writefln(a1);
auto a2 = [3.2, 5.1, 0.0, -3.6, 11.1, 5.1];
selectionSort(a2);
writefln(a2);
}
The output:
112334555689ccddeeoox [-3.6,0,3.2,5.1,5.1,11.1]
[edit] Common Lisp
This is a recursive version. It doesn't really swap the values, it just creates a new list from the old one and returns that.
(defun selection-sort (list)
(when list
(let ((minimum-element (reduce #'min list)))
(cons minimum-element
(selection-sort (remove minimum-element list))))))
[edit] Java
public void selectionSort(int data[],int n)
// pre: 0<=n <= data.length
// post: values in data[0..n-1] in ascending order
{
int numUnsorted=n; // number of values not in order
int index; // general index
int max;
int temp;
while (numUnsorted > 0)
{
//determine a maximum value in Array
max=0;
for (index=1; index < numUnsorted; index++)
if (data[max] < data[index])
max=index;
// swap data[max] and data[numUnsorted-1]
temp = data[max];
data[max] = data[numUnsorted-1];
data[numUnsorted-1] = temp;
numUnsorted--;
}
}
[edit] OCaml
The following function returns a pair of the smallest element in a list and the remaining list:
# let rec select x = function
| [] -> x, []
| h::t ->
let x, h = if x<h then x, h else h, x in
let x, t = select x t in
x, h::t;;
val select : 'a -> 'a list -> 'a * 'a list = <fun>
The selection sort uses the "select" function to prepend each smallest element in turn:
# let rec sort = function
| [] -> []
| h::t -> match select h t with
| h, t -> h::sort t;;
val sort : 'a list -> 'a list = <fun>
For example:
# sort [1;6;2;7;3;8;4;9;5];; - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
[edit] Perl
sub selectionSort {
my @list = @_;
for my $i (0 .. $#list - 1) {
my $min = $i;
for my $j ($i .. $#list) {
if ($list[$j] < $list[$min]) {
$min = $j;
}
}
if ($i != $min) {
@list[$i, $min] = @list[$min, $i];
}
}
return @list;
}
my @unsorted = reverse(1 .. 10);
my @sorted = selectionSort(@unsorted);
[edit] Python
def selection_sort(list):
l=list[:] # create a copy of the list
sorted=[] # this new list will hold the results
while len(l): # while there are elements to sort...
lowest=l[0] # create a variable to identify lowest
for x in l: # and check every item in the list...
if x<lowest: # to see if it might be lower.
lowest=x
sorted.append(lowest) # add the lowest one to the new list
l.remove(lowest) # and delete it from the old one
return sorted
[edit] Ruby
def selectionsort(list)
0.upto(list.size-1) do |start|
min = start
start.upto(list.size-1) do |i|
min = i if list[i] < list[min]
end
list[start], list[min] = list[min], list[start]
end
list
end
[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) do
min := i;
for j range succ(i) 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: [2]
[edit] Turing
var nombres, limit : int
get nombres
get limit
var last, smaller, bigger : int := 0
var rann, sort: array 1 .. nombres of int
for i : 1 .. nombres
rann (i) := Rand.Int (0, limit)
end for
for v : 1 .. upper (rann)
bigger := limit
for b : 1 .. upper (rann)
if rann (b) < bigger then
last := b
bigger := rann (b)
end if
end for
sort (v) := rann (last)
rann (last) := limit
end for
for b : 1 .. upper (sort)
put " ", sort (b) ..
end for
