¿Qué es la ordenación por selección en python?

La mayoría de los lenguajes de programación tienen una función de clasificación incorporada, pero debemos comprender los algoritmos de clasificación para comprender el código de manera efectiva. El algoritmo que vamos a explorar en este blog es el tipo de selección.

Un algoritmo de ordenación por selección ordena los elementos al iterar sobre toda la matriz. Selecciona el elemento más pequeño de la matriz no ordenada y lo intercambia con el elemento presente en el primer índice.

Encuentra el siguiente elemento más pequeño de la matriz no ordenada y lo intercambia con el elemento en el segundo índice. Esto continúa hasta que llegamos a nuestra matriz ordenada resultante.

Entendemos el concepto en diferentes lenguajes de programación.

Aprende más de python con estos temas:

Operación de clasificación selectiva

Los algoritmos básicos son un conjunto de instrucciones que ingresas en las computadoras para completar una tarea.

Un algoritmo de clasificación de selección dividirá su entrada en subsecciones ordenadas y no ordenadas. Inicialmente, nuestra matriz no está ordenada y, a medida que aplicamos la selección para ordenar el algoritmo, elige un elemento de la sección no ordenada y lo mueve a la sección ordenada.

Otra cosa importante para recordar es que mantiene el elemento ordenado más pequeño al comienzo de la matriz de salida.

Aquí tenemos una matriz desordenada de elementos:

21128191

Tabla 1

Buscaremos el número más pequeño en toda la matriz y lo intercambiaremos con el elemento en el primer índice.

21128191

Tabla 2

Intercambiaremos 2 con 1, y luego nuestra matriz se convierte en la siguiente. Ahora buscaremos el siguiente elemento más pequeño y lo reemplazaremos con 11.

11128192

Tabla 3

Después de intercambiar, obtenemos la secuencia de nuestra matriz como {1,2,28,19,11}. Ahora buscaremos el siguiente elemento más pequeño y lo reemplazaremos con 28.

12281911

Tabla-4

Después de este intercambio, tenemos nuestra matriz de salida como:

12111928

Tabla-5

Todos los elementos están ordenados, por lo que no se necesita más intercambio, por lo que esta es nuestra matriz recién ordenada.

Descripción general: Clasificación de selección

Recuerde, los humanos podemos mirar una matriz y saber fácilmente que 1 es el número más pequeño, pero las computadoras no pueden. Deben iterar a través de todo el conjunto de datos para encontrar qué número es el más pequeño o el más grande.

Fuente de la imagen: código calabaza

Para ver cómo las computadoras hacen el número más pequeño y el número más significativo, veamos el pseudocódigo.

function selectionSort(array, size)

    // Iterating over the entire array from 0 to size - 2(0 - 
Based Indexing) 
    for i = 0 to size - 2
        smallest = array[i]
        for j = i+1 to size - 1
            if array[j] < smallest
                smallest = array[j]
                smallest_index = j

        swap(array[i],array[smallest_index])

    return array

El pseudocódigo anterior muestra cómo funcionará el código en la ordenación por selección:

  • Establece el número más pequeño para que sea el primer elemento en la parte no ordenada de la matriz. Inicialmente, toda la matriz no está ordenada, es decir, el primer elemento de la matriz.
  • Mira a través de toda la parte no ordenada de la matriz y luego encuentra el número más pequeño.
  • Intercambiará el valor con el artículo en el índice inicial, es decir. el primer elemento de la sección sin clasificar, que aumenta el tamaño de la sección ordenada en 1 y al mismo tiempo disminuye el tamaño de la sección sin clasificar en 1.

Ahora, para comprender mejor el algoritmo, pasemos a otro ejemplo para obtener una comprensión clara del código.

Fuente de la imagen: HackerEarth

El código: clasificación de selección

Los algoritmos de clasificación toman elementos de matriz como datos de entrada, realizan operaciones específicas en esas matrices y entregan matrices ordenadas como salida. Entonces, veamos cómo se vería el algoritmo de clasificación por selección en diferentes lenguajes de programación.

Ordenar por selección en Java

public class selectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            int smallNumber = arr[index];
            arr[index] = arr[i];
            arr[i] = smallNumber;
        }
    }

    public static void main(String a[]) {
        int[] arr = {11,2,1,3,4,19,28};
           
        selectionSort(arr);
        for (int i: arr) {
            System.out.print(i + " ");
        }
    }
}

Resultado:

[1,2,3,4,11,19,28]
  • Usaremos dos bucles anidados en esta función, que siguen iterando toda la matriz hasta que se encuentra el valor más pequeño.
  • En el primer ciclo que representa la parte ordenada de la matriz, hemos inicializado una variable i = 0, que sigue incrementando su valor hasta la última iteración.
  • Luego, se define un bucle anidado con otra variable j, que es igual a i+1, de modo que el valor junto al valor más pequeño está allí y obtiene el valor más pequeño de la parte no ordenada de la matriz hasta que se coloca en la parte ordenada. . Ambos bucles continuarán iterando hasta que se encuentre la última matriz ordenada.

