Qu'est-ce qu'un bon algorithme de tri dans des cas spéciaux?

13

J'ai un jeu de données qui est un certain nombre d'objets disposés dans une grille 2D. Je sais que j'ai un ordre strict, augmentant à mesure que vous avancez de gauche à droite dans chaque ligne, et augmentant de haut en bas dans chaque colonne. Par exemple,

  • 1 2 3
  • 4 6 7
  • 5 8 9

Puis-je améliorer le tri naïf pour trier l'ensemble de données de manière linéaire (tel que mesuré dans les comparaisons)?

Et pour les jeux de données nd? Ensembles de données arbitraires finis avec un sous-ensemble de comparaisons connues?

Zachary Vance
la source
1
Pouvez-vous poser une question plus précise? Votre premier paragraphe peut être lu pour impliquer que vos données sont déjà triées! Quelle est exactement votre entrée et quelle sortie souhaitez-vous?
Jacques Carette
1
Oui, la langue est un peu déroutante. Il m'a fallu un certain temps pour réaliser que l'ensemble de données se compose de n nombres à trier mais ces nombres sont disposés dans une grille sqrt (n) x sqrt (n) de telle sorte que chaque ligne et chaque colonne sont déjà triées. C'est ce que vous vouliez dire?
Oui, c'est ce que je voulais dire. Je vais modifier pour plus de clarté.
Zachary Vance

Réponses:

19

Il est facile de prouver une borne inférieure Ω (n 2 log n) sur ce problème (dans le modèle de tri par comparaison): si l'élément en position (i, j) est toujours à la distance 1/2 de i + j, alors la grille les diagonales sont indépendantes les unes des autres et l'ordre de tri dans chaque diagonale de la grille est arbitraire. Donc sous cette contrainte le nombre total de commandes possibles est le produit (sur toutes les diagonales de la grille) des factorielles des longueurs des diagonales, qui est exponentiel en n 2 log n.

Autrement dit, les algorithmes de tri par comparaison standard sont asymptotiquement optimaux pour les grilles ordonnées comme vous le décrivez.

David Eppstein
la source
L'autre réponse donne un algorithme explicite avec cette complexité, donc je considérerai ce problème résolu pour les grilles 2D et, sans vraiment vérifier, probablement pour les grilles de dimensions arbitraires.
Zachary Vance
4

Si je comprends bien le problème (et je ne peux pas, n'hésitez pas à me dire si je ne le fais pas) vous voulez transformer une grille 2D en un tableau 1D trié, alors que chaque ligne et colonne est déjà triée dans la grille 2D?

Dans ce cas, le premier élément de la liste doit être le coin supérieur gauche ((0,0), par définition du problème). Après cela, il doit s'agir de l'élément (1,0) ou (0,1), car tous les autres seront plus grands que ceux-ci par définition.

Vous pouvez généraliser en disant que le plus petit élément suivant de la grille est toujours directement sous un élément déjà utilisé (ou le bord de la grille), et également à droite d'un élément déjà utilisé (ou le bord de la grille), car les deux sont défini pour être plus petit que lui. Ainsi, à chaque itération, vous ne devez considérer que la plus petite valeur qui remplit cette exigence.

Vous pouvez conserver les candidats possibles dans l'ordre trié au fur et à mesure que vous les trouvez (pas plus de deux ne seront jamais disponibles en une seule itération), et à chaque itération, vérifiez les nouvelles valeurs mises à disposition (le cas échéant). S'ils sont inférieurs au plus bas des candidats précédents, ajoutez-les immédiatement à la liste et répétez, sinon ajoutez le plus bas candidat précédent et comparez-le au plus bas suivant, etc.

Malheureusement, je ne prétends pas être en mesure de fournir une complexité exacte de cela, ni je prétends que c'est la plus efficace possible, cela semble certainement mieux qu'une approche naïve, et j'espère que je l'ai suffisamment expliquée pour que vous puissiez comprendre.

EDIT: Pour les nd grilles comme celle-ci, je crois que le même principe de base s'applique, mais chaque itération rend jusqu'à n nouveaux candidats disponibles, et ces candidats doivent être les plus petits éléments inutilisés dans chacune des n dimensions à ce stade.

Paul
la source
En bref, vous pouvez faire une fusion sqrt (N) -way, comme dans mergesort? C'était ma meilleure méthode en cours d'exécution, mais elle se révèle être O (N log N) - Je n'ai pas de constante exacte là-bas, mais il y a au moins 0,5 pour log (sqrt (N)).
Zachary Vance