In liste liste tri

J'ai une liste d'objets (L1) et une autre liste d'entiers (L2) qui représente l'ordre dans lequel les objets devraient être. Pour des raisons qui ne sont pas importantes à ce problème, la seule opération qui Je suis autorisé à effectuer sur L1 estIn liste liste tri

L1.move(int fromIndex, int toIndex)

Je me demandais si quelqu'un pouvait me pointer vers un algorithme qui peut mettre les objets en L1 dans l'ordre spécifié par L2 en utilisant uniquement cette seule opération, ou un en place Trier.

Merci

Source

2010-11-04 Jon

Est-ce que le problème est de trouver un algorithme qui le fait en premier lieu, ou en trouver un aussi efficace? –

Il n'y a pas plus de 20 éléments dans la liste, donc je ne suis pas vraiment préoccupé par la vitesse. – Jon

L'élément est inséré avant N, si j'ai une liste d'objets a, b, c dans L1 et que j'appelle L1.move (2, 0) la nouvelle liste est c, a, b – Jon

Regardez ces: tri Bubble, tri peigne, tri de sélection, tri par insertion, HeapSort, trier Shell.

Source

2010-11-04 23:43:20

Yay! Type de peigne! (Presque personne ne l'utilise, ce qui est une honte: - /) En outre, la liste est légèrement réduite est un tri stable est nécessaire ... –

@ pst, ah, bon point sur la stabilité. –

Regardez here, j'ai posté une réponse à propos d'un moyen de réorganiser un tableau en utilisant O (1) espace supplémentaire. Je ne suis pas sûr que cela correspond exactement à la sémantique de move que vous avez, mais cela pourrait s'appliquer.

Source

2010-11-05 02:59:49

Répondre

Questions connexes