SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: excellion en Martes 24 de Febrero de 2004, 15:01

Título: Algoritmo De Ordenacion
Publicado por: excellion en Martes 24 de Febrero de 2004, 15:01
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.
Título: Re: Algoritmo De Ordenacion
Publicado por: CiRRuS en Martes 24 de Febrero de 2004, 16:16
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:
Título: Re: Algoritmo De Ordenacion
Publicado por: Ruben3d en Martes 24 de Febrero de 2004, 16:19
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
  1.  
  2. h = n
  3.  
  4. do {
  5.     h = h / 2
  6.     ...
  7.     hace una pasada
  8.     ...
  9. } while (h &#62; 1)
  10.  
  11.  

Lo que vamos a hacer en cada pasada es ordenar por inserción h subvectores. Cada vector se puede definir comoEsto como mejor se ve es con un ejemplo (he tabulado los subvectores para que se vea claramente cómo se generan):

Código: Text
  1.  
  2. Vector: 3 7 2 3 5 8 6 5 3 6 7 9
  3. Tamaño: 12
  4. h inicial: 6=12/2
  5. Subvectores:
  6.      V0: 3           6
  7.      V1:   7           5
  8.      V2:     2           3
  9.      V3:       3           6
  10.      V4:         5           7
  11.      V5:           8           9
  12.  
  13.  
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
  1.  
  2. Vector: 3 7 2 3 5 8 6 5 3 6 7 9
  3. Tamaño: 12
  4. h: 3 = 6/2
  5. Subvectores:
  6.      V0: 3     3     6     6    
  7.      V1:   7     5     5     7
  8.      V2:     2     8     3     9
  9.  
  10.  

Creo que con esta explicación ya no te será difícil implementar la ordenación Shell.

Un saludo.

Ruben3d
Título: Re: Algoritmo De Ordenacion
Publicado por: excellion en Martes 24 de Febrero de 2004, 17:01
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.
Título: Re: Algoritmo De Ordenacion
Publicado por: Ruben3d en Martes 24 de Febrero de 2004, 17:52
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).
Código: Text
  1.  
  2. int vector[8];
  3. int i;
  4. for (i=0; i&#60;8; i++)
  5. {
  6.     scanf(&#34;%d&#34;, &vector[i]);
  7. }
  8.  
  9.  

La función debería tener un aspecto similar a este (te lo pongo en pseudocódigo):

Código: Text
  1.  
  2. // n es el tamaño
  3. void ShellSort(tipo_dato *vector, int n)
  4. {
  5.     int h, j;
  6.     tipo_dato tmp;
  7.  
  8.     h = n/2;
  9.     while (h&#62;0)   // Realiza las pasadas
  10.     {
  11.         int i;
  12.         for (i=h; i&#60;n; i++)
  13.         {
  14.             tmp = vector[i];
  15.             j = i;
  16.             while (j-h &#62; 0)
  17.             {
  18.                 if (tmp &#60; vector[j-h])
  19.                 {
  20.                     vector[j] = vector[j-h];
  21.                     j = j-h;
  22.                 }
  23.                 else
  24.                     break;
  25.             }
  26.             a[j] = tmp;
  27.         }
  28.         h = h/2;
  29.     }
  30. }
  31.  
  32.  

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
Título: Re: Algoritmo De Ordenacion
Publicado por: excellion en Martes 24 de Febrero de 2004, 18:54
Muchas gracias. Me habeis ayudado mucho. Os adjunto el fichero para que me confirmeis si lo he hecho bien.

Gracias.