Algoritma sortir optimal dalam jumlah swap

Diberikan urutan angka, dapatkah itu diurutkan dengan perbandingan dan swap / gerakan? Setiap penunjuk ke publikasi tentang hal itu atau tandingan yang menunjukkan batas bawah akan membantu. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

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

Algoritma pemilahan berdasarkan perbandingan apa pun perlu melakukan perbandingan

dan

bertukar dalam kasus terburuk (lih. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Kaveh

Secara sepele, Anda bisa mencapai

bergerak jika Anda pertama kali mengurutkan tabel yang berisi indeks elemen, dan hanya setelah itu mengurutkan tabel yang berisi elemen.

O (n)

$O(n)$

Jukka Suomela

@ jukka yah itu curang karena kamu memindahkan elemen ketika kamu mengurutkan tabel ...

Jesse Zixi Zhang

Jawaban:

Ada algoritma sorting in-place yang stabil dengan perbandingan dan gerakan . $O(n \log n)$ $O(n)$

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

Snowie
sumber