Bienvenidos a este nuevo capítulo de este Curso Gratis de Programación #18 Ordenamiento II
¿Te gustaría enterarte de cuando lanzamos descuentos y nuevos cursos?
Ordenamiento por algoritmo de inserción
Supóngase que se desea ordenar los siguientes claves del arreglo (A) utilizando el método de inserción directa el cual consiste en insertar un elemento del arreglo en la parte izquierda del mismo que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.
Ejemplo
tomar un elemento del conjunto e insertarlo en una parte ya ordenada. Se debe repetir este procedimiento para el resto de los elementos que restan por ordenar.
para i <- 2 hasta N hacer
AUX <-X[i]
K <-i-1
sw <- falso
mientras NO(sw) y (K>= 1) hacer
si AUX < X[k] entonces
X[k+1] <-X[k]
K <-k-1
Si-no
sw <- verdadero
fin-si
fin -mientras
X[k+1] <- AUX
fin-para ordenamiento creciente de un arreglo unidimensional con método de inserción Arreglo inicial:
Iteración externa número 1 (i=2)
Iteración externa número 2 (i=3)
Iteración externa número 3 (i=4)
Iteración externa número 4 (i=5)
La aplicación de este método asegura la siguiente cantidad de comparaciones:
Ordenamiento por algoritmo de selección
Si se desea ordenar un arreglo unidimensional en forma creciente, el método de ordenamiento por selección consiste en recorrer el arreglo para buscar el menor elemento e intercambiarlo con el elemento de la primera posición. Luego se debe recorrer nuevamente el arreglo para buscar el segundo menor elemento e intercambiarlo con el elemento de la segunda posición. Este procedimiento se debe aplicar para el resto de los elementos hasta que el arreglo se encuentre ordenado. Suponiendo un arreglo unidimensional X de N elementos, el pseudocódigo del algoritmo de ordenamiento por selección en orden creciente es el siguiente:
para i <- 1 hasta N-1 hacer
AUX <-X[i]
k<-i
para j <- i+1 hasta N hacer
si X[j] < AUX entonces
AUX<-X[j]
k<-j
fin-si
fin-para
X[k]<- X[i]
X[i] <- AUX
fin-para
ordenamiento creciente de un arreglo unidimensional con método de selección
Arreglo inicial:
Iteración externa número 1 (i=1)
Iteración externa número 2 (i=2)
Iteración externa número 3 (i=3)
Iteración externa número 4 (i=4)
Cantidad de comparaciones = (N^2 – N) / 2
= (N^5 – 5) / 2
= (25 – 5) / 2
= 20 / 2
= 10
Ordenamiento por selección (Grafico)
Inserción
Inserción (A,N), Algoritmo, Inserción(A,N) El algoritmo ordena los elementos del arreglo utlizando el método de inserción directa A es un arreglo de N elementos donde I, aux y k son variables de tipo entero
- Repetir con I desde 2 hasta N Hacer aux<- A[I] y k<- I-1
- a. Repetir mientras(aux < [k]) y (k > 1) , Hacer A[k+1]<- A[k] y k<– k-1
- b. {fin del ciclo del paso 1.1}
- c. Si a[k]<=aux Entonces: Hacer A[k+1]<-aux Si no Hacer A[k+1]<- A[k], A[k]<-A[k]
- d. { fin del condicional del paso 1.3}
- {fin del condicional del paso1}
Implementación
A continuación se muestra el ordenamiento por inserción en distintos lenguajes de programación:
Prueba de escritorio
Si A= 15, 67, 08, 16, 44, 27, 12, 35
1ª pasada 08, 67, 15, 16, 44, 27, 12, 35
2ª pasada 08, 15, 67, 16, 44, 27, 12, 35
3ª pasada 08, 15, 16, 67, 44, 27, 12, 35
4ª pasada 08, 15, 16, 44, 67, 27, 12, 35
5ª pasada 08, 15, 16, 44, 27, 67, 12, 35
6ª pasada 08, 15, 16, 44, 27, 12, 67, 35
7ª pasada 08, 15, 16, 44, 27, 12, 35, 67
Análisis de la eficiencia
En general afirmar que si el arreglo se encuentra ordenado se efectúan como máximo n-1 comparaciones y o movimientos entre elementos Cmin = n-1. El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden inverso
- Cmax = 1+2+3+…………+(n-1) = n*(n-1)/2
- Cmax= (n2-n)/2
El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
- Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
- Cmed = (n2+n-2)/4
Respecto al número de movimientos Knuth obtiene los siguiente:
- Mmin = 0
- Mmed = (n2-n)/4
- Mmax = (n2-n)/2
Tiempo de ejecución
- El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2).
- A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo.
Tiempo de ejecución:
El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2). A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo.
CONCEPTOS PRELIMINARES
Antes de comenzar a ver cada algoritmo vamos a ponernos de acuerdo en algunos conceptos, para que no haya confusiones:
Clave: La parte de un conjunto de datos (registro), por la cual se ordena la lista. Por ejemplo, una lista de registros, en la que cada registro de esa lista tiene tres campos diferentes: nombre, dirección y teléfono se puede ordenar alfabéticamente de acuerdo a la clave nombre. En este caso los campos dirección y teléfono no se toman en cuenta en el ordenamiento.
Criterio de ordenamiento (o de comparación): EL criterio que utilizamos para asignar valores a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro.
Registro: Un grupo de datos que forman la lista. Pueden ser datos atómicos (enteros, caracteres, reales, etc.) o grupos de ellos.
Cuando se estudian algoritmos de todo tipo, no sólo de ordenamiento, es bueno tener una forma de evaluarlos antes de pasarlos a código, que se base en aspectos independientes de la plataforma o el lenguaje. De esta manera podremos decidir cuál se adapta mejor a los requerimientos de nuestro programa. Algunos de estos aspectos son:
Estabilidad:
Este parámetro establece o mide cómo se comporta, el algoritmo con registros que tienen claves iguales. Algunos algoritmos mantienen el orden relativo entre
éstos y otros no. Veamos un ejemplo. Si tenemos la siguiente lista de datos (nombre, edad): “Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18, Marcela 17”, y la ordenamos alfabéticamente por el nombre con un algoritmo estable quedaría así: “Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan 18, Pedro 19”. Un algoritmo no estable podría dejar a Juan 18 antes de Juan 23, o a Marcela 20 después de Marcela 17.
Tiempo de ejecución: Este parámetro mide la complejidad del algoritmo, que no tiene que ver con dificultad, sino con rendimiento. Es una función independiente de la implementación.
Una medida de eficiencia es:
- Contar el número de comparaciones
- Contar el número de movimientos de ítems
Estos están en función del número de elementos a ser ordenados.
En el ordenamiento una operación fundamental es la de comparar. Ahora contamos cuántas veces el algoritmo necesita comparar. Si en una lista de n términos realiza n comparaciones la complejidad es O(n). (En realidad es un poco más complicado que eso). Algunos ejemplos de complejidades comunes son:
O(1): Complejidad constante.
O(n2): Complejidad cuadrática.
O(n log(n)): Complejidad logarítmica.
Ahora podemos decir que un algoritmo de complejidad O(n) es más rápido que uno de complejidad O(n2). Otro aspecto a considerar es la diferencia entre el peor y el mejor caso. Cada algoritmo se comporta de modo diferente de acuerdo a cómo se le entregue la información; por eso es conveniente estudiar su comportamiento en casos extremos, como cuando los datos están prácticamente ordenados o muy desordenados.
Requerimientos de memoria:
El algoritmo puede necesitar memoria adicional para realizar su labor. En general es preferible que no sea así, pero es común en la programación tener que sacrificar memoria por rendimiento.
Hay más aspectos que se pueden tener en cuenta para realizar un análisis de calidad sobre un algoritmo de ordenamiento en particular, pero sólo vamos a mencionar en esta materia los hasta aquí descriptos.
Por último, estableceremos algunas convenciones sobre el pseudocódigo:
Vamos a ordenar la lista en forma ascendiente, es decir, de menor a mayor. Obviamente es esencialmente lo mismo que hacerlo en forma inversa. La forma de intercambiar los elementos depende de la estructura de datos: si es un arreglo (dinámico o estático) es necesario guardar una copia del primer elemento, asignarle el segundo al primero y el temporal al segundo. La variable temporal es necesaria, porque de lo contrario se perdería uno de los elementos. Si la estructura es una lista dinámica el procedimiento es parecido,
pero se utilizan las direcciones de los elementos. En el pseudocódigo se utilizará el primer método. La siguiente es una tabla comparativa de algunos algoritmos de ordenamiento, según los parámetros ya vistos.
| Tabla comparativa de algoritmos | |||
| Nombre | Complejidad | Estabilidad | Memoria adicional |
| Ordenamiento Burbuja | O(n2) | Estable | No |
| Ordenamiento por Selección | O(n2) | No Estable | No |
| Ordenamiento por inserción | O(n2) | Estable | No |
| Ordenamiento Rápido (Quicksort) | O(n * log2(n)) | No Estable | No |
Cada algoritmo se comporta de modo diferente de acuerdo a la cantidad y la forma en que se le presenten los datos, entre otras cosas. No existe EL algoritmo de ordenamiento. Sólo existe el mejor para cada caso particular. Se debe conocer el problema que se desea resolver, y aplicar el algoritmo más adecuado. Hay algunos interrogantes que pueden ayudar a escoger un algoritmo en especial:
¿Qué grado de orden tendrá la información que vas a manejar?
Si la información va a estar casi ordenada y no quieres complicarte, un algoritmo sencillo como el ordenamiento burbuja será suficiente. Si por el contrario los datos van a estar muy desordenados, un algoritmo poderoso como Quicksort puede ser el más indicado. Si por forma en que se presenta la información no es posible hacer una presunción sobre el grado de orden de la información, lo mejor será elegir un algoritmo que se comporte de manera similar en cualquiera de estos dos casos extremos.
¿Qué cantidad de datos vas a manipular? Si la cantidad es pequeña, no es necesario utilizar un algoritmo complejo, y es preferible uno de fácil implementación. Una cantidad muy grande puede hacer prohibitivo utilizar un algoritmo que requiera de mucha memoria adicional.
¿Qué tipo de datos quieres ordenar? Algunos algoritmos sólo funcionan con un tipo específico de datos (enteros, enteros positivos, etc.) y otros son generales, es decir, aplicables a cualquier tipo de dato.
¿Qué tamaño tienen los registros de tu lista? Algunos algoritmos realizan múltiples intercambios (burbuja, inserción). Si los registros son de gran tamaño estos intercambios son más lentos.
El ordenamiento es una labor común que realizamos cotidianamente, es un proceso tan común en nuestras vidas que no nos detenemos a meditar mucho en ello. Ordenar es meramente colocar información de una manera especial basándonos en un criterio de ordenamiento.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
Ordenamiento de un vector
Se requiere un algoritmo que nos muestre de todas las ventas mensuales de un determinado año, cuales meses estuvieron por debajo del promedio de venta mensual ordenados primero el de menor venta luego el que le sigue y así sucesivamente. En otras palabras, queremos saber los que están por debajo del promedio, pero queremos verlos ordenados desde el menor al mayor. Volvamos a plantear el método top-down:
1. Carga de los 12 totales de ventas y Cálculo del promedio.
2. Ordenamiento del vector.
3. Muestra de las ventas de menor a mayor hasta que encontremos una que supere el promedio.
Vemos que el primer punto se mantiene tal cual, así que tenemos una gran parte hecha, concentrémonos ahora en el ordenamiento… cómo se ordena un vector? Existen varios algoritmos diseñados para ordenamiento de vectores, cada uno con sus ventajas y desventajas. La idea es poder entenderlos y aplicarlos al algoritmo actual. Vamos a elegir uno simple de entender: el método de ordenamiento de comparaciones sucesivas. Veamos el diagrama de flujo de este método de ordenamiento:
Diagrama de flujo
En este método se utiliza el mecanismo de buscar el menor y ponerlo al principio. Para hacer esto se toma el primer elemento del vector (v[pri]) y se lo va comparando con todos los restantes (v[sig]), cada vez que encontremos uno que sea menor lo intercambiaremos con la primera posición. Al finalizar de comparar el primer elemento con todos los siguientes estaremos seguros de que el menor quedó en la primera posición.
Lo siguiente será repetir la misma búsqueda del menor ahora a partir de la segunda posición y los restantes, luego con la tercera y así hasta la anteúltima, por descarte en la última posición quedará el mayor.
Este método es bastante simple de entender, pero lamentablemente es de muy baja performance ya que requiere que se comparen los elementos del vector todos con todos por lo tanto al crecer en una unidad el vector se suma un ciclo entero de comparaciones
Lo invito a prestar atención a esta progresión pues más adelante buscaremos un método para calcularla. Apliquemos entonces este método de ordenamiento al algoritmo. Pues bien, nos encontramos con un problema, he aquí que el mes de las ventas está asociado al índice así que tendremos que guardar el mes en un vector auxiliar e intercambiarlo a medida que cambiamos las ventas así no perdemos la relación. Vamos a tener que rehacer todo el Algoritmo:
Algoritmo
y el diagrama de flujo
Analicemos el diagrama, primero tenemos la declaración de las variables y la defnición del vector con los nombres de los meses. A continuación tenemos 3 ciclos importantes, veamos uno por uno:
El ciclo 1 corresponde a la carga del vector de ventas y al cálculo del promedio, tal cual como lo hemos visto anteriormente, el único cambio es en el mensaje: en lugar de mostrar el numero de cada mes, aprovechamos y mostramos su nombre.
El ciclo 2 corresponde al ordenamiento tanto del vector de ventas de mayor a menor como también del vector de nombres (nombreMes) que debe mantener la asociación con el mes de la venta.
El ciclo 3 ahora es una estructura repetitiva condicional, en lugar de una iteración aprovechamos que el vector está ordenado y mientras las ventas sean menores al promedio se mostrarán los datos del vector, apenas superemos el promedio ya no se deberá mostrar nada más.
Si usted quiere como tarea adicional podría agregar a continuación otro ciclo para que muestre las ventas ordenadas que superan al promedio, no olvide poner el título “Meses por arriba del promedio” para evitar confusiones en los datos. Pero, ¿Hay algún método de ordenamiento mejor y que sea facil de entender?
No te detengas, sigue avanzando
Aquí tienes un propósito para este 2024 que debes considerar seriamente: si has querido mejorar tus habilidades en hacking, Ciberseguridad y programación ahora es definitivamente el momento de dar el siguiente paso. ¡Desarrolla tus habilidades aprovechando nuestros cursos a un precio increíble y avanza en tu carrera!
Python Practicando. Desde 0 hasta Desarrollador en Python
Aprende Python, donde iniciamos desde 0, sin conocimientos previos hasta desarrollar aplicaciones con mucha practica!
Calificación: 4,6 de 5 (20.833 calificaciones) 249.493 estudiantes Creado por Alvaro Chirou • 1.800.000+ Enrollments Worldwide, Walter Coto || +450,000 Estudiantes Español.
Lo que aprenderás
- Ejercitar la lógica de programación
- Comprender cómo la vida cotidiana puede ser fácilitada o simulada con código
- Aprender programación desde cero
- Usar Visual Studio Code como Editor de Código
- Conocer y aprender el lenguaje de programación Python
- Ser un programador desde cero, sin conocimiento en otro lenguaje o con algo previo
- Mejorar las habilidades de programación, mejorar procesos y fácilitar la comprensión de código
- Preparar un entorno dónde programar en Python
- Operaciones aritméticas y jerarquía de Python
- Manejo de cadenas en Python
- Digitar datos por teclado con Python
- Mostrar Datos por Pantalla al usuario en Python
- Operadores Relacionales de Python
- Operadores Lógicos de Python
- Condicionales en Python
- Estructuras de Datos: Listas, Tuplas y Diccionarios
- Iteraciones y bucles repetitivos de Python
- Segmentar Código y hacerlo más eficaz con las Funciones en Python
- Gestionar posibles errores que puedan dar tus programas
- Programación Orientada a Objetos
- HTML y CSS
- Selenium Web Driver con Python
- Ejercitar todo lo Aprendido con Ejercicios
Este curso incluye:
- 25,5 horas de vídeo bajo demanda
- 21 artículos
- 148 recursos descargables
- Acceso en dispositivos móviles y TV
- Certificado de finalización
Python es Hoy uno de los lenguajes más utilizados por Excelencia.
Esto se debe por su simpleza al momento de Desarrollar aplicaciones.
Por su capacidad de procesamiento a altas velocidades con grandes volúmenes de información.
Es un increíble lenguaje con el cual si no sabes programar, podrás aprender.
Y si ya sabes desarrollar, te aconsejo aprenderlo ya que en el mercado cada vez se solicitan más desarrolladores en Python.
Aspirar al trabajo que desean, o mejorar sus ingresos con un aumento de salario.
Python se utiliza para muchisimas cosas como:
- Machine Learning
- Data Science
- Inteligencia Artificial.
- Y mucho más!
En este curso te acompañare en el proceso por el cual aprenderás las bases del lenguaje, para luego determinar qué camino quieres seguir.
Te invito que me acompañes a conocer este Gran Lenguaje!
Aprende con nuestros más de 100 cursos que tenemos disponibles para vos
¿Te gustaría enterarte de cuando lanzamos descuentos y nuevos cursos?
Sobre los autores
Álvaro Chirou
Yo soy Álvaro Chirou, tengo más de 20 Años de experiencia trabajando en Tecnología, eh dado disertaciones en eventos internacionales como OWASP, tengo más de 1.800.000 estudiantes en Udemy y 100 formaciones profesionales impartidas en la misma. Puedes serguirme en mis redes:
Laprovittera Carlos
Soy Laprovittera Carlos. Con más de 20 años de experiencia en IT brindo Educación y Consultoría en Seguridad de la Información para profesionales, bancos y empresas. Puedes saber más de mi y de mis servicios en mi sitio web: laprovittera.com y seguirme en mis redes:
¿Quieres iniciarte en hacking y ciberseguridad pero no sabes por dónde empezar? Inicia leyendo nuestra guia gratuita: https://achirou.com/como-iniciarse-en-ciberseguridad-y-hacking-en-2024/ que te lleva de 0 a 100. Desde los fundamentos más básicos, pasando por cursos, recursos y certificaciones hasta cómo obtener tu primer empleo.