Introducción
Ordenar una matriz es uno de los primeros problemas serios que se estudian en el curso clásico "Algoritmos y estructuras de datos" de la disciplina informática. En este sentido, las tareas de clasificación por escrito y las preguntas correspondientes se encuentran a menudo en entrevistas para el puesto de un desarrollador en prácticas o junior.
Formulación del problema
Tradicionalmente, vale la pena comenzar la presentación de soluciones al problema con su enunciado. Por lo general, la tarea de clasificación implica ordenar una serie de números enteros en orden ascendente. Pero de hecho, esto es una simplificación excesiva. Los algoritmos descritos en esta sección se pueden utilizar para ordenar una matriz de cualquier objeto entre los cuales se establece una relación de ordenación (es decir, para dos elementos cualesquiera podemos decir: el primero es mayor que el segundo, el segundo es mayor que el primero o son iguales). Puede ordenar tanto en orden ascendente como descendente. Usaremos la simplificación estándar.
Ordenación rápida
La última vez hablamos de un tipo un poco más complejo: el tipo de inserción. Hoy hablaremos de un algoritmo mucho más complejo: clasificación rápida (también llamada clasificación Hoare).
Descripción del algoritmo
El algoritmo de clasificación rápida es recursivo, por lo tanto, por simplicidad, el procedimiento tomará como entrada los límites de un segmento de matriz desde l inclusive hasta r no inclusive. Está claro que para ordenar la matriz completa, se debe pasar 0 como el parámetro l y n como r, donde, por tradición, n denota la longitud de la matriz.
El algoritmo de clasificación rápida se basa en el procedimiento de partición. La partición selecciona algún elemento de la matriz y reordena los elementos de la sección de la matriz para que la matriz se divida en 2 partes: el lado izquierdo contiene elementos que son menores que este elemento y el lado derecho contiene elementos que son mayores o iguales a este elemento. Este elemento separador se llama pivote .
Implementación de partición:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
El pivote en nuestro caso se elige al azar. Este algoritmo se llama aleatorio . De hecho, el pivote se puede seleccionar de varias formas: tomar un elemento aleatorio, o tomar el primer / último elemento de la sección, o seleccionarlo de alguna manera "inteligente". La elección del pivote es muy importante para la complejidad final del algoritmo de clasificación, pero hablaremos de eso más adelante. La complejidad del procedimiento de partición es O (n), donde n = r - l es la longitud de la sección.
Ahora usamos la partición para implementar la ordenación:
Implementación de partición:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
Un caso extremo: una matriz de un elemento tiene la propiedad de estar ordenada. Si la matriz es larga, usamos la partición y llamamos al procedimiento de forma recursiva en las dos mitades de la matriz.
Si revisa la clasificación escrita en el ejemplo de la matriz 1 2 2, notará que nunca terminará. ¿Por qué sucedió?
Al escribir la partición, asumimos que todos los elementos de la matriz deben ser únicos. De lo contrario, el valor de retorno de m será ly la recursividad nunca terminará, porque sort (l, m) llamará sort (l, l) y sort (l, m). Para resolver este problema, debe dividir la matriz no en 2 partes (<pivote y> = pivote), sino en 3 partes (<pivote, = pivote,> pivote) y llamar a la clasificación recursiva para la primera y la tercera parte.
Análisis
Propongo analizar este algoritmo.
La complejidad temporal del algoritmo se expresa mediante la fórmula: T (n) = n + T (a * n) + T ((1 - a) * n). Por lo tanto, cuando llamamos a ordenar una matriz de n elementos, se necesitan aproximadamente n operaciones para ejecutar la partición y ejecutarse a sí misma 2 veces con los parámetros a * ny (1 - a) * n, porque el pivote ha dividido el elemento en fracciones.
En el mejor de los casos, a = 1/2, es decir, el pivote divide el área en dos partes iguales cada vez. En este caso: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. El total será log (n) términos, porque los términos aparecen hasta que el argumento disminuye a 1. Como resultado, T (n) = O (n * log (n)).
En el peor de los casos, a = 1 / n, es decir, el pivote corta exactamente un elemento. La primera parte de la matriz contiene 1 elemento y la segunda contiene n - 1. Es decir: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = norte + O (1) + (norte - 1 + O (1) + T (norte - 2)) = O (norte ^ 2). El cuadrado aparece debido a que aparece en la fórmula para la suma de una progresión aritmética que aparece en el proceso de garabatear la fórmula.
En promedio, idealmente, se debe considerar la expectativa matemática de varias opciones. Se puede demostrar que si el pivote divide la matriz en la proporción 1: 9, entonces las asintóticas resultantes seguirán siendo O (n * log (n)).
La clasificación se llama rápida, porque la constante que se oculta debajo del signo O resulta ser bastante pequeña en la práctica, lo que llevó a un uso generalizado del algoritmo en la práctica.
Lee mas
