Implémentation d'algorithmes classiques/Algorithmes de tri/Tri par sélection

C

void selection(int *t, int taille)
{
     int i, mini, j, x;

     for (i = 0; i < taille - 1; i++)
     {
         mini = i;
         for (j = i + 1; j < taille; j++)
              if (t[j] < t[mini])
                  mini = j;
          x = t[i];
          t[i] = t[mini];
          t[mini] = x;
     }
}

C++

Old C++ (before 2011)

void triSelection(int tab[], int const taille)
{
    int i, min, j;

    for (i = 0; i < taille - 1; ++i)
    {
        min = i;
        for (j = i + 1; j < taille; ++j)
        {
            if (tab[j] < tab[min])
            {
                min = j;
            }
        }
        if (min != i)
        {
            std::swap(tab[i], tab[min]); // defined in <algorithm> before C++11
        }
    }
}

Modern C++ ( use -std=c++11 to compile )

template< typename T >
void triSelection( T& tab )
{
	typename T::iterator min, jt;

	for( typename T::iterator it = tab.begin(); it < tab.end()-1; ++it )
	{
		min = it;
		for( jt = it+1; jt < tab.end(); ++jt )
		{
			if( *jt < *min )
			{
				min = jt;
			}
		}
		if( min != it )
		{
			std::swap( *it, *min );
		}
	}
}

Note that this example can not be used with classic arrays ( "int tab[50];" ) but it can be used with any container, including std::array, which is a classic array in the final binary. The advantage of std::array being that you can retrieve it's size without the need of global constants ( no need to do things like "#define SIZE 50" or "const size_t SIZE = 50;" as in C, and so less dangers of error when you do changes ).

Caml

Tri de vecteurs en Caml Light, en ordre décroissant :

let tri_select t =
  let n = vect_length t and m = ref(0) and i = ref(0) in
     for j=0 to (n - 2) do
       m := t.(j);
       i := j;
       for k = (j + 1) to (n - 1) do
          if !m < t.(k) then begin
                             m:= t.(k);
                             i:= k;
                             end
                             
       done;       
   t.(!i) <- t.(j); t.(j) <- !m;
  done;
t;;

Haskell

selTri :: Ord a 26 => [a] -> [a]
remFirstOcc :: Ord a => a->[a] -> [a]

selTri [] = []
selTri l = m: selTri (remFirstOcc m l)
  where m = minimum l

remFirstOcc n (x:xs)
	| (x == n) =  xs
	| otherwise = x:(remFirstOcc n xs)

Java ou C#

 public void sortBySelection(int[] t, int sizeOfTheCollection) {

     int i, min, j , x;
     for(i = 0 ; i < sizeOfTheCollection - 1 ; i++)
     {
         min = i;
         for(j = i+1 ; j < sizeOfTheCollection; j++)
              if(t[j] < t[min])
                  min = j;
         if(min != i)
         {
             x = t[i];
             t[i] = t[min];
             t[min] = x;
         }
     }

 }

JavaScript

T est un tableau de nombres dont le premier indice est 0, et n est un entier tel que l'on souhaite trier T[0..n-1].

function executer_tri_par_selection (T, n) {
    if (T.length < 2) return T;
    var i, indice_min, j, temp;
    for (i = 0; i < n - 1; i++) {
        indice_min = i;
        for (j = i + 1; j < n; j++) {
            if (T[j] < T[indice_min])
                indice_min = j;
        }
        if (indice_min != i) {
            temp = T[i];
            T[i] = T[indice_min];
            T[indice_min] = temp;
        }
    }
    return T;
}

Pascal

 procedure TriSelection(n : integer ; var t : tab);
 var i, j, min, tmp : integer;
 begin
    for i := 1 to n - 1 do begin
       min := i;
 
       for j := i + 1 to n do
          if (t[j] < t[min]) then min:=j;
 
       if (i <> min) then begin
          tmp := t[i];
          t[i] := t[min];
          t[min] := tmp;
       end;
    end; 
 end;

PHP

function triSelection(&$arrayOf)
{
	$count = count($arrayOf);
	for($i=0;$i<$count-1;$i++)
	{
		$min = $i;
		$minV = $arrayOf[$min];
		for($j=$i+1;$j<$count;$j++)
		{
			if($arrayOf[$j] < $minV)
			{
				$min = $j;
				$minV = $arrayOf[$min];
			}
		}
	
		if($min != $i)
		{
			$arrayOf[$min] = $arrayOf[$i];
			$arrayOf[$i] = $minV;
		}
	}
}

Python

import random

MAX_LENGTH = 100
un_tableau = [ k for k in range(0,MAX_LENGTH) ]
random.shuffle(un_tableau)

for k in range(0,MAX_LENGTH) :
    min = k
    for l in range(k+1, MAX_LENGTH) :
        if un_tableau[l] < un_tableau[min] :
            min = l
    if min is not k :
        number = un_tableau[k]
        un_tableau[k] = un_tableau[min]
        un_tableau[min] = number

Tout ou partie de cette page est issue de l'article Wikipédia « Tri par sélection » dans sa version du 22/04/2010.