Curso Propedéutico de Programación Básica:
Ordenamiento
Dr. Gregorio Toscano Pulido
email: gtoscano@[Link]
Introducción
Objetivos 2
Presentar el concepto de ordenamiento.
Presentar diferentes métodos de ordenamiento y sus diferencias principales.
¿Qué es ordenamiento? 3
Por ordenar se entiende el proceso de reorganizar un conjunto de objetos en una
cierta secuencia de acuerdo a un criterio especificado. En general, la idea final de
dicho proceso es facilitar la posterior búsqueda de elementos en el conjunto
ordenado.
Ordenamiento 4
Los métodos de ordenamiento, pueden agruparse en dos grandes grupos:
Internos: Es cuando los datos están disponibles en un área de la memoria
principal, como cuando se leen un conjunto de datos desde el teclado.
Externos: Los datos están guardados en un medio externo, como puede ser un
archivo, una base de datos, etc. En donde los datos están alojados en el disco
duro u otro medio físico.
Intercambio directo (burbuja) 5
Es un algoritmo que se aplica para poder ordenar una cantidad de datos ya sea de
forma ascendente o descendente.
La idea básica de este algoritmo consiste en comparar pares de elementos
adyacentes e intercambiarlos entre sí hasta que todos se encuentran ordenados.
¿Cómo funciona? 6
En palabras el algoritmo funciona como sigue: Se realizan (n − 1) pasadas,
transportando en cada una de las mismas el menor o mayor elemento (según sea el
caso) a su posición ideal. Al final de las (n − 1) pasadas los elementos del arreglo
estarán ordenados.
Es el algoritmo más fácil de implementar, pero a cambio pagamos un alto precio
en procesamiento, ya que este método evalúa los datos muchas veces y en
ocasiones innecesariamente (como por ejemplo cuando son iguales).
Código en C del ordenamiento por Burbuja 7
Listing 1: Ordenamiento burbuja
1 void swap ( int *a , int *b){
2 int aux = *a;
3 * a = *b;
4 * b = aux ;
5 }
6
7 void bubble_sort ( int * arr , int len ){
8 for ( int i = 0; i < len - 1; ++ i)
9 {
10 for ( int j = 0; j < len - i -1; ++ j)
11 {
12 if ( arr [j] > arr [j +1])
13 swap ( arr +j , arr +( j +1) );
14 }
15 }
16 }
Análisis del algoritmo 8
Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por
lo tanto es estable.
Requerimientos de memoria: Este algoritmo sólo requiere de una variable
adicional para realizar los intercambios sin importar qué tan grande sea el
vector. Requerimiento constante.
Tiempo de ejecución: El ciclo interno se ejecuta (n − 1) × n/2 veces para una
lista de n elementos. El ciclo externo se ejecuta n veces. Es decir, la
complejidad es n × n O(n 2 ). 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(n 2 ).
Ordenamiento por selección 9
Se basa en buscar en cada iteracción el mínimo en el rango de i y el final del
arreglo e intercambiarlo con el de índice i.
El algoritmo total será entonces de orden O(n 2 )
Es interesante observar que en este algoritmo el contenido de los datos de entrada,
no influye en el costo del algoritmo. En efecto se puede comprobar (aplicar el
algoritmo sobre varios arreglos ejemplo), que se ejecutan de forma completa
ambos ciclos tanto para arreglo desordenado como para arreglo ordenado.
Análisis del algoritmo 10
Estabilidad: No es estable. Intercambia registros con claves iguales.
Requerimientos de memoria: Este algoritmo sólo requiere de una variable
adicional para realizar los intercambios sin importar qué tan grande sea el
vector. Requerimiento constante.
Tiempo de ejecución: El ciclo externo se ejecuta n veces para una lista de n
elementos. Cada búsqueda requiere comparar todos los elementos no
clasificados. Luego la complejidad es O(n 2 ). Este algoritmo presenta un
comportamiento constante independiente del orden de los datos. Luego la
complejidad promedio es también O(n 2 ).
Ordenamiento por Inserción 11
El algoritmo consiste en ordenar los dos primeros elementos del arreglo, luego se
inserta el tercer elemento en la posición correcta con respecto a los dos primeros, a
continuación se inserta el cuarto elemento en la posición correcta con respecto a
los tres primeros elementos ya ordenados y así sucesivamente hasta llegar al
ultimo elemento del arreglo.
Comparaciones requeridas 12
Es posible suponer que mientras en una búsqueda secuencial se necesitan k
comparaciones para insertar un elemento, en una búsqueda binaria se necesitará la
mitad de las k comparaciones.
Por lo tanto, el número de comparaciones promedio en el método de
ordenamiento por Inserción Binaria puede calcularse como :
C (1/2) + (2/2) + (3/2) + ... + ((n − 1)/2) ((n(n − 1))/4) ((n 2 ˘n)/4)
Código en C del ordenamiento por Inserción 13
Listing 2: Ordenamiento por Inserción
1 void insert_sort ( int * arr , int len ){
2 for ( int i = 1; i < len ; ++ i)
3 {
4 int aux = arr [i ];
5 int j = i -1;
6 while (j >=0 && aux < arr [j ]) {
7 // arr [j +1] = arr [j ];
8 j - -;
9 }
10 if (i - j +1 >0) {
11 memcpy ( arr +( j +2) , arr +( j +1) , sizeof ( int ) *(i -1 - j));
12 arr [j +1] = aux ;
13 }
14
15 }
16 }
Análisis del algoritmo 14
Estabilidad: Si es estable.
Requerimientos de memoria: Este algoritmo sólo requiere de una variable
adicional para realizar los intercambios sin importar qué tan grande sea el
vector. Requerimiento constante.
Tiempo de ejecución: Al analizar el método de ordenamiento por inserción se
advierte la presencia de un caso antinatural. El método efectúa el menor
número de comparaciones cuando el arreglo está totalmente desordenado y el
máximo cuando está ordenado.
Ordenamiento Shell 15
Denominado así por su desarrollador Donald Shell (1959), ordena una estructura
de una manera similar a la del Bubble Sort, sin embargo no ordena elementos
adyacentes sino que utiliza un intervalo entre los datos.
Ordenamiento Shell: Cáculo del intervalo 16
El intervalo puede ser de cualquier tamaño de acuerdo a una secuencia de valores
que empiezan con un valor grande (pero menor al tamaño total de la estructura) y
disminuye hasta llegar a 1.
Usualmente, se calcula el intervalo inicial con la formula de Knuth: h h × 3 + 1,
donde h toma el valor inicial de 1, y se búsca que este valor no exceda un tercio el
tamaño del arreglo. Posteriormente se actualiza h usando la siguiente fórmula
h (h − 1)/3. En la práctica se pueda usar la longtiud del arreglo entre dos como
intervalo inicial, y posteriormente reducir la longitud a la mitad, hasta llegar a la
unidad.
Funcionamiento 17
Ordena subgrupos de elementos separados K unidades (respecto de su posición
en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados, se escoge un
nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo
conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el
proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste
de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos;
el último valor debe ser 1.
Código en C de Ordenamiento Shell 18
Listing 3: Ordenamiento Shell
1 void shellSort ( int a [] , int h)
2 {
3 int i ;
4 while (h > 0) {
5 for (i = h -1; i <n; i ++) {
6 int B = a[i ];
7 int j = i;
8 for (j = i; (j >= h) && (a[j - h] > B); j -= h){
9 a[j] = a[j - h ];
10 }
11 a[j] = B;
12 }
13 h = h / 2;
14 }
15 }
Análisis del algoritmo 19
Estabilidad: Este algoritmo se considera estable.
Requerimientos de Memoria: Una variable adicional para realizar los
intercambios. Y una variable para el salto. Requerimiento constante.
Tiempo de Ejecución: Los estudios realizados indican que su complejidad es
de O(n 1,2 ) en el mejor caso y de O(n 1,25 ) en el caso promedio.
Merge sort 20
Este método de ordenamiento fue propuesto en 1945 por John Von Neumann [?].
La lógica detrás del algoritmo radica en dos ideas:
Una lista pequeña se ordena en menos pasos que una lista grande.
Se necesitan menos pasos para construir una lista ordenada a partir de dos
listas también ordenadas, que a partir de dos listas desordenadas.
Merge sort: Funcionamiento 21
Tiene como casos bases un argumento lista con longitud 0 ó 1, entonces ya
está ordenada.
En caso contrario el método divide la lista desordenada en dos sublistas de
aproximadamente la mitad del tamaño.
Posteriormente, ordena cada sublista recursivamente aplicando el
ordenamiento por mezcla.
Finalmente, mezclar las dos sublistas en una sola lista ordenada.
Merge Sort 22
Este método aplica la técnica divide-y-vencerás, dividiendo la secuencia de datos
en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego
se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada,
en forma sucesiva hasta obtener una secuencia única ya ordenada.
Si n = 1 solo hay un elemento por ordenar, sino se hace una ordenamiento de
mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se
ordenan de igual forma. Ejemplo: Se tiene un arreglo de 8 elementos, se ordenan
los 4 elementos de cada arreglo y luego se mezclan. El arreglo de 4 elementos, se
ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2
elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.
Código en C de Merge Sort 23
15 if (i < len_l )
1 void merge ( int * arr , int l , int m , int r){ 16 memcpy ( arr +k , tmp_l +i , sizeof ( int ) *( len_l -i));
2 int len_l = m - l ; 17 if (j < len_r )
3 int len_r = r - m +1; 18 memcpy ( arr +k , tmp_r +j , sizeof ( int ) *( len_r -j));
4 int tmp_l [ len_l ]; 19 }
5 int tmp_r [ len_r ]; 20
6 int i = 0, j= 0, k=l; 21 void merge_sort ( int * arr , int l , int r){
7 22 if (l >= r) return ;
8 memcpy ( tmp_l , arr + l , sizeof ( int ) * len_l ); 23 int m = l + (r +1 - l) / 2;
9 memcpy ( tmp_r , arr + m , sizeof ( int ) * len_r ) ; 24
10 25 merge_sort ( arr , l , m -1) ;
11 while (i < len_l && j < len_r ){ 26 merge_sort ( arr , m , r);
12 if ( tmp_l [i]< tmp_r [j ]) arr [k ++] = tmp_l [i ++]; 27 merge ( arr , l , m , r);
13 else arr [k ++] = tmp_r [j ++]; 28 }
14 }
Análisis del algoritmo 24
Estabilidad: Sí es estable.
Requerimientos de Memoria: Se necesita memoria auxiliar del mismo tamaño
de los conjuntos a mezclar.
Tiempo de Ejecución: O(n log n).
Ordenamiento rápido (Quicksort) 25
Es un algoritmo basado en la técnica de divide y vencerás. Esta es probablemente
la técnica más rápida conocida. Fue desarrollada por Tony Hoare en 1960.
El método se basa en dividir los n elementos de la lista a ordenar en dos partes o
particiones separadas por un elemento: una partición izquierda, un elemento
central denominado pivote o elemento de partición, y una partición derecha. La
partición o división se hace de tal forma que todos los elementos de la primera
sublista (partición izquierda) son menores que todos los elementos de la segunda
sublista (partición derecha). Las dos sublistas se ordenan entonces
independientemente.
Ordenamiento rápido (Quicksort) 26
Para dividir la lista en particiones (sublistas) se elige uno de los elementos de la
lista y se utiliza como pivote o elemento de partición. Si se elige una lista
cualquiera con los elementos en orden aleatorio, se puede seleccionar cualquier
elemento de la lista como pivote, por ejemplo, el primer elemento de la lista. Si la
lista tiene algún orden parcial conocido, se puede tomar otra decisión para el
pivote. Idealmente, el pivote se debe elegir de modo que se divida la lista
exactamente por la mitad, de acuerdo al tamaño relativo de las claves.
Una vez que el pivote ha sido elegido, se utiliza para ordenar el resto de la lista en
dos sublistas: una tiene todas las claves menores que el pivote y la otra, todos los
elementos (claves) mayores que o iguales que el pivote (o al revés). Estas dos listas
parciales se ordenan recursivamente utilizando el mismo algoritmo; es decir, se
llama sucesivamente al propio algoritmo quicksort. La lista final ordenada se
El algoritmo es el siguiente 27
Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el
primer elemento), y por la derecha con j (desde el último elemento).
Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los
intercambias.
Repites esto hasta que se crucen los índices.
El punto en que se cruzan los índices es la posición adecuada para colocar el
elemento de división, porque sabemos que a un lado los elementos son todos
menores y al otro son todos mayores (o habrían sido intercambiados). Al
finalizar este procedimiento el elemento de división queda en una posición en
que todos los elementos a su izquierda son menores que él, y los que están a
su derecha son mayores.
Código en C Quicksort 28
13 j ++;
1 void swap ( int *a , int *b){ 14 }
2 int aux = *a; 15 }
3 * a = *b; 16 swap ( arr + j , arr +r);
4 * b = aux ; 17 return j;
5 } 18 }
6 19
7 int p_sel ( int * arr , int l , int r){ 20 void quick_sort ( int * arr , int l , int r){
8 int p = arr [r ]; 21 if (l >= r) return ;
9 int j =l; 22 int p_idx = p_sel ( arr , l , r);
10 for ( int i = l; i < r; ++ i){ 23 quick_sort ( arr , l , p_idx - 1) ;
11 if ( arr [i] < p){ 24 quick_sort ( arr , p_idx + 1 , r);
12 swap ( arr + i , arr + j); 25 }
Análisis del algoritmo 29
Estabilidad: No es estable.
Requerimientos de Memoria: El espacio en pila usualmente es de orden
O(log n).
Tiempo de Ejecución: caso promedio O(n log n), peor caso O(n 2 ).
Problemas a resolver 30
Utilizando un generador de números aleatorios, cree una lista de 500 enteros.
Realice una prueba de referencia usando algunos de los algoritmos de
ordenamiento vistos. ¿Cuál es la diferencia en la velocidad de ejecución?
Un ordenamiento burbuja puede modificarse para que “burbujee” en ambas
direcciones. La primera pasada mueve la lista hacia “arriba”, y la segunda
pasada la mueve hacia “abajo”. Este patrón alternante continúa hasta que no
son necesarias más pasadas. Implemente esta variación y describa en qué
circunstancias podría ser apropiada.
Implemente el ordenamiento por selección usando asignación simultánea.
Realice una prueba de referencia para un ordenamiento de Shell, utilizando
diferentes conjuntos de incrementos en la misma lista.
Problemas a resolver 31
Implemente la función ordenamientoPorMezcla sin usar el operador de
partición.
Una forma de mejorar el ordenamiento rápido es usar un ordenamiento por
inserción en listas que tengan una longitud pequeña (llamémosla “límite de
partición”). ¿Por qué esto tiene sentido? Re-implemente el ordenamiento
rápido y utilícelo para ordenar una lista aleatoria de enteros. Realice un
análisis utilizando diferentes tamaños de lista para el límite de partición.
Implemente el método de mediana de tres para seleccionar un valor pivote
como una modificación de ordenamientoRapido. Lleve a cabo un experimento
para comparar las dos técnicas.
¿Preguntas? 32
Dr. Gregorio Toscano Pulido <gtoscano@[Link]>
[Link]