Quale sarebbe il tipo migliore da utilizzare su qualcosa con "blocchi" ordinati?

0

Immagina un mazzo ordinato di carte N tagliate K volte spostando le carte X dall'alto verso il basso (X è una quantità diversa / casuale ogni volta, X è sempre < N) - quale sarebbe il migliore modo di ordinare questo, sapendo che ci sono "pezzi" di carte ordinate?

Sto pensando qualcosa sulla falsariga di andare 1 per 1 fino a raggiungere uno che è fuori uso, e poi dividere quello che ho raggiunto come un "chunk", e poi continuare fino a che ho (K + 1?) pezzi e quindi ordinare i blocchi tramite un ordinamento standard, tuttavia non sono sicuro che questa sia la soluzione migliore, né esattamente come descrivere la sua complessità in termini di big-o

(per il big-o, penso che sarebbe N (chunking) + (k + 1) log (k + 1) per l'ordinamento - > k + 1 (log (k + 1)), ma Non sono sicuro)

    
posta user2813274 11.12.2014 - 21:20
fonte

1 risposta

2

Timsort , che combina l'unione e l'inserzione sort per fare esattamente ciò che descrivi. Utilizza le parti già ordinate della raccolta per velocizzare l'ordinamento.

In effetti è un ordinamento di tipo merge fino a quando non trova abbastanza "blocchi" da usare l'ordinamento per inserzione. Questo gli dà il caso peggiore e la complessità del tempo medio di O (nlogn), come l'ordinamento di unione di base. Ottiene l'O (n) miglior caso di ordinamento per inserimento.

È l'ordinamento predefinito per Python e un numero crescente di altre piattaforme.

    
risposta data 11.12.2014 - 21:31
fonte

Leggi altre domande sui tag