Algorytm optymalnego sortowania w liczbie zamian

Biorąc pod uwagę ciąg liczb, czy można go sortować za pomocą porównań i zamian / ruchów? Każdy wskaźnik do publikacji na ten temat lub kontrargumentów pokazujących dolną granicę byłby pomocny. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

cc.complexity-theory ds.algorithms

— Jesse Zixi Zhang
źródło

Każdy algorytm sortowania oparty na porównaniu będzie musiał wykonać porównania

i zamiany

w najgorszym przypadku (por. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

— Kaveh,

Trywialny, można osiągnąć

przenosi, jeżeli pierwszy rodzaj tabeli, która zawiera wskaźniki pierwiastków, a dopiero po tym rodzaju stołu, który zawiera elementy.

O (n)

$O(n)$

— Jukka Suomela,

@jukka cóż, to oszustwo, bo przesuwałeś elementy, gdy sortowałeś stół ...

— Jesse Zixi Zhang

Istnieje stabilny algorytm sortowania w miejscu z porównaniami i ruchami . $O(n \log n)$ $O(n)$

Zobacz: Gianni Franceschini: Sortowanie stabilne, na miejscu, z porównaniami i ruchami . Teoria Oblicz. Syst. 40 (4): 327-353 (2007) http://www.springerlink.com/content/d7348168624070v7/ $O(n \log n)$ $O(n)$

— Snowie
źródło