DAA - Orden de selección

Este tipo de clasificación se llama Selection Sortya que funciona ordenando elementos repetidamente. Funciona de la siguiente manera: primero encuentre el más pequeño en la matriz e intercambie con el elemento en la primera posición, luego busque el segundo elemento más pequeño e intercambie con el elemento en la segunda posición, y continúe de esta manera hasta que toda la matriz esté ordenados.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

El ordenamiento por selección es una de las técnicas de ordenación más simples y funciona muy bien para archivos pequeños. Tiene una aplicación bastante importante, ya que cada elemento se mueve como máximo una vez.

La clasificación de secciones es un método de elección para clasificar archivos con objetos muy grandes (registros) y claves pequeñas. El peor de los casos ocurre si la matriz ya está ordenada en orden descendente y queremos ordenarlas en orden ascendente.

No obstante, el tiempo requerido por el algoritmo de clasificación de selección no es muy sensible al orden original de la matriz que se va a clasificar: la prueba si A[j] < min x se ejecuta exactamente el mismo número de veces en todos los casos.

La ordenación por selección pasa la mayor parte del tiempo tratando de encontrar el elemento mínimo en la parte no ordenada de la matriz. Muestra claramente la similitud entre el ordenamiento por selección y el ordenamiento por burbujas.

  • La clasificación de burbujas selecciona el máximo de elementos restantes en cada etapa, pero desperdicia algo de esfuerzo en impartir algo de orden a una parte no clasificada de la matriz.

  • El ordenamiento por selección es cuadrático tanto en el peor de los casos como en el promedio, y no requiere memoria adicional.

Para cada i desde 1 a n - 1, hay un intercambio y n - i comparaciones, por lo que hay un total de n - 1 intercambios y

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparaciones.

Estas observaciones son válidas, independientemente de los datos de entrada.

En el peor de los casos, esto podría ser cuadrático, pero en el caso promedio, esta cantidad es O(n log n). Implica que elrunning time of Selection sort is quite insensitive to the input.

Implementación

Void Selection-Sort(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; 
   } 
}

Ejemplo

Unsorted list:
5 2 1 4 3

1 st iteración:

Más pequeño = 5

2 <5, más pequeño = 2

1 <2, más pequeño = 1

4> 1, más pequeño = 1

3> 1, más pequeño = 1

Intercambiar 5 y 1
1 2 5 4 3

2 nd iteración:

Más pequeño = 2

2 <5, más pequeño = 2

2 <4, más pequeño = 2

2 <3, más pequeño = 2

Sin intercambio
1 2 5 4 3

3 ª iteración:

Más pequeño = 5

4 <5, más pequeño = 4

3 <4, más pequeño = 3

Intercambiar 5 y 3
1 2 3 4 5

4 º iteración:

Más pequeño = 4

4 <5, más pequeño = 4

Sin intercambio
1 2 3 4 5

Finalmente,

the sorted list is
1 2 3 4 5