Ordenamiento por Inserción Directa y Ordenamiento por Selección
Unidad de Apoyo para el Aprendizaje
IniciarImagina que tienes una baraja dividida en dos partes; una mitad está ordenada y la otra está desordena, después, tomas las cartas de la mitad desordenada y las insertas una por una, de manera ordenada, en la otra mitad de manera que dicha mitad no pierda la característica de ser la ordenada. Ésta es la forma, a grandes rasgos de cómo funciona el método de ordenamiento por inserción directa.
Ahora imagina que tenemos una baraja, vamos a utilizar otra estrategia para lograr nuestro objetivo de ordenarla. Lo que hacemos es dividir el juego en dos partes, la parte ordenada quedará del lado izquierdo y la parte sin ordenar quedará del lado derecho; en un inicio, del lado izquierdo no hay nada, porque la parte ordenada está vacía. Luego nos vamos al juego de cartas y seleccionamos el elemento de menor valor de una sola figura, es decir; el dos (recuerda que en una baraja no hay uno ni cero), ese elemento se pone del lado izquierdo en la parte ordenada y así sucesivamente hasta que tengas toda la baraja ordenada del lado izquierdo. Ésta es la forma, a grandes rasgos, en que funciona el ordenamiento por selección.
Analogía de ordenamiento por selección
En un arreglo es importante tomar en cuenta que, al inicio del ordenamiento, la parte izquierda ordenada no tenga ningún elemento, así que lo que se hace es ir formando la parte ordenada con los primeros elementos del arreglo. Observa los pasos que se realizan en el siguiente arreglo desordenado de elementos:
Haz clic en cada número o en las flechas para desplegar el contenido.
El procedimiento se repite hasta que toda la lista esté ordenada.
En la siguiente imagen, vemos la implementación de este método de ordenamiento en Lenguaje C.
Declaración en Lenguaje C de la función de ordenamiento por inserción directa
La complejidad de este algoritmo es de O(n2), donde n es el número de elementos del arreglo o lista.
En el contexto de un arreglo, el proceso de este algoritmo consiste en buscar el menor elemento e intercambiarlo por el elemento en la primera posición. Luego se busca el segundo elemento más pequeño del arreglo y se intercambia con el elemento de la segunda posición. El proceso continúa hasta que todos los elementos del arreglo hayan sido ordenados.
El método se basa en los siguientes principios:
En el siguiente ejemplo podrás identificar de manera detallada los pasos que se deben seguir para utilizar este método de ordenamiento. Tenemos los siguientes elementos desordenados:
Haz clic en cada número o en las flechas para desplegar el contenido.
El procedimiento se repite hasta que toda la lista esté ordenada. En la siguiente imagen vemos la implementación de este método de ordenamiento en Lenguaje C.
Declaración en Lenguaje C de la función para realizar el ordenamiento por selección
Este algoritmo no es recomendable para grandes conjuntos de datos, ya que en promedio y en el peor de los casos la complejidad es de O(n2), donde n es el número de elementos.
Actividad. Características del método de ordenamiento por inserción directa y por selección
Con el método de inserción directa se pretende comparar los elementos desordenados con los ordenados; mientras que con el de selección simplemente se busca el elemento menor y se lleva al inicio.
Autoevaluación. Programación del método de ordenamiento por inserción directa y por selección
Las características de programación del método de ordenamiento por inserción directa y por selección son completamente diferentes; en el método por inserción directa se van tomando los elementos de la lista y se van comparando con la lista ordenada; en cambio, en el método por selección primero se busca en toda la lista desordenada el elemento menor y se va llevando a la lista ordenada uno después de otro.