Tri d'un tableau presque trié (éléments mal placés par pas plus de k)

Question

J'ai été demandé à cette question d'entrevue récemment:

Vous êtes donné un tableau qui est presque triées, en ce que chacun des N éléments peuvent être égarés par pas plus de k des postes à partir du bon ordre de tri. Trouver un espace-temps d'algorithme efficace pour trier le tableau.

J'ai un O(N log k) solution comme suit.

Nous allons désigner arr[0..n) à la moyenne des éléments de la matrice à partir de l'index 0 (inclus) N (exclusif).

• Trier arr[0..2k)
  • Maintenant, nous savons que arr[0..k) sont dans leur dernière triés positions...
  • ...mais arr[k..2k) peut encore être égaré par k!
• Trier arr[k..3k)
  • Maintenant, nous savons que arr[k..2k) sont dans leur dernière triés positions...
  • ...mais arr[2k..3k) peut encore être égaré par k
• Trier arr[2k..4k)
• ....
• Jusqu'à ce que vous triez arr[ik..N), puis vous avez terminé!
  • Cette dernière étape peut être moins cher que les autres étapes lorsque vous avez moins de 2k éléments de gauche

Dans chaque étape, vous de tri à la plupart des 2k éléments O(k log k), mettre de côté au moins k éléments dans leur dernière triés à la fin de chaque étape. Il y a O(N/k) étapes, de sorte que la complexité globale est - O(N log k).

Mes questions sont les suivantes:

• Est - O(N log k) - elle optimale? Cela peut-il être amélioré?
• Pouvez-vous faire cela sans (partiellement) re-trier les mêmes éléments?

Answer 1

Comme Bob Sedgewick a montré dans son travail de thèse (et suivez-ons), le tri par insertion absolument écrase le "presque-tableau trié". Dans ce cas, votre asymptotique bonnes, mais si k < 12 je parie que le tri par insertion gagne à chaque fois. Je ne sais pas qu'il y a une bonne explication pour pourquoi le tri par insertion le fait si bien, mais le seraient dans un de Sedgewick de manuels de droit des Algorithmes (il a fait de nombreuses éditions pour les différentes langues).

• Je n'ai aucune idée si O(N log k) est optimale, mais plus au point, je n'ai pas vraiment de soins—si k est petit, c'est la constante des facteurs de la question, et si k est grand, vous pouvez ainsi trier le tableau.

• Le tri par Insertion sera clou ce problème sans re-trier les mêmes éléments.

Big-O de notation, c'est très bien pour l'algorithme de classe, mais dans le monde réel, les constantes de la matière. Il est trop facile de perdre de vue ce. (Et je dis cela comme un professeur qui a enseigné le Big-O notation!)

Answer 2

Depuis k est apparemment censé être assez petit, le tri par insertion est probablement la plus évidente et la plus généralement acceptée de l'algorithme.

Dans une le tri par insertion aléatoire sur des éléments, vous devez analyser par le biais de N éléments, et vous devez vous déplacer chacun une moyenne de N/2 positions, donnant ~N*N/2 total des opérations. Le "/2" constante est ignoré dans un big-O (ou similaire), la caractérisation, donnant O(N²) de la complexité.

Dans le cas où vous proposons, le nombre d'opérations est ~N*K/2 -- mais depuis k est une constante, l'ensemble de l' k/2 terme est ignoré dans un big-O de la caractérisation, de sorte que la complexité est O(N).

Answer 3

Votre solution est bonne si k est assez grand. Il n'y a pas de meilleure solution en termes de temps de la complexité; chaque élément peut être hors de l'endroit en k des lieux, ce qui signifie que vous devez apprendre log2 k de bits d'information pour le placer correctement, ce qui signifie que vous besoin de faire log2 k comparaisons au moins--il y a donc une complexité d'au moins O(N log k).

Cependant, comme d'autres l'ont souligné, si k est petite, les termes constants vont vous tuer. Utiliser quelque chose qui est très rapide par opération, comme le tri par insertion, dans ce cas.

Si tu voulais vraiment être optimale, vous mettriez les deux méthodes, et passer de l'un à l'autre selon l' k.