¿Cómo implementar la ordenación por selección en C?

La clasificación por selección es otro algoritmo que opera ubicando el entero más bajo de la matriz y luego asignándolo a la posición superior. El índice junto a la posición del entero más pequeño se usará para comenzar la siguiente matriz que debe escanearse.

Ejemplo de clasificación de selección en C

Si tomamos una matriz con números [10,2,8,4,6] en la que el número más pequeño es 2. Así, colocaremos el número más pequeño, que es 2, en la primera posición, después de lo cual la matriz se verá como [2,10,8,4,6]. A continuación, tomaremos el siguiente número más pequeño porque 2 ya está en su posición correcta ahora. El siguiente número más pequeño es 4, que se colocará en la segunda posición, después de lo cual se buscará en la matriz de manera similar hasta que finalmente se ordene.

El ordenamiento por selección en C ordena los números en orden ascendente. Al modificar el algoritmo, los números se pueden organizar en una ordenación de selección descendente que también se puede realizar en otros lenguajes además de C, como la ordenación de selección C ++ o la ordenación de selección Python.

Aprenda cursos de desarrollo de software en línea de las mejores universidades del mundo. Obtenga Programas PG Ejecutivos, Programas de Certificado Avanzado o Programas de Maestría para acelerar su carrera.

Algoritmo de clasificación de selección

• Primero, establecemos que el elemento inicial en la ordenación por selección sea el mínimo y buscamos el elemento más pequeño en la matriz para el procedimiento correcto del algoritmo de ordenación por selección .
• El elemento mínimo se compara ahora con el segundo componente. Si el segundo elemento cae por debajo del mínimo, los intercambiaremos y luego asignaremos al tercer elemento un valor mínimo.
• De lo contrario, continuaremos con el tercer elemento y lo compararemos con el mínimo. Si el segundo elemento excede nuestro primer elemento, lo intercambiaremos. Repita este proceso hasta el último componente.
• Después de cada iteración, veremos que nuestro mínimo ha llegado al principio de la lista sin ordenar.
• Comenzaremos a indexar desde la primera entrada de la lista desordenada para cada iteración. Hasta que la lista esté ordenada o todos los componentes estén colocados adecuadamente, repetiremos los pasos 1 a 4 varias veces.

Cursos y artículos populares sobre ingeniería de software

El siguiente ejemplo con cada iteración ayudará a comprender el proceso de clasificación de selección en C en detalle:

Iteración #1

Yo [ ] = 8,5,2,6,4

Establecer un mínimo – 8

Compara i 0 e i 1

Como, i 0 > i 1 , establecer mínimo = 5.

• Compara i 1 e i 2

Como, i 1 > i 2 , establezca mínimo = 2.

• Compara i 2 e i 3

Como, i 2 < i 3 , establecer mínimo = 2.

• Compara i 2 e i 4

Como, i 2 < i 4 , establecer mínimo =2.

2 es el número más pequeño de todos los elementos, debemos intercambiar i 0 e i 2

­ Iteración #2

Yo [ ]= 2,5,8,6,4

Establecer mínimo 5

• Compara i 1 e i 2

Como, i 1 < i 2 , establezca mínimo = 5.

• Compara i 1 e i 3

Como i 1 < i 3, establecer mínimo = 5

• Compara i 1 e i 4

Nuevamente, i 1 < i 4 , establezca mínimo = 4.

4 es el elemento más pequeño de la matriz, por lo tanto, debemos intercambiar i 1 e i 4 .

Iteración #3

Yo [ ]= 2,4,8,6,5

Establecer mínimo 8

• Compara i 2 e i 3

Como, i 2 > i 3 , establezca mínimo = 6.

• Compara i 3 e i 4

Como, i 3 > i 4 , establecer mínimo = 5.

5 es el elemento más pequeño de la matriz, debe intercambiar i 2 e i 4 .

Iteración #4

Yo [ ] = 2,4,5,6,8

Establecer mínimo 6

• Compara i 3 e i 4

Como i 3 < i 4 , establezca mínimo = 6.

