Algoritmo de classificação ideal em número de swaps

Dada uma sequência de números, ela pode ser classificada com comparações e swaps / movimentos? Qualquer ponteiro para publicações sobre esse assunto ou contra-argumentos mostrando um limite inferior ajudaria. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

cc.complexity-theory ds.algorithms Jesse Zixi Zhang
fonte

Qualquer algoritmo de classificação baseado em comparação precisará executar comparações e trocas no pior caso (cf. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Kaveh

Trivialmente, você pode realizar movimentos se primeiro classificar uma tabela que contém os índices dos elementos e somente depois classificar a tabela que contém os elementos.

O (n)

$O(n)$

Jukka Suomela 06/07

@jukka Bem, isso é batota coz você moveu elementos quando ordenados a mesa ...

Jesse Zixi Zhang

Respostas:

Existe um algoritmo de classificação no local estável com comparações e movimentos . $O(n \log n)$ $O(n)$

$O(n \log n)$ $O(n)$

Snowie
fonte