Selection sort

From CodeCodex

Related content:

Selection sort is a sorting algorithm, a comparison sort that works as follows:

  1. find the minimum value in the list
  2. swap it with the value in the first position
  3. sort the remainder of the list (excluding the first value)

It is probably the most intuitive sort algorithm to invent.

Implementations[edit]

C[edit]

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]

Common Lisp[edit]

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

D[edit]

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]

Erlang[edit]

select_sort([]) -> [];
select_sort(List) -> select_sort(List, []).

select_sort([], Sorted) -> Sorted;
select_sort([H|T], Sorted) ->
    {Max, Rest} = select_max(T, H, []),
    select_sort(Rest, [Max|Sorted]).

select_max([], Max, Rest) -> {Max, Rest};
select_max([H|T], Max, Rest) when H < Max ->
    select_max(T, Max, [H|Rest]);
select_max([H|T], Max, Rest) ->
    select_max(T, H, [Max|Rest]).

Java[edit]

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

OCaml[edit]

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]

Perl[edit]

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

PHP[edit]

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;
      $tmp = $arr[$min];
      $arr[$min] = $arr[$i];
      $arr[$i] = $tmp;
   }
}

Python[edit]

  def ssort(V):                            #V is the list to be sorted
    j = 0                                #j is the "current" ordered position, starting with the first one in the list
    while j != len(V):                   #this is the replacing that ends when it reaches the end of the list
        for i in range(j, len(V)):       #here it replaces the minor value that it finds with j position
            if V[i] < V[j]:              #but it does it for every value minor than position j
                V[j],V[i] = V[i],V[j]
        j = j+1                          #and here's the addiction that limits the verification to only the next values
    return V
another method

  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
another method
a=input("Enter the length of the list :")          # too ask the user length of the list
l=[]                                              # take a emty list
for g in range (a):                              # for append the values from user 
	b=input("Enter the element :")           # to ask the user to give list values
	
	l.append(b)                              # to append a values in a empty list l
print "The given eliments list is",l
for  i in range (len(l)):                         # to repeat the loop take length of l
	index=i                                 # to store the values i in string index
	num=l[i]                                # to take first value in list and store in num
	for j in range(i+1,len(l)):              # to find out the small value in a list read all values
		if num>l[j]:                    # to compare two values which store in num and list
			index=j                 # to store the small value of the loop j in index
			num=l[j]                # to store small charecter are value in num
	tem=l[i]                               # to swap the list take the temparary list stor list vlaues
	l[i]=l[index]                         # to take first value as another
	l[index]=tem
print "After the swping the list by selection sort is",l

Ruby[edit]

def selectionsort(list)
  list.size.times 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

Seed7[edit]

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]

Turing[edit]

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