Ordenar por selección en Python

def selectionSort(array, size):
    for step in range(size):
        minimum_idx = step

        for i in range(step + 1, size):

        if array[i] < array[minimum_idx]:
            minimum_idx = i

     
    (array[step], array[minimum_idx]) = (array[minimum_idx], 
array[step])


list = [11,2,28,19,7,65]
size = len(list)
selectionSort(list, size)
print(list)

Resultado:

[2, 7, 11, 19, 28, 65]

Ordenar por selección en C++

#include <iostream>
using namespace std;

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int array[], int size){
    for (int step = 0; step < size - 1; step++){
        int minimum_idx = step;
        for (int i = step + 1; i < size; i++){
            if (array[i] < array[minimum_idx])
                minimum_idx = i;
        }
        swap(&array[minimum_idx], &array[step]);
    }
}

// driver code
int main(){
    int data[] = {11, 1, 21, 28, 19, 6, 7};
    int size = sizeof(data) / sizeof(data[0]);
    selectionSort(data, size);
    for (int i = 0; i < size; i++){
        cout << data[i] << " ";
    }
}

Resultado:

[1,6,7,11,19,21,28]

Este método de clasificación tiene la desventaja de que, incluso si tenemos una matriz ordenada o casi ordenada, seguirá comprobando todos los elementos de la matriz.

Por eso la complejidad del tiempo tipo de selección en el peor, en el mejor, y el promedio es el mismo – O(n²). Esto significa que a medida que aumenta el número de elementos, el tiempo de ejecución aumenta a un ritmo cuadrático. Incluso si hemos editado la matriz en el mejor de los casos, tendremos que revisar toda la matriz para estar seguros. Por lo tanto, la complejidad temporal en todos los casos es la misma.

Clasificación de selección acumulada

Complejidad del tiempoO(n²) en todos los casos.
Complejidad espacialO(1) ya que usamos espacio adicional continuo.
Estable/inestableInestableporque encuentra el elemento mínimo y luego lo reemplaza en su lugar adecuado intercambiando con el elemento presente en el primer índice.
Interno externoInterno porque los datos de entrada se pueden ajustar en la memoria principal al mismo tiempo.
Comparables/Incomparablessí, es un algoritmo de comparabilidad que compara los elementos antes de ordenarlos.
Recursivo/No Recursivorecursivo porque ordena gradualmente las partes una por una y todavía afirma que hay sobras.

Preguntas frecuentes

¿Por qué se utiliza el ordenamiento por selección?

La ordenación por selección usa muy poco almacenamiento de memoria porque no requiere ningún almacenamiento adicional fuera de la matriz original para almacenar la matriz ordenada. Además, funciona de manera eficiente cuando se consideran arreglos o conjuntos de datos más pequeños.

¿Qué es mejor: la selección o la clasificación?

Es preferible ordenar la entrada porque se ejecuta de manera mucho más eficiente debido a su complejidad de tiempo cuando la matriz está ordenada o casi ordenada. Sin embargo, la ordenación por inserción siempre realiza intercambios O(n^2) en promedio y en el peor de los casos, mientras que la ordenación por selección siempre dará intercambios O(n), esto es útil cuando escribir en la memoria es una operación costosa.

¿La ordenación por burbuja es más rápida que la ordenación por selección?

La ordenación por selección es más rápida que la ordenación por burbuja porque la ordenación por selección usa el peor de los casos n swaps para intercambiar los elementos, mientras que la ordenación por burbuja usa el peor de los casos n(n-1)/2 swaps para ordenar los elementos con el mismo número de comparaciones para ambos algoritmos en el peor de los casos, es decir. n(n-1)/2

¿Qué técnica de clasificación es mejor?

Quicksort es uno de los algoritmos de clasificación más eficientes, con complejidades promedio y en el peor de los casos de O(N log N) y O(n*2).

Aprende más de programación:

6 comentarios en «¿Qué es la ordenación por selección en python?»

  1. ¡La ordenación por selección en Python es como hacer fila en el supermercado! 🛒🐍

    • ¡Qué comparación tan acertada! La ordenación por selección en Python puede ser eficaz para tareas simples, pero ¿no crees que hay métodos más eficientes y rápidos disponibles? Quizás sea hora de explorar otras opciones para optimizar tu código. ¡Anímate a probar nuevas técnicas! 🚀👩‍💻

  2. ¡La ordenación por selección en Python es genial para ordenar listas de forma eficiente! 🐍👌

  3. ¡La ordenación por selección en Python es genial! ¿Pero es realmente la mejor opción?

  4. Creo que la ordenación por selección en Python es útil, ¿no crees? 🤔

    • No estoy de acuerdo. Creo que la ordenación por selección en Python puede ser ineficiente en comparación con otros algoritmos de ordenamiento más eficaces. ¿Has considerado utilizar otras opciones como la ordenación rápida o la ordenación de mezcla? Son más rápidas y eficientes en la mayoría de los casos. 🤔

Los comentarios están cerrados.