Clasificación de concha

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de julio de 2020; las comprobaciones requieren 23 ediciones .

Clasificación de concha
Ordenar con los pasos 23, 10, 4, 1.
Autor	Concha, Donald [1]
objetivo	Algoritmo de clasificación
Estructura de datos	formación
peor momento	O( n 2 )
Mejor tiempo	O( n log 2 n )
Tiempo promedio	depende de los pasos elegidos
costo de memoria	O(n) total, O(1) adicional

Shell sort es un algoritmo de clasificación que es una versión mejorada de la ordenación por inserción . La idea del método Shell es comparar elementos que no solo están uno al lado del otro, sino también a cierta distancia entre sí. En otras palabras, se trata de una clasificación por inserción con pases preliminares "aproximados". Una mejora similar a la clasificación de burbuja se llama clasificación de peine .

Descripción

Al clasificar Shell, los valores primero se comparan y clasifican entre sí, parándose uno del otro a cierta distancia ( ver más abajo para elegir un valor ). Después de eso, el procedimiento se repite para algunos valores más pequeños de , y la clasificación de Shell se completa ordenando los elementos en (es decir, la clasificación de inserción habitual ). La eficiencia de Shell sort en ciertos casos está garantizada por el hecho de que los elementos se colocan "más rápido" (en métodos de clasificación simples, por ejemplo, bubble sort , cada permutación de dos elementos reduce el número de inversiones en la lista en un máximo de 1, y con Shell sort este número puede ser más). $d$ $d$ $d$ $re=1$

Aunque Shellsort es más lento que quicksort en muchos casos , tiene una serie de ventajas:

sin necesidad de memoria de pila;
sin degradación en conjuntos de datos incorrectos: Quicksort se degrada fácilmente a O (n²), que es peor que el peor tiempo garantizado para Shellsort.

Historia

Shell sort lleva el nombre de su inventor, Donald Shell , quien publicó el algoritmo en 1959 .

Ejemplo

Deje que se dé una lista y se ordene por el método Shell, y . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

El primer paso ordena las sublistas compuestas por todos los elementos que difieren en 5 posiciones, es decir, las sublistas , , , , . $A$ $A$ $A_{{5,1}}=(32,66,40)$ $A_{{5,2}}=(95,35,43)$ $A_{{5,3}}=(16,19,93)$ $A_{{5,4}}=(82,75,68)$ $A_{{5,5}}=(24,54)$

En la lista resultante, en el segundo paso, las sublistas se ordenan nuevamente a partir de elementos espaciados por 3 posiciones.

El proceso finaliza con el tipo de inserción habitual de la lista resultante.

Elegir la longitud de los espacios

El tiempo promedio de ejecución del algoritmo depende de la longitud de los intervalos - , que contendrán los elementos ordenados de la matriz original con una capacidad en cada paso del algoritmo. Hay varios enfoques para elegir estos valores: $d$ $norte$

la secuencia de longitudes de intervalo utilizada originalmente por Shell: en el peor de los casos, la complejidad del algoritmo será ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Secuencia propuesta por Hibbard: todos los valores ; tal secuencia de pasos conduce a un algoritmo de complejidad ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/2}})$
secuencia propuesta por Sedgwick : si i es par y si i es impar. Al utilizar dichos incrementos, la complejidad media del algoritmo es: , y en el peor de los casos del orden de . Cuando utilice la fórmula de Sedgwick, debe detenerse en el valor inc[s-1] si 3*inc[s] > tamaño. [2] ; $d_{i}=9\cdot 2^{i}-9\cdot 2^{i/2}+1$ $d_{i}=8\cdot 2^{i}-6\cdot 2^{(i+1)/2}+1$ $O(n^{{7/6}})$ $O(n^{{4/3}})$
secuencia propuesta por Pratt: todos los valores ; en este caso, la complejidad del algoritmo es ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(registroN)^{2})$
secuencia empírica de Marcin Ciur (secuencia A102549 en OEIS ): ; es uno de los mejores para ordenar una matriz de hasta aproximadamente 4000 elementos. [3] ; ${\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\right\))$
secuencia empírica basada en números de Fibonacci : ; $d\in \left\{F_{n}\right\}$
todos los valores ${\ estilo de visualización (3 ^ {j} -1) \ leq N}$ , ; tal secuencia de pasos conduce a un algoritmo de complejidad . $j\in {\mathbb N}$ $O(N^{{3/2}})$

Implementación en C++

plantilla < nombre de tipo RandomAccessIterator , nombre de tipo Comparar > void shell_sort ( RandomAccessIterator primero , RandomAccessIterator último , Compare comp ) { for ( auto d = ( último - primero ) / 2 ; d != 0 ; d /= 2 ) //necesita un ciclo para primero = a[0..d-1] for ( auto i = primero + d ; i != último ; ++ i ) for ( auto j = i ; j - primero >= d && comp ( * j , * ( j - d ) ); j -= d ) estándar :: intercambio ( * j , * ( j - d ) ); }

Implementación en C

void shell_sort ( int * matriz , tamaño int ) { para ( int s = tamaño / 2 ; s > 0 ; s /= 2 ) { para ( int i = s ; i < tamaño ; ++ i ) { for ( int j = i - s ; j >= 0 && arreglo [ j ] > arreglo [ j + s ]; j -= s ) { inttemp = matriz [ j ] ; arreglo [ j ] = arreglo [ j + s ]; matriz [ j + s ] = temporal ; } } } }

Implementación en Java

clase pública ShellSort { public static void shellSort ( int [] matriz ) { int h = 1 ; while ( h <= arreglo . longitud / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int exterior = h ; exterior < matriz . longitud ; exterior ++ ) { int tmp = matriz [ exterior ] ; int interior = exterior ; while ( interno > h - 1 && matriz [ interna - h ] > tmp ) { matriz [ interna ] = matriz [ interna - h ] ; interno -= h ; } matriz [ interior ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Implementación en Python

def shell_sort ( datos : lista [ int ]) -> lista [ int ]: last_index = len ( datos ) step = len ( data ) // 2 while step > 0 : for i in range ( step , last_index , 1 ): j = i delta = j - paso while delta >= 0 y datos [ delta ] > datos [ j ]: datos [ delta ], datos [ j ] = datos [ j ], datos [ delta ] j = delta delta = j - paso paso //= 2 devolver datos

Notas

↑ Shell D. L. Un procedimiento de clasificación de alta velocidad // Commun . ACM - [Nueva York] : Asociación de Maquinaria de Computación , 1959. - Vol. 2, edición. 7.- Págs. 30-32. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/368370.368387
↑ J. Incerpi, R. Sedgewick , "Límites superiores mejorados para Shellsort", J. Computer and System Sciences 31, 2, 1985.
↑ Marcin Ciura Mejores incrementos para el caso promedio de Shellsort . Consultado el 15 de septiembre de 2009. Archivado desde el original el 30 de agosto de 2011. (indefinido)

Enlaces

D. Knut . El arte de programar. Volumen 3. Clasificación y búsqueda, 2ª ed. cap. 5.2.1. ISBN 5-8459-0082-4
Representación animada del algoritmo de clasificación Shell
Representación de baile del algoritmo de ordenación de Shell (video)

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
inserciones	inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento