Algoritmos de ordenación y análisis de eficiencia

golfredoe@gmail.com | Skype: golfredoe |

La importancia de los algoritmos de ordenación no se discute.

¡Tienen gran importancia dentro de la Ciencia de la Computación!, dado que una buena cantidad de los procesos realizados por medios computacionales requieren que sus datos estén ordenados.

Por lo tanto, en este post quiero compartir un material que resume diversos métodos de ordenación (estudiados ampliamente) y el análisis de su complejidad, tema clave para los programadores que aspiran transitar hacia las “grandes ligas”.

Dado un conjunto de n elementos a1, a2,..., an y una relación de orden total (≤) sobre ellos, el problema de la ordenación consiste en encontrar una permutación de esos elementos ordenada de forma creciente.

Aunque tanto el tipo y tamaño de los elementos como la “estructura” y el dispositivo en donde se encuentran almacenados puede influir en el método que utilicemos para ordenarlos, a efectos de la explicación que presenta el material compartido, simplemente, se utiliza un vector (arreglo simple, unidimensional) de números enteros. 

Const n =…; (* número máximo de elementos *)
Type a = Array [1..n] of integer;

Los métodos para los que encontrarás algoritmos y el análisis de su complejidad son los siguientes:

  • Ordenación por Inserción
  • Ordenación por Selección
  • Ordenación Burbuja
  • Ordenación por Mezcla (Mergesort)
  • Ordenación mediante Montículos (Heapsort)
  • Ordenación Rápida de Hoare (Quicksort)
  • Ordenación por Incrementos (Shellsort)
  • Otros algoritmos de ordenación:
    • Ordenación por Cubetas (Binsort)
    • Ordenación por Residuos (Radix)
El aprendizaje que se logra con el estudio y la solución a los problemas que proponen es, sencillamente, relevante. Así que no se pierdan este material: Descargar (46 páginas). 
Post relacionados: 

Con más vistas en el último mes

The Importance of Music for Children...

golfredoe@gmail.com | Skype: golfredoe |
Music is an art form that is created through the use of organized sounds in a harmonious and rhythmic manner. These sounds can be produced by musical instruments, the human voice, everyday objects, or electronics. Music is composed of elements such as melody, rhythm, harmony, and dynamics, and it can evoke a wide range of emotions and moods in the listener . In addition to being a form of artistic expression, music can also be used for therapeutic, ceremonial, religious, cultural, and entertainment purposes. In the case of children, learning music can have many positive effects for several reasons: Enhances cognitive development : Music involves mathematical and reasoning skills as children need to count rhythms, understand patterns and structures, and recognize tones and intervals. These skills strengthen children's logical and creative thinking abilities. Emotional and social development : Music is a powerful medium for expressing emotions and promoting social connection. Childre...
Leer más...

Algoritmos de búsqueda más conocidos

golfredoe@gmail.com | Skype: golfredoe |
Imagen
Los algoritmos de búsqueda son herramientas esenciales en la resolución eficiente de problemas en diversos campos, desde la informática y la ingeniería hasta la toma de decisiones y la optimización. Su importancia radica en su capacidad para encontrar información, tomar decisiones óptimas y mejorar el rendimiento en una amplia variedad de aplicaciones. 7 algoritmos comunes de búsqueda de elementos en un arreglo 1. Búsqueda lineal (Linear Search): Descripción: Este algoritmo recorre secuencialmente el arreglo, comparando cada elemento con el valor buscado hasta que se encuentre o se llegue al final del arreglo. Ventajas: Es simple y fácil de implementar. Funciona en cualquier tipo de arreglo, ya sea ordenado o desordenado. Desventajas: Tiene una complejidad de tiempo promedio y peor caso de O(n), donde "n" es el tamaño del arreglo. Es menos eficiente para arreglos grandes, ya que puede requerir comparaciones con todos los elementos. 2. Búsqueda binaria ( Binary Search ): Descr...
Leer más...

Programa para reducir una fracción dada X/Y

golfredoe@gmail.com | Skype: golfredoe |
En un libro sobre algoritmos, un problema básico es el siguiente: “escribe un programa para reducir una fracción dada x/y (con números x, y enteros) a sus términos más simples”. Piden que el programa sea hecho en Pascal y en C++. Programa en Pascal: Program ReduceFraction; Function GCD(a, b: integer): integer; begin   if b = 0 then     Result := a   else     Result := GCD(b, a mod b); end; Procedure ReduceFraction(var numerator, denominator: integer); var   gcd1: integer; begin   gcd1 := GCD(numerator, denominator);   numerator := numerator div gcd1;   denominator := denominator div gcd1; end; var   x, y: integer; Begin     writeln('Ingrese el numerador (x): ');     readln(x);     writeln('Ingrese el denominador (y): ');     readln(y);     ReduceFraction(x, y);     writeln('La fraccion reducida es: ', x, '/', y);     readln; End. Programa en C++: #include ...
Leer más...

Alan Turing, un visionario...

golfredoe@gmail.com | Skype: golfredoe |
Había una vez un visionario llamado Alan Turing, cuya mente brillante y curiosa lo llevaría a convertirse en el principal promotor de la computación tal como la conocemos hoy día. — ¿Los sabías? Nacido en 1912 en Maida Vale, Londres, desde una edad temprana demostró una inteligencia excepcional y una pasión insaciable por los rompecabezas y los desafíos intelectuales. Desde su infancia, Turing mostró un interés particular en las matemáticas y la lógica. A medida que crecía, fue desarrollando habilidades que le facilitaron el ingreso a la Universidad de Cambridge, donde pronto comenzó a destacar en sus estudios y a explorar la naturaleza fundamental de la computación.  Fue allí donde comenzó a idear conceptos que más tarde serían relevantes para la creación de las primeras computadoras. — ¡Un genio! La Segunda Guerra Mundial cambió el rumbo de la vida de Turing de una manera inesperada. Fue reclutado por el Gobierno Británico para trabajar en Bletchley Park, un centro secreto donde ...
Leer más...

Ejecución de la instrucción a := a+b en un lenguaje de bajo nivel

golfredoe@gmail.com | Skype: golfredoe |
Lenguaje de programación de bajo nivel Un lenguaje de programación de bajo nivel es un tipo de lenguaje que se encuentra más cercano a la máquina o al código de operación que entiende directamente el hardware de una computadora; en particular, el microprocesador. Se caracteriza por tener una estrecha relación con la arquitectura del procesador y las instrucciones que este puede ejecutar. Por lo tanto, estos lenguajes ofrecen un alto nivel de control sobre el hardware y permiten una programación muy eficiente en términos de rendimiento y recursos.  Características distintivas de los lenguajes de bajo nivel 1. Abstracción mínima : Los lenguajes de bajo nivel brindan una abstracción mínima sobre el hardware, lo que significa que las instrucciones y operaciones en el código se corresponden directamente con las operaciones que el procesador puede realizar. 2. Uso directo de memoria : En estos lenguajes, los programadores deben administrar la memoria manualmente, lo que implica controlar...
Leer más...