Tema
métodos de ordenamiento
objetivo
estudio de los métodos de ordenamiento en los lenguajes de
programación y para facilitar el un correcto
uso de todas la funciones que existen en el lenguaje de programación.
Justificación
estos métodos seran aplicados en la creación de programas
que facilitan el trabajo de nosotros y del usuario.
Marco teórico
metodos de ordenamiento
¿qué es el ordenamiento?
Es la operación de arreglar los registros de una tabla en un orden secuencial de acuerdo a un criterio definido. Este
ordenamiento se efectúa con base en el valor de algún campo del
registro a ser ordenado.
Su objetivo es el facilitar la búsqueda de los elemento del
conjunto ordenado.
El ordenar significa ademas mover datos o referencias para que queden en
una secuencia tal que queden en un orden, este orden
puede ser numérico, alfabético o incluso alfanumérico. Es
conveniente usar un método de ordenamiento
cuando la cantidad de búsquedas es mayor y el factor tiempo es el que
prima en esas búsquedas.
Existen dos tipos de ordenamiento: el interno y el externo.
El método de ordenamiento interno es aquel que los valores a ordenar estan en la memoria principal y que el
tiempo de ordenamiento debe ser el mismo para todos los elementos.
El método de ordenamiento externo es aquel que los valores a ser
ordenados estan en una memoria externa como discos, por lo que
el tiempo para acceder al elemento se debe basar en la última
posición accesada.
Método burbuja
este método funciona de lasiguiente manera: se
recorre el arreglo intercambiando los elementos adyacentes que estén
desordenados. Este método es el mas simple, pues se comparan
todos los elementos de una lista contra todos, con la condición que si
es mayor o menor a otro este cambie de posición
hasta ponerlo en su lugar.
1. Tomar el primer elemento de la lista y se compara con todos los elementos
con la condición si es mayor o menor a dicho elemento, intercambiando de
posición si esta condición se cumple.
2. Se toma el segundo elemento y se lo compara con los otros elementos viendo
si se cumple o no la misma condición que el anterior, hasta el
último de la lista a ordenarse.
Procedimiento:
for (i=1; i<limite; i++)
for j=0; j<limite - 1; j++)
if (vector[j] > vector [j+1])
temp = vector[j];
vector[j] = vector [j+1];
vector [j+1] = temp;
método merge sort
este algoritmo consiste basicamente en dividir en partes iguales la
lista de números y luego mezclarlo comparandolos,
dejandolos ordenados.
El método quicksort divide la estructura en dos y ordena cada mitad
recursivamente. El caso del mergesort es el opuesto, es
decir, en éste método se unen dos estructuras ordenadas para
formar una sola ordenada correctamente.
Tiene la ventaja de que utiliza un tiempo proporcional
a: n log (n), su desventaja radica en que se requiere de un espacio extra para
el procedimiento.
Este tipo de ordenamiento es útil cuando se tiene una estructura
ordenada y los nuevos datos a añadir se
almacenan en una estructuratemporal para después agregarlos a la
estructura original de manera que vuelva a quedar ordenada.
Procedimiento mergesort
/*recibe el arreglo a ordenar un índice l que indica el límite
inferior del arreglo a ordenar y un índice r que indica el límite
superior*/
void mergesort (int a [], int l, int r)
}
a =
a,e,e,l,m,p,x}
a =
el algoritmo de ordenamiento por mezcla (mergesort) se divide en dos procesos,
primero se divide en partes iguales la lista:
public static void mergesort(int[ ] matrix, int init, int n)
}
y el algoritmo que nos permite mezclar los elementos según corresponda:
private static void merge(int[ ] matrix, int init, int n1, int n2)
while (temp1 < n1)
buffer[temp++] = matrix[init + (temp1++)];
while (temp2 < n2)
buffer[temp++] = matrix[init + n1 + (temp2++)];
for (i = 0; i < n1+n2; i++)
matrix[init + i] = buffer[i];
}
metodo rapido o quicksort
sin duda, este algoritmo es uno de los mas eficientes. Este
método es el mas rapido gracias a sus llamadas recursivas,
basandose en la teoría de divide y venceras.
Lo que hace este algoritmo es dividir recurvisamente
el vector en partes iguales, indicando un elemento de inicio, fin y un pivote
(ocomodín) que nos permitira segmentar nuestra lista. Una vez
dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y
todos los menores a su izq. Al finalizar el algoritmo,
nuestros elementos estan ordenados.
Ejemplo no1
si tenemos 3 5 4 8 basicamente lo que hace el algoritmo es dividir la
lista de 4 elementos en partes iguales, por un lado 3,
por otro lado 4 8 y como
comodín o pivote el 5. Luego pregunta, 3 es mayor o
menor que el comodín? Es menor, entonces lo
deja al lado izq. Y como se acabaron los elementos de
ese lado, vamos al otro lado. 4 es mayor o menor que el
pivote? Menor, entonces lo tira a su izq. Luego
pregunta por el 8, al ser mayor lo deja donde esta, quedando algo así
3 4 5 8
en esta figura se ilustra de mejor manera un vector con mas elementos, usando como
pivote el primer elemento:
el algoritmo es el siguiente:
public void _quicksort(int matrix[], int a, int b)
while(matrix[to] > pivot)
if(from <= to)
}while(from <= to);
if(a < to)
if(from < b)
this. Matrix = matrix;
el algoritmo fundamental es el siguiente:
* elegir un elemento de la lista de elementos a ordenar, al que
llamaremospivote.
* resituar los demas elementos de la lista a
cada lado del
pivote, de manera que a un lado queden todos los menores que él, y al
otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a
su derecha como
a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le
correspondera en la lista ordenada.
* la lista queda separada en dos sublistas, una
formada por los elementos a la izquierda del
pivote, y otra por los elementos a su derecha.
* repetir este proceso de forma recursiva para cada
sublista mientras éstas contengan mas de un elemento. Una vez
terminado este proceso todos los elementos
estaran ordenados.
Como se puede suponer, la eficiencia del
algoritmo depende de la posición en la que termine el pivote elegido.
* en el mejor caso, el pivote termina en el centro de la lista,
dividiéndola en dos sublistas de igual tamaño. En este caso, el
orden de complejidad del
algoritmo es o(n·log n).
* en el peor caso, el pivote termina en un extremo de
la lista. El orden de complejidad del
algoritmo es entonces de o(n²). El peor caso
dependera de la implementación del algoritmo,
aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi
ordenadas. Pero principalmente depende del
pivote, si por ejemplo el algoritmo implementado toma como
pivote siempre el primer elemento del
arreglo y el arreglo que le pasamos esta ordenado, siempre va a generar
a su izquierda un arreglo vacío, lo que esineficiente.
* en el caso promedio, el orden es o(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se
aplican al algoritmo se centren en la elección del pivote.
Ejemplo no 2
en el siguiente ejemplo se marcan el pivote y los índices i y j con las
letras p, i y j respectivamente.
Comenzamos con la lista completa. El elemento divisor sera el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4
p
comparamos con el 5 por la izquierda y el 1 por la derecha.
5 - 3 - 7 - 6 - 2 - 1 - 4
i j p
5 es mayor que 4 y 1 es menor. Intercambiamos
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
avanzamos por la izquierda y la derecha:
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos
ahí.
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
7 es mayor que 4 y 2 es menor: intercambiamos.
1 - 3 - 2 - 6 - 7 - 5 - 4
i j p
avanzamos por ambos lados
1 - 3 - 2 - 6 - 7 - 5 - 4
iyj p
en este momento termina el ciclo principal, porque los índices se
cruzaron. Ahoraintercambiamos lista[i] con lista[sup]
(pasos 16-18):
1 - 3 - 2 - 4 - 7 - 5 - 6
p
aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2).
Tenemos lo siguiente
1 - 3 - 2
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la
derecha. Como se intercambiaron los índices termina el ciclo. Se
intercambia lista[i] con lista[sup]:
1 - 2 - 3
el mismo procedimiento se aplicara a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial
ordenada en forma ascendente.
1 - 2 - 3 - 4 - 5 - 6 - 7
void quicksort(int a[], int l, int r)
swap(a,i,r);
quicksort(a,l,i-1);
quicksort(a,i+1,r);
}
}
a =
a i o r t s n
a i n r t s o
a i n o t s r
a i n o r s tordenación por cubetas (binsort)
suponemos que los datos a ordenar son números naturales, todos distintos
y comprendidos en el intervalo [1,n]. Es decir, nuestro problema es ordenar un vector con los n primeros números naturales. Bajo
esas circunstancias es posible implementar un algoritmo de complejidad temporal
o(n). Es el método de ordenación por
cubetas, en donde en cada iteración se sitúa un elemento en su
posición definitiva:
procedure cubetas(var a:vector);
var i:cardinal;
begin
for i:=1 to n do
while a[i]<>i do
intercambia(a,i,a[i])
end
end
end cubetas
ordenación por residuos (radix)
este método puede utilizarse cuando los valores a ordenar estan
compuestos por
secuencias de letras o dígitos que admiten un orden
lexicografico. Éste es el caso
de palabras, números (cuyos dígitos admiten este orden) o bien
fechas.
El método consiste en definir k colas (numeradas de 0
a k–1) siendo k los
posibles valores que puede tomar cada uno de los dígitos que componen la
secuencia. Una vez tengamos las colas habría que repetir, para i
a partir de 0 y
hasta llegar al número maximo de dígitos o letras de
nuestras cadenas
1. Distribuir los elementos en las colas en función del dígito i.
2. Extraer ordenada y consecutivamente los elementos de las colas
introduciéndolos de nuevo en el vector.
Los elementos quedan ordenados sin haber realizado
ninguna comparación.
Descripción
la mayor parte de los ordenadores digitales representan internamente todos sus
datos como
representacioneselectrónicas de números binarios, por lo que procesar
los dígitos de las representaciones de enteros por representaciones de
grupos de dígitos binarios es lo mas conveniente. Existen dos
clasificaciones de radix sort: el de dígito menos significativo (lsd) y
el de dígito mas significativo (msd). Radix sort
lsd procesa las representaciones de enteros empezando por el dígito
menos significativo y moviéndose hacia el dígito mas
significativo. Radix sort msd trabaja en sentido
contrario.
Ejemplo no 1
vector original
25 57 48 37 12 92 86 33
asignamos los elementos en colas basadas en el dígito menos
significativo de cada uno de ellos.
0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9
después de la primera pasada, la ordenación queda:
12 92 33 25 86 57 37 48
colas basadas en el dígito mas significativo.
0:
1:12
2:25
3:33 37
4:48
5:57
6:
7:
8:86
9:92
lista ordenada
12 25 33 37 48 57 86 92
conclusión
metodos de ordenamiento
¿qué es el ordenamiento?
Es la operación de arreglar los registros de una tabla en un orden secuencial de acuerdo a un criterio definido. Este
ordenamiento se efectúa con base en el valor de algún campo del
registro a ser ordenado.
Su objetivo es el facilitar la búsqueda de los elemento del
conjunto ordenado.
El ordenar significa ademas mover datos o referencias para que queden en
una secuencia tal que queden en un orden, este orden
puede ser numérico, alfabético o incluso alfanumérico. Es
conveniente usar un método de ordenamiento
cuando lacantidad de búsquedas es mayor y el factor tiempo es el que
prima en esas búsquedas.
Existen dos tipos de ordenamiento: el interno y el externo.
El método de ordenamiento interno es aquel que los valores a ordenar estan en la memoria principal y que el
tiempo de ordenamiento debe ser el mismo para todos los elementos.
El método de ordenamiento externo es aquel que los valores a ser
ordenados estan en una memoria externa como discos, por lo
que el tiempo para acceder al elemento se debe basar en la última
posición accesada.
Método burbuja
este método funciona de la siguiente manera: se
recorre el arreglo intercambiando los elementos adyacentes que estén
desordenados. Este método es el mas simple, pues se comparan
todos los elementos de una lista contra todos, con la condición que si
es mayor o menor a otro este cambie de posición
hasta ponerlo en su lugar.
3. Tomar el primer elemento de la lista y se compara con todos los elementos
con la condición si es mayor o menor a dicho elemento, intercambiando de
posición si esta condición se cumple.
4. Se toma el segundo elemento y se lo compara con los otros elementos viendo
si se cumple o no la misma condición que el anterior, hasta el
último de la lista a ordenarse.
For (i=1; i<limite; i++)
for j=0; j<limite - 1; j++)
if (vector[j] > vector [j+1])
temp = vector[j];
vector[j] = vector [j+1];
vector [j+1] = temp;
método merge sort
este algoritmo consiste basicamente en dividir en partes iguales la
lista de números yluego mezclarlo comparandolos,
dejandolos ordenados.
El método quicksort divide la estructura en dos y ordena cada mitad
recursivamente. El caso del mergesort es el opuesto, es
decir, en éste método se unen dos estructuras ordenadas para
formar una sola ordenada correctamente.
Tiene la ventaja de que utiliza un tiempo proporcional
a: n log (n), su desventaja radica en que se requiere de un espacio extra para
el procedimiento.
Este tipo de ordenamiento es útil cuando se tiene una estructura
ordenada y los nuevos datos a añadir se
almacenan en una estructura temporal para después agregarlos a la
estructura original de manera que vuelva a quedar ordenada.
Procedimiento mergesort
/*recibe el arreglo a ordenar un índice l que indica el límite
inferior del arreglo a ordenar y un índice r que indica el límite
superior*/
void mergesort (int a [], int l, int r)
}a =
a,e,e,l,m,p,x}
a =
el algoritmo de ordenamiento por mezcla (mergesort) se divide en dos procesos,
primero se divide en partes iguales la lista:
public static void mergesort(int[ ] matrix, int init, int n)
}
y el algoritmo que nos permite mezclar los elementos según corresponda:
private static void merge(int[ ] matrix, int init, int n1, int n2)
while (temp1 < n1)
buffer[temp++] = matrix[init + (temp1++)];
while (temp2 < n2)
buffer[temp++] = matrix[init + n1 + (temp2++)];
for (i = 0; i < n1+n2; i++)
matrix[init + i] = buffer[i];
}
metodo rapido o quicksort
sin duda, este algoritmo es uno de los mas eficientes. Este
método es el mas rapido
gracias a sus llamadas recursivas, basandose en la teoría de
divide y venceras.
Lo que hace este algoritmo es dividir recurvisamente el vector en partes
iguales
indicando un elemento de inicio, fin y un pivote (o comodín) que nos
permitira
segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los
mayores que
el pivote a su derecha y todos los menores a su izq. Al
finalizar el algoritmo, nuestros
elementos estan ordenados.
Por ejemplo, si tenemos 3 5 4 8 basicamente lo que hace el algoritmo es
dividir la
lista de 4 elementos en partes iguales, por un lado 3,
por otro lado 4 8 y como
comodín o pivote el 5. Luego pregunta, 3 es mayor o
menor que el comodín? Es
menor, entonces lo deja al lado izq. Y como se acabaron los elementos de ese lado
vamos al otro lado. 4 es mayor o menor que el pivote? Menor, entonces lo tira a su
izq. Luego pregunta por el 8, al ser mayor lo deja donde esta, quedando
algo así
3 4 5 8
en esta figura se ilustra de mejor manera un vector con mas elementos, usando como
pivote el primer elemento:
el algoritmo es el siguiente:
public void _quicksort(int matrix[], int a, int b)
while(matrix[to] > pivot)
if(from <= to)
}while(from <= to);
if(a < to)
if(from < b)
this. Matrix = matrix;
el algoritmo fundamental es el siguiente:
* elegir un elemento de la lista de elementos a ordenar, al que llamaremos
pivote.
* resituar los demas elementos de la lista a
cada lado del
pivote, de manera que a un lado queden todos los menores que él, y al
otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a
su derecha como
a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le
correspondera en la lista ordenada.
* la lista queda separada en dos sublistas, una
formada por los elementos a la izquierda del
pivote, y otra por los elementos a su derecha.
* repetir este proceso de forma recursiva para cada
sublista mientras éstas contengan mas de un elemento. Una vez
terminado este proceso todos los elementos
estaran ordenados.
Como se puede suponer, la eficiencia del
algoritmo depende de la posición en la que termine el pivote elegido.
* en el mejor caso, el pivote termina en el centro de la lista,
dividiéndola en dos sublistas de igual tamaño. En estecaso, el
orden de complejidad del
algoritmo es o(n·log n).
* en el peor caso, el pivote termina en un extremo de
la lista. El orden de complejidad del
algoritmo es entonces de o(n²). El peor caso
dependera de la implementación del algoritmo,
aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi
ordenadas. Pero principalmente depende del
pivote, si por ejemplo el algoritmo implementado toma como
pivote siempre el primer elemento del
arreglo y el arreglo que le pasamos esta ordenado, siempre va a generar
a su izquierda un arreglo vacío, lo que es ineficiente.
* en el caso promedio, el orden es o(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se
aplican al algoritmo se centren en la elección del pivote.
Eejmplo
en el siguiente ejemplo se marcan el pivote y los índices i y j con las
letras p, i y j respectivamente.
Comenzamos con la lista completa. El elemento divisor sera el 4:
5 - 3 - 7 - 6 - 2 - 1 - 4
p
comparamos con el 5 por la izquierda y el 1 por la derecha.
5 - 3 - 7 - 6 - 2 - 1 - 4
i j p
5 es mayor que 4 y 1 es menor. Intercambiamos
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
avanzamos por la izquierda y la derecha:
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos
mantenemos ahí.
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
7 es mayor que 4 y 2 es menor: intercambiamos.
1 - 3 - 2 - 6 - 7 - 5 - 4
i j p
avanzamos por ambos lados
1 - 3 - 2 - 6 - 7 - 5 - 4
iyj p
en este momento termina el ciclo principal, porque los índices se
cruzaron. Ahora intercambiamos lista[i] con lista[sup]
(pasos 16-18):
1 - 3 - 2 - 4 - 7 - 5 - 6
p
aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2).
Tenemos lo siguiente
1 - 3 - 2
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la
derecha. Como se intercambiaron los índices termina el ciclo. Se
intercambia lista[i] con lista[sup]:
1 - 2 - 3
el mismo procedimiento se aplicara a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial
ordenada en forma ascendente.
1 - 2 - 3 - 4 - 5 - 6 - 7
void quicksort(int a[], int l, int r)
swap(a,i,r);
quicksort(a,l,i-1);
quicksort(a,i+1,r);
}
}
a =
a i o r t s n
a i n r t s o
a i n o t s r
a i n o r s t
2.9.1
ordenación por cubetas (binsort)
suponemos que los datos a ordenar son números naturales, todos distintos
y
comprendidos en el intervalo [1,n]. Es decir, nuestro problema es ordenar un vector
con los n primeros números naturales. Bajo esas circunstancias es
posible
implementar un algoritmo de complejidad temporal o(n).
Es el método de
ordenación por cubetas, en donde en cada iteración se
sitúa un elemento en su
posición definitiva:
procedure cubetas(var a:vector);
var i:cardinal;
begin
for i:=1 to n do
while a[i]<>i do
intercambia(a,i,a[i])
end
end
end cubetas
2.9.2 ordenación por residuos (radix)
este método puede utilizarse cuando los valores a ordenar estan
compuestos por
secuencias de letras o dígitos que admiten un orden
lexicografico. Éste es el caso
de palabras, números (cuyos dígitos admiten este orden) o bien
fechas.
El método consiste en definir k colas (numeradas de 0
a k–1) siendo k los
posiblesvalores que puede tomar cada uno de los dígitos que componen la
secuencia. Una vez tengamos las colas habría que repetir, para i
a partir de 0 y
hasta llegar al número maximo de dígitos o letras de
nuestras cadenas
1. Distribuir los elementos en las colas en función del dígito i.
2. Extraer ordenada y consecutivamente los elementos de las colas
introduciéndolos de nuevo en el vector.
Los elementos quedan ordenados sin haber realizado
ninguna comparación.
Descripción
la mayor parte de los ordenadores digitales representan internamente todos sus datos
como
representaciones electrónicas de números binarios, por lo que
procesar los dígitos de las representaciones de enteros por
representaciones de grupos de dígitos binarios es lo mas
conveniente. Existen dos clasificaciones de radix sort: el de dígito
menos significativo (lsd) y el de dígito mas significativo (msd).
Radix sort lsd procesa las representaciones de enteros
empezando por el dígito menos significativo y moviéndose hacia el
dígito mas significativo. Radix sort msd
trabaja en sentido contrario.
Ejemplo
vector original
25 57 48 37 12 92 86 33
asignamos los elementos en colas basadas en el dígito menos
significativo de cada uno de ellos.
0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9
después de la primera pasada, la ordenación queda:
12 92 33 25 86 57 37 48
colas basadas en el dígito mas significativo.
0:
1:12
2:25
3:33 37
4:48
5:57
6:
7:
8:86
9:92
lista ordenada
12 25 33 37 48 57 86 92