El mínimo se coloca en el lugar correcto; por lo tanto, no se producirá ningún intercambio.

Ejemplo de clasificación de selección en C

// Ordenar por selección en C

#incluir <stdio.h>

// función para intercambiar la posición de dos elementos

intercambio vacío (int * a, int * b) {

temperatura interna = *a;

*a = *b;

*b = temperatura;

}

void selección Ordenar (arreglo int [], tamaño int) {

for (int paso = 0; paso < tamaño – 1; paso++) {

int min_idx = paso;

for (int i = paso + 1; i < tamaño; i++) {

// Para ordenar en orden descendente, cambie > por < en esta línea.

// Selecciona el elemento mínimo en cada bucle.

si (matriz[i] <matriz[min_idx])

min_idx = yo;

}

// poner min en la posición correcta

swap(&matriz[min_idx], &matriz[paso]);

}

}

// función para imprimir una matriz

void imprimirArray(matriz int[], tamaño int) {

para (int i = 0; i < tamaño; ++i) {

printf(“%d”, arreglo[i]);

}

imprimirf(“\n”);

}

// código del controlador

int principal() {

datos int[] = {20, 12, 10, 15, 2};

tamaño int = tamaño de (datos) / tamaño de (datos [0]);

selecciónOrdenar(datos, tamaño);

printf(“Array ordenado en orden ascendente:\n”);

printArray(datos, tamaño);

}

Análisis de complejidad del ordenamiento por selección

Entrada: se dan n elementos de entrada.

Salida: el número de pasos necesarios para ordenar la lista.

Lógica: si nos dan n elementos, hará n-1 comparaciones en el primer paso, n-2 comparaciones en el segundo paso, n-3 comparaciones en el tercer paso, y así sucesivamente. En consecuencia, el número total de comparaciones puede calcularse utilizando el;

Producción -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Suma = n(n-1)/2 es decir, O(n²)

Debido a que el método de clasificación por selección necesita algo de espacio de memoria adicional para las variables temporales para el intercambio, tiene una complejidad de tiempo de O(n2) y una complejidad de espacio de O(1).

Análisis de complejidad de tiempo de clasificación de selección

Mejor caso: para la matriz que se ha ordenado previamente, el método de ordenación por selección tiene una complejidad de tiempo en el mejor de los casos de O(n²).

Caso promedio: el algoritmo de ordenación por selección tiene una complejidad de tiempo de caso promedio de O(n²) cuando los elementos se ordenan de forma desordenada, es decir, ni en orden ascendente ni descendente.

Peor caso: cuando invertimos el orden descendente de una matriz en orden ascendente, la complejidad temporal del peor caso es O(n²).

La complejidad temporal del método de clasificación por selección es O(n²) en cada uno de los tres escenarios. Esto se debe a que debemos identificar los elementos mínimos de cada etapa para organizarlos adecuadamente. Después de rastrear toda la matriz, habremos encontrado nuestro elemento mínimo.

Conclusión

Esto trae el final de la publicación de blog sobre "Ordenar por selección en C". Debe comprender que también se puede realizar en otros lenguajes, como Selection Sort C++ y Selection Sort Python. Esperamos que este artículo lo ayude a comprender cómo ordenar elementos en C.

La clasificación de selección no es el único segmento en el viaje de convertirse en programador. Si espera obtener un impulso significativo en su carrera de desarrollo de software con un título profesional, ¡upGrad está aquí! desarrollo frontend (JavaScript, HTML, CSS), backend (NoSQL-MongoDB) y microservicios de upGrad, luego puede seguir el curso de Maestría en Ciencias en Ciencias de la Computación de UpGrad. Impartido por IIIT Bangalore y LJMU Alumni Status, este curso lo ayuda a iniciar su carrera como ingeniero de software/desarrollador full-stack con los gigantes tecnológicos de todo el mundo.

Este curso cubre el conocimiento básico de herramientas como Java, Spring e Hibernate, fortaleciendo nuestras habilidades de desarrollo completo para explorar el mercado laboral con oportunidades notables.

¡ Regístrese para obtener más información!