Bienvenidos a este nuevo capítulo de este Curso Gratis de Programación #17 Ordenamiento
¿Te gustaría enterarte de cuando lanzamos descuentos y nuevos cursos?
Ordenamiento
El ordenamiento es una labor común que realizamos continuamente. ¿Pero, qué es ordenar? El ordenamiento es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento. La finalidad de un ordenamiento es el de facilitar el acceso a la información.
En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. En esta unidad vamos a mostrar algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.
Ordenamiento por algoritmo de burbuja
Tiene su base en la comparación de pares de elementos adyacentes e intercambiarlos entre sí. Se deben recorrer sus elementos, se comparan de forma adyacente y se intercambian hasta llegar al final del arreglo.
burbuja mejorada: Si se ordena crecientemente un arreglo unidimensional una vez finalizado el primer recorrido, el mayor elemento se encuentra en la última posición y no es necesario comparar el último par de elementos en el siguiente recorrido.
Esta lógica de evitar comparaciones innecesarias se puede repetir a medida que se ordenan los mayores elementos en las últimas posiciones.
para i <- 1 hasta N-1 hacer
para j <- 1 hasta N-i hacer
si X[j] > X[j+1] entonces
// intercambiar
AIJX <-X[j]
X[j] <-X[j+1]
X[j+1] <- AUX
fin-si
fin-para
fin-para 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 Burbuja
Otro de los métodos de ordenamiento se basa en recorrer todo el vector hasta el anteúltimo elemento y comparar dos elementos adyacentes, si esos se encuentran desordenados entonces se los ordena. En un primer paso podemos observar que al avanzar en las comparaciones siempre el de mayor valor se posiciona inmediatamente al fondo en el primer ciclo, pero los valores menores avanzan una posición por cada ciclo. Por ejemplo para un vector de tamaño N, un ciclo de ordenamiento sería:
Si no tomamos ninguna consideración para mejorarlo, deberíamos repetir este ciclo tantas veces como elementos tenga el vector menos uno, esto es por que si tenemos la mala suerte de que el menor elemento estuviera al fnal del vector avanzaría hasta la primera posición de a una posición por ciclo. Entonces el diagrama quedaría así:
La verdad que visto así no presenta ninguna mejora con respecto al método de comparaciones, pero se pueden pensar unas cuantas modifcaciones como para que el algoritmo se pueda optimizar.
Primera optimización, acortamiento del ciclo de burbujeo
La primera consideración que podemos hacer es precisamente que al efecto de que en cada ciclo se envía el mayor al fnal, el siguiente ciclo no necesita llegar hasta la última posición. Por lo tanto podemos hacer que el ciclo de comparaciones elimine una comparación por ciclo en forma acumulativa. El diagrama quedaría de la siguiente forma:
Segunda optimización, detectar vector ordenado
La segunda consideración que podemos hacer es pensar que el algoritmo se plantea como un proceso de fuerza bruta, de forma tal que si el vector se ordenó en un ciclo anterior al fnal igualmente el proceso se seguirá realizando sin ordenar nada. Para esto podemos encender un flag que indique si hubo un ordenamiento, lo que nos dará una pista de que el vector sigue desordenado. Si el flag está apagado entonces no hace falta seguir ordenando. Entonces el algoritmo se plantearía de la siguiente forma:
Tercera optimización, ciclos alternados.
Otra optimización que puede hacerse es aprovechar que en un ciclo uno de los extremos se mueve directamente al fnal y realizar la misma tarea pero en sentido inverso así en el siguiente ciclo tenemos el primer elemento ordenado, esto viene muy bien en el caso de que sean vectores parcialmente ordenados al que se agrega un único elemento desordenado al fnal. Tal cual como lo hacíamos con el último elemento, debemos ajustar también el extremo inferior en cada ciclo para hacer comparaciones redundantes. Y también contemplaremos el flag en el nuevo ciclo invertido. Ahora el diagrama será un poquito más complejo, pero no tanto.
Parece complejo, pero veamos un ejemplo completo hecho en pseudocódigo:
Comparación de métodos
Método de burbuja
(Intercambiar cada pareja consecutiva que no esté ordenada)
(Nota: algunos autores hacen el bucle exterior creciente y otros decreciente, así:)
Selección directa
(En cada pasada busca el menor, y lo intercambia al final de la pasada)
Inserción directa
AC menor] )
(Comparar cada elemento con los anteriores -que ya están ordenados- y desplazarlo hasta su composición correcta.)
Algoritmo Burbuja pros y contras
BubbleSort recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en las últimas posiciones o tomar el menor y colocarlo en las primeras posiciones.
Tiempo de ejecución: El ciclo interno se ejecuta n veces. El ciclo externo también se ejecuta n veces, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).
Estabilidad: No intercambia registros con claves iguales.
Ventajas:
- Fácil implementación.
- No requiere memoria adicional.
Desventajas:
- Muy lento.
- Muchas comparaciones. Muchos intercambios.
En pseudocódigo el algoritmo es:
algoritmo Método_Burbuja
//declaraciones inicio
// lectura del vector
desde i ⭠ 1 hasta N hacer
leer ( vec[ i ] )
fin-desde
//ordenamiento del vector
desde i ⭠ 1 hasta n-1 hacer
desde j ⭠ 1 hasta n-1 hacer
si vec [ j ] > vec [ j +1 ] entonces
//intercambiar aux ⭠ vec [ j ]
vec [ j ] ⭠ vec [ j +1 ] vec [ j+1 ] ⭠ aux
fin-si
fin-desde
fin-desde
// mostrar por pantalla el arreglo ordenado
desde i ⭠ 1 hasta N hacer
mostrar ( vec[ i ] )
fin-desde
finOrdenación por burbuja mejorada.
Después de cada pasada (el bucle desde más externo), el elemento de más valor se ubica en el extremo del arreglo. Lo que significa que toma su posición correcta, por este motivo sería conveniente que, en vez de realizar todas las comparaciones en la segunda pasada, se haga una comparación menos.
algoritmo Método_Burbuja_mejorada
//declaraciones inicio
// lectura del vector
desde i ⭠ 1 hasta N hacer
leer ( vec[ i ] )
fin-desde
//ordenamiento del vector
desde i ⭠ 1 hasta n-1 hacer
desde j ß 1 hasta n- i hacer
si vec [ j ] > vec [ j +1 ] entonces
//intercambiar
aux ⭠ vec [ j ]
vec [ j] ⭠ vec [ j +1 ] vec [ i+1 ] ⭠ aux
fin-si
fin-desde
fin-desde
// mostrar por pantalla el arreglo ordenado
desde i ⭠ 1 hasta N hacer
mostrar ( vec[ i ] )
fin-desde
finEjercicios de aplicación.
Ejemplo 1) Generar un arreglo de 10 elementos enteros ordenados de menor mayor.
tipo
array [1..10] de entero : vector
var
vector: vec entero: i, j, aux
inicio
escribir („ ingresar los valores‟)
desde i ⭠ 1 hasta 10 hacer
leer (vec [i ] )
fin-desde
escribir („Comienza el ordenamiento‟)
desde i ⭠ 1 hasta 9 hacer
desde j ⭠ i+1 hasta 10 hacer
si vec [i ] > vec [ j ] entonces
aux ⭠ vec [ i ] vec [i ] ⭠ vec [ j ] vec [j ] ⭠ aux
fin-si
fin-desde
fin-desde
escribir („el vector ordenado es:‟ )
desde i ⭠ 1 hasta 10 hacer
mostrar ( vec [ i ])
fin-desde
finEjemplo 2)
Generar un arreglo de 10 elementos enteros ordenados de mayor a menor.
Algoritmo ordenación_selección
Algoritmo ordenación_selección
tipo
array [1..10] de entero : vector
var
vector: vec entero: i, j, aux
inicio
escribir („ ingresar los valores ‟)
desde i ⭠ 1 hasta 10 hacer
leer (vec [i ] )
fin-desde
escribir („Comienza el ordenamiento‟)
desde i ⭠ 1 hasta 9 hacer
desde j ⭠ i+1 hasta 10 hacer
si vec [i ] < vec [ j ] entonces
aux ⭠ vec [ i ]
vec [i ] ⭠ vec [ j ] vec [j ] ⭠ aux
fin-si
fin-desde
fin-desde
escribir („el vector ordenado es:‟ ) desde i ⭠ 1 hasta 10 hacer
mostrar ( vec [ i ])
fin-desde
finBúsqueda secuencial
La búsqueda secuencial es utilizado cuando los elementos del conjunto no se encuentran ordenados. Este algoritmo consiste en recorrer secuencialmente la estructura de datos para comparar cada uno de los elementos con el valor que se desea buscar. Expondremos una de las variantes de este algoritmo. Suponiendo un arreglo unidimensional A de N elementos, si se desea buscar el valor K, el pseudocódigo de búsqueda secuencial es el siguiente:
leer(K)
para i <- 1 hasta N hacer
si A[i] ==K entonces
Escribir("Elemento encontrado en la posición ", i)
fin -si
fin -para Para cada ocurrencia en la que se encuentre el valor Ken el arreglo A, se mostrará un mensaje informando la posición en la que se ha encontrado el valor. El recorrido del arreglo se puede realizar con cualquiera de las estructuras repetitivas. Si el valor a buscar se encuentra una sola vez en el arreglo, entonces el peor escenario es que dicho valor se encuentre en la última posición o no se encuentre. En este caso se deben realizar N comparaciones. En el mejor de los escenarios, si el valor se encuentra en la primera posición, entonces se realiza una sola comparación. Esto indica que la cantidad promedio de comparaciones que realiza este método de búsqueda es (N+ 1)/2.2.
Este tipo de algoritmo, como su nombre indica, busca desde el primer dato hasta el último, uno a uno comparando sucesivamente todos los datos en memoria hasta localizar el dato que queramos localizar. Este algoritmo puede usarse en cualquier situación, pero se recomienda usarlo solo en listas que no estén ordenadas, ya que para las que lo estén podremos usar el siguiente algoritmo, que es mucho más eficiente.
Problema de la Búsqueda: Dada una lista xn y un valor x devolver el índice de x en xn si x está en xn, y −1 si x no está en xn.
Diseñamos una solución: Podemos comparar uno a uno los elementos de la lista con el valor de x, y retornar el valor de la posición donde lo encontramos en caso de encontrarlo. Si llegamos al final de la lista sin haber salido antes de la función es porque el valor de x no está en la lista, y en ese caso retornamos −1. En esta solución necesitamos una variable i que cuente en cada momento en qué posición de la lista estamos parados. Esta variable se inicializa en 0 antes de entrar en el ciclo y se incrementa en 1 en cada paso.
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.