Ordenación Shell Sort
De Wikipedia, la enciclopedia libre
El Shell Sort es un algoritmo de ordenación de disminución incremental, nombrado así debido a su inventor Donald Shell. El rendimiento de este algoritmo depende del orden de la tabla inicial y va de n2 en el caso peor a n4 / 3 y se puede mejorar.
Tabla de contenidos |
[editar] Descripción del algoritmo
El algoritmo ordena subgrupos de elementos separados k unidades (respecto de su posición en la tabla) en la tabla original. El valor k es llamado incremento. Después de que los primeros k subgrupos han sido ordenados (generalmente utilizando Ordenamiento por inserción), se escoge un nuevo valor de k más pequeño, y la tabla es de nuevo partida entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de k hasta que en algún momento k llega a valer 1.
[editar] Código en Java
void shell_sort(int[] A, int n) // ordena A[0], A[1], ... , A[n-1]
{
int i, j, k, m=0, temp;
int[] incrementos = { 1,4,10,23,57,143,311,666,1787,4711,11841,27901,
84833,213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647 };
while (incrementos[m] < n) // busca el mayor incremento menor que n
++m;
while (--m >= 0)
{
k = incrementos[m];
for (i=k; i<n; i++) // ordena k subgrupos con insertionsort
{
j = i;
temp = A[i];
while ((j >= k) && (A[j-k] > temp))
{
A[j] = A[j - k];
j = j - k;
}
A[j] = temp;
}
}
}
[editar] Algoritmo Shell en C++
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define n 100
void shell_sort(int A[], int size)
{
int i, j, incrmnt, temp;
incrmnt = 3;
while (incrmnt > 0)
{
for (i=0; i < size; i++)
{
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp))
{
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
if (incrmnt/2 != 0)
incrmnt = incrmnt/2;
else if (incrmnt == 1)
incrmnt = 0;
else
incrmnt = 1;
}
//imprime arreglo
for(i=0;i<n;i++)
printf("%d ",A[i]);
}
main()
{
int A[n],a,i;
clrscr();
randomize();
for (i=0;i<n;i++)
A[i]=random(5);
shell_sort(A,n);
getch();
return 0;
}
[editar] Pseudocódigo en C del Shell Sort
/* Ordenación por ShellSort
tabla T: tabla a ordenar
índice P = principio de la tabla
índice U = final de la tabla
tabla Inc = tabla con los incrementos de mayor a menor. Un ejemplo podría ser 4,3,2,1
entero nInc = número de incrementos
*/
ShellSort (tabla T, indice P, indice U)
tabla Inc = [4,3,2,1]
entero nInc = 4
for (i=1; i<nInc; i++)
for (j=0; j<Inc[i]; j++)
InsertSortconIncrementos (T, P+j-1, Inc[i])
/* Es el InsertSort pero con subtablas */
InsertSortconIncrementos (tabla T, indice P, indice U, entero k)
i = P + k;
while (i <= U)
A = T[i]
j = i - k
while (j >= P ) y (T[j] > A)
T[j+k] = T[j]
j = j - k
T[j+k] = A
i = i + k
[editar] Pseudocódigo de Shell Sort en Pascal
Procedimiento Shell Sort;
const MAXINC = _____;
incrementos = array[1..MAXINC] of integer;
var j,p,num,incre,k:integer;
begin
for incre := 1 to MAXINC do begin
k := inc[incre]; /* k recibe un tipo de incremento */
for p := k+1 to MAXREG do begin /* inserción directa para el grupo que se encuentra
cada k posiciones */
num := reg[p];
j := p-k;
while (j>0) AND (num < reg[j]) begin
reg[j+k] := reg[j];
j := j - k;
end;
reg[j+k] := num;
end
end
end;
[editar] Implementación en WinPseudo 1.4
#
# Shell Sort. Herbert Schildt, "Advanced C", Pag. 13.
#
INICIO Programa 18 - Shell Sort. Herbert Schildt, "Advanced C", Pag. 13.
VAR
VECTOR Vect[150]
VECTOR A[5]
NUMERICO i
NUMERICO j
NUMERICO k
NUMERICO s
NUMERICO w
NUMERICO Aux
NUMERICO Cant
FIN-VAR
Cant = 150
i = 0
MIENTRAS (i < Cant)
Vect[i] = Cant - i
i = i + 1
FIN-MIENTRAS
A[0] = 9
A[1] = 5
A[2] = 3
A[3] = 2
A[4] = 1
w = 0
MIENTRAS (w < 5)
k = A[w]
s = 0 - k
i = k
MIENTRAS (i < Cant)
Aux = Vect[i]
j = i - k
SI (s = 0)
s = 0 - k
s = s + 1
Vect[s] = Aux
FIN-SI
MIENTRAS ((Aux < Vect[j]) & (j >= 0) & (j <= Cant))
Vect[j+k] = Vect[j]
j = j - k
FIN-MIENTRAS
Vect[j+k] = Aux
i = i + 1
FIN-MIENTRAS
w = w + 1
FIN-MIENTRAS
i = 0
MIENTRAS (i < Cant)
imprimir entero (Vect[i])
imprimir ", "
i = i + 1
FIN-MIENTRAS
FINAL
[editar] Ejemplo
Para el arreglo a = [6, 1, 5, 2, 3, 4, 0] Tenemos el siguiente recorrido:
Recorrido Salto Lista Ordenada Intercambio 1 3 2,1,4,0,3,5,6 (6,2), (5,4), (6,0) 2 3 0,1,4,2,3,5,6 (2,0) 3 3 0,1,4,2,3,5,6 Ninguno 4 1 0,1,2,3,4,5,6 (4,2), (4,3) 5 1 0,1,2,3,4,5,6 Ninguno
