Programación General > C/C++
Algoritmo De Ordenacion
excellion:
Hola. Tengo poca experiencia en la programacion y necesito q alguien me ayude a hacer un algoritmo de ordenacion Shell Sort en C.
Me dan un vector de entrada definido como una constante pero cuando tengo que poner las distancias para ordenarlo no sé como hacerlo.
Espero q alguien me pueda dar una idea.
Muchas gracias.
CiRRuS:
El método Shell es un método de inserción directa mejorado. Los elementos se agrupan y ordenan por separado. Primero se ordenan de cuatro en cuatro, luego de dos en dos etc...
Si llamamos t al incremento de los grupos, el algoritmo quedaría:
[CODE]
t = 4;
variables
i, j, k, s: indice;
x: item;
m: 1..t;
h[1] = 9; h[2] = 5; h[3] = 3; h[4] = 1;
para m = 1 a t hacer
k = h[m];
s = -k; // centinela
para i = k + 1 a n hacer
si s = 0 entonces
s = -k;
s = s + 1;
a = x;
fin_si
mientras x.clave < a[j].clave hacer
a[j+k] = a[j];
j = j - k;
fin_mientras
a[j+k] = x;
fin_para
fin_para
[CODE]
Lo he sacao de un libro, es psudocódigo y los incrementos los hace de cuatro en cuatro (t = 4). Si necesitas más ayuda o no te aclaras ya sabes donde estamos.
Nos vemos :hola:
Ruben3d:
Hola.
Para realizar la ordenación Shell has de elegir primeramente un incremento. El propuesto por Shell es h = n/2, donde n es el número de elementos del vector.
Una vez elegido el incremento h, el algoritmo lo dividirá entre dos en cada iteración, hasta que sea 1. Así, tendrá este aspecto:
--- Código: Text --- h = n do { h = h / 2 ... hace una pasada ...} while (h > 1)
Lo que vamos a hacer en cada pasada es ordenar por inserción h subvectores. Cada vector se puede definir como
* Vk = { Ni / i = m*h+k }, i,k,m naturales positivos, k<h</li>Esto como mejor se ve es con un ejemplo (he tabulado los subvectores para que se vea claramente cómo se generan):
--- Código: Text --- Vector: 3 7 2 3 5 8 6 5 3 6 7 9Tamaño: 12h inicial: 6=12/2Subvectores: V0: 3 6 V1: 7 5 V2: 2 3 V3: 3 6 V4: 5 7 V5: 8 9 En la siguiente iteración los vectores que se generarían son (hay que tener en cuenta que no los he ordenado, pero se supone que se tiene que ordenar cada uno independientemente por inserción):
--- Código: Text --- Vector: 3 7 2 3 5 8 6 5 3 6 7 9Tamaño: 12h: 3 = 6/2Subvectores: V0: 3 3 6 6 V1: 7 5 5 7 V2: 2 8 3 9
Creo que con esta explicación ya no te será difícil implementar la ordenación Shell.
Un saludo.
Ruben3d
excellion:
El funcionamiento del algoritmo me ha quedado claro lo que pasa que no se exactamente como hacerlo en C. Tengo un vector de 8 posiciones y lo declaro como constante. ¿Como hago para rellenarlo con los datos que quiera? (una secuencia de numeros desordenados).
El vector tendre q pasarselo como referencia a una funcion y aplicar la ordenacion, pero me lio.
:huh:
Gracias por la ayuda.
Ruben3d:
--- Citar ---Tengo un vector de 8 posiciones y lo declaro como constante. ¿Como hago para rellenarlo con los datos que quiera? (una secuencia de numeros desordenados).
--- Fin de la cita ---
--- Código: Text --- int vector[8];int i;for (i=0; i<8; i++){ scanf("%d", &vector[i]);}
La función debería tener un aspecto similar a este (te lo pongo en pseudocódigo):
--- Código: Text --- // n es el tamañovoid ShellSort(tipo_dato *vector, int n){ int h, j; tipo_dato tmp; h = n/2; while (h>0) // Realiza las pasadas { int i; for (i=h; i<n; i++) { tmp = vector[i]; j = i; while (j-h > 0) { if (tmp < vector[j-h]) { vector[j] = vector[j-h]; j = j-h; } else break; } a[j] = tmp; } h = h/2; }}
Bueno, me ha salido más bien código normal. No te aseguro que la función compile a la primera ni que haya definido bien los límites (en los bucles), pero la idea general es esa (según una antigua función que tengo en pascal).
Un saludo.
Ruben3d
Navegación
[#] Página Siguiente
Ir a la versión completa