Algorithm Implementation/Sorting/Selection sort

From Wikibooks, open books for an open world
Jump to: navigation, search

This article describes implementations of the selection sort sorting algorithm in a variety of real-world programming languages.

BASIC[edit]

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 i

C/C++[edit]

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]

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]

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

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]

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

JavaScript[edit]

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;
 
        tmp2 = sortMe[tmp];
        sortMe[tmp] = sortMe[i];
        sortMe[i] = tmp2;
    }
}

ML[edit]

(* 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]

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

PHP[edit]

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

Python[edit]

def selectionSort(items):
    n = len(items)
    for i in range(n - 1):
        min = i
        for j in range(i + 1, n):
            if items[j] < items[min]:
                min = j
        if min != i:
            items[i], items[min] = items[min], items[i]

Ruby[edit]

  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