Ordenamiento por selección

Ordenamiento por selección

Consiste en encontrar el menor de todos los elementos del vector e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenarlo todo.

Representación animada del ordenación por selección :

Representación animada del ordenación por selección

  1. PROCEDIMIENTO selection_sort ( Vector a[1:n])
  2.     PARA i VARIANDO DE 1 HASTA n - 1 HACER
  3.         ENCONTRAR [j] EL ELEMENTO MÁS PEQUEÑO DE [i + 1:n];
  4.         INTERCAMBIAR [j] Y [i];
  5. FIN PROCEDIMIENTO;
  1. let rec mas_pequeno tab comienzo fin =
  2.     if (comienzo == fin) then comienzo else
  3.     let temp =mas_pequeno tab (comienzo+1) fin in
  4.     if tab.(comienzo) > tab.(temp) then temp else comienzo;;
  5.        
  6. let selection_sort vector =
  7.     for actual = 0 to 18 do    
  8.         let p = mas_pequeno vector (actual+1) 19 in
  9.         begin
  10.             if p <> actual then
  11.             begin
  12.                 let a = vector.(actual) in
  13.                 begin
  14.                     vector.(actual) <- vector.(p);
  15.                     vector.(p) <- a;
  16.                 end;
  17.             end;
  18.         end;
  19.     done;
  20. vector;;
  1. type tab = array[1..20] of integer;
  2. procedure selection_sort(var vector : tab);
  3. var
  4.   temp: integer;
  5.   actual, mas_pequeno, j : integer;
  6.  
  7. begin
  8.   for actual:= 1 to 19 do
  9.   begin
  10.     mas_pequeno := actual;
  11.     for j:= actual + 1 to 20 do
  12.     begin
  13.       {Encontrar el elemento más pequeño}
  14.       if vector[j] < vector[mas_pequeno] then mas_pequeno:= j;
  15.     end;
  16.     {Guarde el elemento más pequeño en la posición "actual"}
  17.     temp:= vector[actual];
  18.     vector[actual]:= vector[mas_pequeno];
  19.     vector[mas_pequeno]:=temp;
  20.   end;
  21. end;
  1. def selection_sort(vector):
  2.     nb = len(vector)
  3.     for actual in range(0,nb):    
  4.         mas_pequeno = actual
  5.         for j in range(actual+1,nb) :
  6.             if vector[j] < vector[mas_pequeno] :
  7.                 mas_pequeno = j
  8.         if min is not actual :
  9.             temp = vector[actual]
  10.             vector[actual] = vector[mas_pequeno]
  11.             vector[mas_pequeno] = temp
  1. void selection_sort(int *vector, int taille)
  2. {
  3.      int actual, mas_pequeno, j, temp;
  4.  
  5.      for (actual = 0; actual < taille - 1; actual++)
  6.      {
  7.          mas_pequeno = actual;
  8.          for (j = actual 1; j < taille; j++)
  9.               if (vector[j] < vector[mas_pequeno])
  10.                   mas_pequeno = j;
  11.           temp = vector[actual];
  12.           vector[actual] = vector[mas_pequeno];
  13.           vector[mas_pequeno] = temp;
  14.      }
  15. }

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 


Rendimiento del algoritmo

Cada búsqueda requiere comparar todos los elementos no clasificados, de manera que el número de comparaciones C(n) no depende del orden de los términos, si no del número de términos; por lo que este algoritmo presenta un comportamiento constante independiente del orden de los datos. C(n)= n(n-1)/2. Luego la complejidad es del orden Θ(n2).

Rendimiento del ordenación por selección Número de operaciones Número de términos Θ(n2)