Na verdade, além do indicador de desempenho, existem outras características, muitas vezes igualmente importantes. Um deles é a naturalidade . O que é isso? A classificação é chamada de natural se for mais rápida quando a matriz está quase classificada. E qual array pode ser considerado "quase classificado"? Aqui estão duas matrizes dos mesmos elementos:
{1,2,9,3,4,5,7,6,8,10} e {9,1,6,3,10,5,4,2, 8,7}
Mesmo a olho nu, você pode ver que a primeira matriz está mais ordenada (apenas 9 e 7 estão "fora do lugar"). Enquanto na segunda matriz os números são misturados aleatoriamente. Qual é a medida de ordem? A resposta é conhecida - o número de inversões. Um par de elementos A [i] e A [j] para j> i constitui um inverso se A [j] <A [i]. (Nesta nota, o objetivo da classificação é sempre em ordem crescente.)
Agora podemos dar uma definição precisa: a classificação é chamada de natural se sua velocidade diminui quando o número de inversões na matriz original diminui.
A naturalidade é uma "fruta rara" no mundo da classificação - infelizmente, nem a classificação QuickSort nem a Shell têm essa propriedade. Mas existe um algoritmo que, pode-se dizer, é absolutamente natural - é o tipo de inserção. Embora esse algoritmo seja conhecido por todas as pessoas cultas, deixe-me repetir brevemente sua essência.
A matriz a ser classificada é verificada uma vez do início ao fim. Assim que for verificado que os elementos i-ésimo e (i-1) formam uma inversão, o i-ésimo elemento é "jogado" para trás (o que é conseguido deslocando o segmento desejado do início da matriz para a direita em uma posição). A partir dessa descrição, fica claro que, se houver poucas inversões na matriz, o algoritmo "voará" pela matriz muito rapidamente. Se não houver nenhuma inversão, o algoritmo será concluído no tempo O (n). Mas QuickSort, neste caso, será longo e tedioso para selecionar um elemento de separação, dividir uma matriz já ordenada em segmentos, etc. Mas se houver muitas inversões, a situação será, obviamente, a oposta: o desempenho da ordenação por inserção cairá para O (n ^ 2), e QuickSort será o campeão - O (n * log (n)).
Essa situação levanta uma questão natural do meu ponto de vista: quantas inversões superam a naturalidade e a classificação por inserção funciona mais rápido do que o QuickSort?
Para responder a essa pergunta, fiz uma série de experimentos computacionais. Sua essência era a seguinte. Pegamos arrays de inteiros variando em tamanho de 3.000 a 30.000 elementos, um certo número de inversões foi introduzido neles e, em seguida, os arrays foram classificados por inserções e classificação rápida. O tempo de classificação foi medido (em tiques do sistema). Para calcular a média, cada classificação foi repetida 10 vezes. Os resultados foram os seguintes:
A imagem mostra a dependência do tempo de classificação no número de inversões introduzidas. A série framboesa é, obviamente, QuickSort, e a série azul é tipo de inserção. Para um tamanho de array de 30 mil elementos, até cerca de 400 mil inversões "vitórias naturais". Para arrays menos ordenados, QuickSort já é mais benéfico.
E a próxima imagem mostra a dependência empírica do número crítico de inversões com o tamanho da matriz.
É fácil ver que, para uma matriz de tamanho n, o número crítico de inversões é de aproximadamente 10 * n. Com mais inversões, QuickSort é benéfico. Deve-se notar que o número máximo de inversões para uma matriz de comprimento n é n * (n-1) / 2. O valor 10 * n é uma parte muito insignificante deles. O que não é surpreendente.
Ao que foi dito, resta acrescentar que os resultados de tais experimentos dependem de muitos fatores (linguagem de programação, o tipo de dados sendo classificados, etc.) Para ser honesto, eu estava com preguiça de investigar essas questões em mais detalhes. Meus experimentos foram feitos no Microsoft Excel em ambiente VBA:
Código fonte de teste
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
Obrigado pela atenção!
PS
E obrigado a todos que notaram meus erros! (Grafia incorreta de Timsort - na primeira edição havia "TeamSort" e o "i" ausente no QuickSort). E sim! - (especialmente para perfeccionistas) QuickSort pode "degradar" o desempenho quadrático. Mas neste post estou considerando não o pior, mas o melhor caso de uso para QuickSort.