De hecho, además del indicador de desempeño, existen otras características, que a menudo no son menos importantes. Uno de ellos es la naturalidad . ¿Lo que es? La ordenación se llama natural si es más rápida cuando la matriz está casi ordenada. ¿Qué matriz se puede considerar "casi ordenada"? Aquí hay dos matrices de los mismos elementos:
{1,2,9,3,4,5,7,6,8,10} y {9,1,6,3,10,5,4,2, 8.7}
Incluso a simple vista puede ver que la primera matriz está más ordenada (solo 9 y 7 están "fuera de lugar"). Mientras que en la segunda matriz los números se mezclan al azar. ¿Cuál es la medida del orden? La respuesta es conocida: el número de inversiones. Un par de elementos A [i] y A [j] para j> i constituyen un inverso si A [j] <A [i]. (En esta nota, el propósito de la clasificación es siempre el orden ascendente).
Ahora podemos dar una definición precisa: la clasificación se llama natural si la velocidad de su operación disminuye con una disminución en el número de inversiones en la matriz original.
La naturalidad es una "fruta rara" en el mundo de la clasificación; por desgracia, ni QuickSort ni Shell tienen esta propiedad. Pero hay un algoritmo que, se podría decir, es completamente natural: es el tipo de inserción. Aunque este algoritmo es conocido por todas las personas cultas, permítanme repetir brevemente su esencia.
La matriz que se va a ordenar se escanea una vez desde el principio hasta el final. Tan pronto como se descubre que los elementos i-ésimo y (i-1) forman una inversión, el elemento i-ésimo se "arroja" hacia atrás (lo que se logra desplazando el segmento deseado del comienzo de la matriz hacia la derecha en una posición). A partir de esta descripción, queda claro que si hay pocas inversiones en la matriz, el algoritmo "volará" a través de la matriz muy rápidamente. Si no hay ninguna inversión, el algoritmo se completará en O (n) tiempo. Pero QuickSort en este caso será largo y tedioso para seleccionar un elemento de separación, dividir una matriz ya ordenada en segmentos, etc. Pero si hay muchas inversiones, la situación, por supuesto, será la opuesta: el rendimiento de la ordenación por inserción caerá a O (n ^ 2), y QuickSort será el campeón - O (n * log (n)).
Esta situación plantea una pregunta natural desde mi punto de vista: ¿cuántas inversiones superan la naturalidad y la ordenación por inserción funciona más rápido que QuickSort?
Para responder a esta pregunta, realicé una serie de experimentos computacionales. Su esencia era la siguiente. Se tomaron matrices de números enteros que iban desde 3000 a 30.000 elementos, se introdujeron una cierta cantidad de inversiones en ellas, luego las matrices se ordenaron por inserciones y clasificación rápida. Se midió el tiempo de clasificación (en tics del sistema). Para promediar, cada tipo se repitió 10 veces. Los resultados fueron los siguientes:
La imagen muestra la dependencia del tiempo de clasificación del número de inversiones introducidas. La serie de frambuesa es, por supuesto, QuickSort, y la serie azul es el tipo de inserción. Para un tamaño de matriz de 30 mil elementos, hasta aproximadamente 400 mil inversiones "ganancias naturales". Para arreglos menos ordenados, QuickSort ya es más beneficioso.
Y la siguiente imagen muestra la dependencia empírica del número crítico de inversiones en el tamaño de la matriz.
Es fácil ver que para una matriz de tamaño n, el número crítico de inversiones es aproximadamente 10 * n. Con más inversiones, QuickSort es beneficioso. Cabe señalar que el número máximo de inversiones para una matriz de longitud n es n * (n-1) / 2. El valor 10 * n es una parte muy insignificante de ellos. Lo cual no es de extrañar.
A lo dicho, queda agregar que los resultados de tales experimentos dependen de muchos factores (lenguaje de programación, el tipo de datos que se ordenan, etc.) Para ser honesto, fui demasiado vago para investigar estos temas con más detalle. Mis experimentos se realizaron en Microsoft Excel en un entorno VBA:
Probar código fuente
Private Declare Function GetTickCount Lib "kernel32" () As Long
':::
Sub JSort(A() As Long)
n& = UBound(A, 1)
For i& = 2 To n
If A(i&) < A(i& - 1) Then
j& = i& - 1
x& = A(i&)
Do While (A(j&) > x&)
A(j& + 1) = A(j&)
j& = j& - 1
If j& = 0 Then Exit Do
Loop
A(j& + 1) = x&
End If
Next i&
End Sub
':::
Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
If (e - b) <= 1 Then Exit Sub
i& = b
j& = e
w& = A((i& + j&) / 2)
Do While (i& < j&)
Do While (A(i&) < w&)
i& = i& + 1
Loop
Do While (A(j&) > w&)
j& = j& - 1
Loop
If i& < j& Then
tmp& = A(i&)
A(i&) = A(j&)
A(j&) = tmp&
i& = i& + 1
j& = j& - 1
End If
Loop
If j& > b Then QSort A, b, j&
If i& < e Then QSort A, i&, e
End Sub
'::: ( )
Sub InsInv(A() As Long, k As Long)
n& = UBound(A, 1)
For i& = 1 To k
Do
k1& = n& * Rnd
k2& = n& * Rnd
If (k1& <> k2&) And (k1& >= 1) And (k2& >= 1) Then Exit Do
Loop
tmp& = A(k1&)
A(k1&) = A(k2&)
A(k2&) = tmp&
Next i&
End Sub
':::
Function NumInv(A() As Long) As Long
n& = UBound(A, 1)
For i& = 1 To n& - 1
For j& = i& + 1 To n&
If A(j&) < A(i&) Then NumInv = NumInv + 1
Next j&
Next i&
End Function
':::
Sub Gtest_1()
Dim Eta() As Long
Dim Arr() As Long
Size& = CLng(InputBox("Sz="))
ReDim Eta(1 To Size&) As Long
ReDim Arr(1 To Size&) As Long
Randomize
For i& = 1 To Size&
Eta(i&) = i&
Next i&
q# = Size& * (Size& - 1) / 2
For iii% = 1 To 10
InsInv Eta, CLng(iii%)
ni# = CDbl(NumInv(Eta))
Cells(iii%, 1).Value = ni#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
JSort Arr
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
Next l%
Cells(iii%, 2).Value = S#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
QSort Arr, 1, Size&
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
If Not check(Arr) Then Exit Sub
Next l%
Cells(iii%, 3).Value = S#
DoEvents
Next iii%
MsgBox "OK"
End Sub
¡Gracias por la atención!
PD ¡
Y gracias a todos los que notaron mis errores! (Deletreo incorrecto de Timsort - en la primera edición había "TeamSort" y la "i" que faltaba en QuickSort). ¡Y si! - (especialmente para los perfeccionistas) QuickSort puede "degradar" a un rendimiento cuadrático. Pero en esta publicación estoy considerando no lo peor, sino el mejor caso de uso para QuickSort.