El
método de ordenación Shell debe su nombre a su inventor, Donald
Shell, y fue uno de los primeros algoritmos de ordenamiento en romper
la barrera del tiempo cuadrático.
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.
El
método Shell de ordenación en Java para ordenar un array A de
enteros es el siguiente:
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.
}
}
}
}
}
Ejemplo
de ejecución:
Con
sólo 6 intercambios se ha ordenado el array, cuando por inserción
se necesitaban muchos más. El rendimiento del método Shell de
ordenación es bastante aceptable, aún para el caso de un número de
elementos muy grande. Se ha comprobado que el tiempo
de ejecución promedio es de O(n2/3)
para la mayoría de las secuencias de salto.
Cómo muestro la información del ordenado en consola?
ResponderEliminarstatic void Impresion (int[] numeros){
Eliminarfor (int i = 0; i < numeros.length; i++) {
System.out.println("["+numeros[i]+"]");
}
}
Utiliza otro for
ResponderEliminarfor(int i=0;i<A.lenght;i++){
sout(A[i]);
}
En que parte meto el for?
Eliminardisculpa como lo arias de modo gráfico me puede ayudar?
ResponderEliminaryo lo hice de forma grafica
Eliminarpublic void shell() {
Eliminarint salto, aux, i; //variables
it=transformar(); //it se convierte en el metodo transformar
Imprimir();
boolean cambios;
//bucle for para poder leer los datos ingresados
for (salto = it.length / 2; salto>0;salto=salto==2 ? 1 : (int)(salto / 2.2));{
//bucle para poder
for (salto = it.length / 2; salto != 0; salto /= 2) {
cambios = true;
while (cambios) { // Mientras se intercambie algún elemento
cambios = false;
for (i = salto; i < it.length; i++) // se da una pasada
{
if (it[i - salto] > it[i]) { // y si están desordenados
aux = it[i]; // se reordenan
it[i] = it[i - salto];
it[i - salto] = aux;
cambios = true; // y se marca como cambio.
Imprimir();
}
}
}
}
}
}
Como se cuantos intercambio y comparaciones han echo?
ResponderEliminarme pueden ayudar con este programa... Un array contiene los elementos indicados más abajo. Utilizando el algoritmo de
ResponderEliminarordenación Shell, encuentre las pasadas y los intercambios que se realizan para su
ordenación.
8 43 17 6 40 16 18 97 11 7
probaste con una prueba de escritorio?
Eliminarsino toma, cambia el array y parametros noma
#include
#define N 5
void mostrarLista(int*);
int main(int argc, char** argv){
int arreglo[N]={5,2,4,1,3};
int i,clave,j;
//Recorrer el arreglo
for (i = 1; i < N; i++){
clave = *(arreglo+i);
j = i-1;
//Comparar el valor selecionado con todos los valores anteriores
while (j >= 0 && *(arreglo+j) > clave){
//Insertar el valor donde corresponda
*(arreglo+j+1) = *(arreglo+j);
j = j-1;
}
*(arreglo+j+1) = clave;
mostrarLista(arreglo);
}
mostrarLista(arreglo);
return 0;
}
//Función para mostrar estado de la lista
void mostrarLista(int *lista){
int i;
for (i=0; i< N; i++){
printf("%d ",*(lista+i));
}
printf("\n");;
}
como haria oara ordenar un jtable
ResponderEliminar