Ordenamiento por Inserción Directa y Ordenamiento por Selección

Unidad de Apoyo para el Aprendizaje

Iniciar

Introducción


Imagina 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

Analogía de ordenamiento por selección



El estudio de este tema te permitirá:

Generar códigos de programación, a partir del reconocimiento de las características del método de ordenación por inserción directa y ordenamiento por selección, para manipular datos y solucionar diferentes tipos de problemas.

Ordenamiento por inserción directa


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.

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.

Ordenamiento por selección

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

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.

Fuentes de información

Básicas

Bibliografía

Domínguez, E. (2014). Programación estructurada: raptor y lenguaje C. México: Alfaomega.

Guardati, S. (2015). Estructuras de datos básicas: programación orientada a objetos con java. México: Alfaomega.

Joyanes, L. (1998). Fundamentos de Programación: Algoritmos y estructuras de datos. Madrid: McGraw-Hill.

Kalicharan, N. (2013). Advanced topics in C: core concepts in data structures. California: Apress.

López, B. (2012). Estructuras de datos orientadas a objetivos: pseudocódigo y aplicaciones en C#.NET. México: Alfaomega.

López, B. (2015). Estructuras de datos orientadas a objetos. México: Alfaomega.

Maes, R. (2013). Physically unclonable functions: constructions, properties and applications. Berlín: Springer.

Malik, D. (2013). Estructura de datos con C++. México: Cengage Learning.

Weiss, M. (2012). Data Structures and Algorithm Analysis in Java. New Jersey: Addison-Wesley.

Documentos electrónicos

Martínez, J. M. y Castro, R. (2012). Programación (Estructura de Datos) [Versión electrónica]. México: SUAYED-FCA-UNAM. Consultado el 23 de abril de 2018 de http://fcasua.contad.unam.mx/apuntes/interiores/docs/20172/informatica/3/apunte/LI_1361_30096_A_Prog_estruc_datos_V1.pdf

Complementarias

Bibliografía

López, A. (2011). Estructura de datos con JAVA: un enfoque práctico. México: UNAM-Facultad de Ciencias.

Luján, S., Ferrández, A., Peral, J. y Requena, A. (2014). Ejercicios resueltos sobre programación y estructuras de datos. Alicante: Publicaciones de la Universidad de Alicante.

Mora, A. (2014). Bases de datos: diseño y gestión. Madrid: Editorial Síntesis.

Weiss, M. A. (2013). Estructuras de datos en Java. Madrid: Pearson Educación.

.

Cómo citar

Texto correspondiente a esta sección.