Métodos de
Ordenamiento
Los métodos de ordenamiento son necesarios para que luego de ordenar, se puedan buscar datos de una manera mucho más rápida y eficiente aplicando distintas técnicas.
Ordenamientos
Internos y Externos
Internos: los valores a ordenar están en memoria principal, por lo que se
asume que el tiempo que se requiere para acceder cualquier elemento sea el
mismo (a[1], a[500], etc).
Externos: Los valores a ordenar están en memoria secundaria (disco, cinta,
cilindro magnético, etc), por lo que se asume que el tiempo que se requiere
para acceder a cualquier elemento depende de la última posición accesada
(posición 1, posición 500…)
Método de ordenamiento Burbuja
·
ALGORITMO
for ( i=1; i
for( j=0;j if (a[j] > a[j+1]) temp = a[j]; a[j]= a[j+1]; a[j+1]= temp; } |
·
DIAGRAMA DE FLUJO
Ventajas:
- Fácil implementación.
- No requiere memoria adicional. |
Desventajas:
- Muy
lento.
- Realiza numerosas comparaciones. - Realiza numerosos intercambios. |
Ejemplo:
Método de ordenamiento por selección
·
ALGORITMO
for (i=0; i
pos_men = Menor(lista, TAM, i) temp = lista[i]; lista[i] = lista [pos_men]; lista [pos_men] = temp; } |
·
DIAGRAMA DE FLUJO
Menor(lista,TAM,i)
es una función que busca el elemento menor del arreglo llamado lista que se
encuentra entre las posiciones i y la posición TAM, y devuelve la el
identificador. A continuación se encuentra el código de la función:
int menor
(tipo arreglo, int largo, int j) {
tipo menor=arreglo[j]; int pos_menor=j; for (j++;j if (arreglo[j] menor=arreglo[j]; pos_menor=j; } return pos_menor; } //Fin del for |
EJEMPLO
Ventajas:
- Fácil implementación. - No requiere memoria adicional. - Realiza pocos intercambios. - Rendimiento constante: poca diferencia entre el peor y el mejor caso. |
Desventajas:
- Lento.
- Realiza
numerosas comparaciones.
|
Ordenamiento por inserción
·
ALGORITMO
for (i=1;
i
temp = lista[ i ]; j = i - 1 ; while ( (lista[ j ] > temp) && (j >= 0) ) { lista[ j+1] = lista[ j ] ; j-- ; } //Fin while lista [ j+1] = temp; }//Fin for |
·
DIAGRAMA DE FLUJO
ejemplo
Ventajas:
- Fácil
implementación.
-
Requerimientos mínimos de memoria.
|
Desventajas:
- Lento.
- Realiza
numerosas comparaciones
|
Quicksort
El
algoritmo quicksort es quizá el más eficiente de los algoritmos de
ordenamiento, debido a que su complejidad es mínima y por lo tanto su tiempo de
ejecución también es mínimo. Se divide la lista en dos sublistas y ordenarlas
en forma independiente cada una. El proceso de partición es repetido hasta
llegar a listas de tamaño 1 (que están ordenadas).
·
ALGORITMO
while(i<=j) {
for(i=izquierda;v[i]<pivote;i++);
for(j=derecha;v[j]>pivote;j--);
if(i<=j) {
tmp = v[i];
v[i]=v[j];
v[j]=tmp ;
i++;
j--;
}
}
if (izquierda<j){
quicksort (v,izquierda,j);}
if (i<derecha){
quicksort(v,i,derecha);}
}
|
DIAGRAMA DE FLUJO
MÉTODO SHELL
Es una mejora del método de inserción directa, utilizado cuando el array
tiene un gran número de elementos.
Cualquier algoritmo de ordenación que intercambia elementos adyacentes
(como los algoritmos burbuja, selección o inserción) tiene un tiempo promedio
de ejecución de orden cuadrático (n2). El método Shell mejora este
tiempo comparando cada elemento con el que está a un cierto número de posiciones
llamado salto, en lugar de compararlo con el el que está justo a su lado. Este
salto es constante, y su valor inicial es N/2 (siendo N el número de elementos,
y siendo división entera).
Se van dando pasadas con el mismo salto hasta que en una pasada no se
intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y
se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así
sucesivamente hasta que el salto vale 1.
·
ALGORITMO
Ejemplo:
public static void
shell(int A[]){
int salto, aux, i;
boolean cambios;
for(salto=A.length/2; salto!=0;
salto/=2){
cambios=true;
while(cambios){ //
Mientras se intercambie algún elemento
cambios=false;
for(i=salto; i< A.length;
i++) // se da una pasada
if(A[i-salto]>A[i]){ //
y si están desordenados
aux=A[i]; // se reordenan
A[i]=A[i-salto];
A[i-salto]=aux;
cambios=true; // y se
marca como cambio.
}
}
}
}
|
