+\layout Standard
+
+La técnica de Block Sorting
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+desde ahora lo llamaremos BS, para minimizar la notación.
+\end_inset
+
+ tiene su principal desventaja en que es un algoritmo que consume muchos
+ recursos, y para ser una solución práctica debe ser trabajada para dar
+ resultados coherentes.
+\layout Standard
+
+En una implementación simple, el BS debe crear una matriz y crear todos
+ los desplazamientos sobre ella.
+ Esto hace que se necesite
+\begin_inset Formula $O(n^{2})$
+\end_inset
+
+ en memoria, donde
+\begin_inset Formula $n$
+\end_inset
+
+ es la longitud del vector sobre el cual se quiere operar.
+ Claramente es un problema, ya que para una página pequeña, digamos 1kb,
+ se necesita una matriz de 1Mb.
+\layout Standard
+
+El otro problema es el tiempo de ordenamiento de los desplazamientos, que
+ debe ser lo menor posible.
+ Una posibilidad es utilizar un método de ordenamiento de bajo orden, como
+ el Quick Sort
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+Se ha optado por utilizar el qsort de la libc por ser ANSI-C y tener una
+ técnica de selección del pivot aceptable.
+\end_inset
+
+ utilizado en esta implementación.
+ Otra posible opción hubiera sido el Heap Sort, pero dada la complejidad
+ de su implementación no se creyó que diera una mejora factible y suficiente
+ apreciable como para implementarlo.
+\layout Standard
+
+Como última opción se estudió el Radix Sort, ya que justamente nuestro dato
+ a ordenar es de longitud fija
+\begin_inset Formula $n$
+\end_inset
+
+ y se cuenta con un conjunto de
+\begin_inset Formula $L=255$
+\end_inset
+
+ elementos posibles a aparecer en el dato.
+ El orden de éste método sería
+\begin_inset Formula $O(n*L)$
+\end_inset
+
+, pero para que realmente el Radix Sort sea efectivo, se requiere que
+\begin_inset Formula $255=L<log_{2}(n)=15$
+\end_inset
+
+, por lo que fue descartado.
+\layout Standard
+
+Para solucionar el problema del consumo de memoria se plateó un esquema
+ como el que se indica a continuación :
+\layout LyX-Code
+
+
+\layout LyX-Code
+
+
+\size small
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+\layout LyX-Code
+
+
+\size small
+Dato | | | | | | | | | | | | | | | | | | | | | | | | | |
+\layout LyX-Code
+
+
+\size small
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+\layout LyX-Code
+
+
+\size small
+ ^ ^ ^
+\layout LyX-Code
+
+
+\size small
+Desplazamientos | | |
+\layout LyX-Code
+
+
+\size small
+ +-+ | | |
+\layout LyX-Code
+
+
+\size small
+ | |---------+ | |
+\layout LyX-Code
+
+
+\size small
+ +-+ | |
+\layout LyX-Code
+
+
+\size small
+ | |-----------+ |
+\layout LyX-Code
+
+
+\size small
+ +-+ |
+\layout LyX-Code
+
+
+\size small
+
+\backslash
+/
+\backslash
+ |
+\layout LyX-Code
+
+
+\size small
+ +-+ |
+\layout LyX-Code
+
+
+\size small
+ | |---------------------------------------------------------+
+\layout LyX-Code
+
+
+\size small
+ +-+
+\layout Standard
+
+El vector desplazamiento es una estructura de control que almacena :
+\layout Itemize
+
+La posición inicial de la palabra desplazada i en el Dato
+\layout Itemize
+
+La posición final de la palabra desplazada en el Dato ( se calcula como
+ (pos_inicial+n-1)%n)
+\layout Standard
+
+La ganancia de este método es que se utilizan
+\begin_inset Formula $2*n$
+\end_inset
+
+ bytes de memoria solamente, es decir, que se bajó a O(n) el orden en memoria
+ del algoritmo.
+\layout Standard
+
+Luego de inicializar el vector Desplazamiento (esta parte es
+\begin_inset Formula $O(n)$
+\end_inset
+
+ en tiempo) se ordena el vector utilizando el qsort, que es del orden de
+
+\begin_inset Formula $O(n*log_{2}(n))$
+\end_inset
+
+
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+En realidad es del orden de O(1.44*n*log2(n)), para el caso promedio.
+\end_inset
+
+.
+ Y como último paso se obtiene la salida recurriendo el vector Desplazamiento
+ ordenado y emitiendo el último byte de cada posición.
+ Si se detecta la posición donde la posición inicial sea 0, se obtiene el
+ k para retornar.
+\layout Standard
+
+Se debe aclara que los órdenes estimados más arriba se basan en la suposición
+ de que el orden de una comparación en
+\begin_inset Formula $O(1)$
+\end_inset
+
+.
+ En el caso de tener que comprimir archivos donde los desplazamientos queden
+ iguales o solo cambien sobre el final, los órdenes se ven muy afectados.
+ Sin embargo, para el caso promedio no se comporta tan mal.
projects / z.facultad / 75.06 / jacu.git / blobdiff