J'ai beaucoup lu récemment sur mergesort et je me demande s'il existe un moyen de faire un mergesort sans utiliser au moins un tableau supplémentaire. C'est possible?Implémenter un mergesort sans utiliser un tableau supplémentaire?
Répondre
Selon Wikipedia il est en effet possible, mais pourrait ne pas donner gain de performance:
Le tri sur place est possible (par exemple en utilisant des listes plutôt que des tableaux) mais est très compliqué et offrira peu de gains de performance en pratique, même si l'algorithme fonctionne en O (n log n). Dans ces cas, les algorithmes comme heapsort offrent généralement une vitesse comparable et sont beaucoup moins complexes. De plus, contrairement au tri par fusion standard, le tri par fusion sur place n'est pas un tri stable. Dans le cas de listes liées, l'algorithme n'utilise pas plus d'espace que celui déjà utilisé par la représentation de liste, mais le O (log (k)) utilisé pour la trace de récurrence. Certains soutiendraient que le tri d'une liste chaînée n'est pas en place car même si vous triez dans la structure de données donnée, la structure de données contient intrinsèquement des données supplémentaires que vous manipulez (par exemple, les liens dans la liste).
Non, vous aurez toujours besoin d'une structure de données supplémentaire pour fusionner les éléments triés. Sinon, vous écraserez simplement les choses que vous avez déjà triées.
Apparemment, c'est. This paper décrit un tri de fusion sur place:
Deux variantes en place de l'algorithme de fusion classique sont analysées en détail. La première variante directe effectue au plus N log 2 N + O (N) comparaisons et 3N log 2 N + O (N) se déplace pour trier N éléments. La seconde variante plus avancée nécessite au plus N log 2 N + O (N) comparaisons et "N log 2 N se déplace, pour tout fixe"? 0 et tout N? N (") En théorie, le second est supérieur aux versions avancées de heapsort.En pratique, en raison des frais généraux de la manipulation de l'index, notre fusion la plus rapide sur place se comporte toujours environ 50% plus lentement que l'ascendance ascendante . Cependant, nos implémentations sont pratiques par rapport aux algorithmes de mergesort basés sur en place la fusion.
Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola, "pratique in-place mergesort" (1996).
Ne vais pas résumer le papier ici, je ne l'ai pas lu. Mais j'ai ajouté dans le résumé et la référence, ce qui devrait aider à suivre les traces de liens morts. – Thomas
Voici l'implémentation Java
public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {
for (int i = 1; i <seed.length; i=i+i)
{
for (int j = 0; j < seed.length - i; j = j + i+i)
{
inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
}
}
}
public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) {
int left = low;
int right = mid + 1;
if(collection[mid].equals(collection[right])) {
return ;//Skip the merge if required
}
while (left <= mid && right <= high) {
// Select from left: no change, just advance left
if (collection[left].compareTo(collection[right]) <= 0) {
left ++;
} else { // Select from right: rotate [left..right] and correct
T tmp = collection[right]; // Will move to [left]
rotateRight(collection, left, right - left);
collection[left] = tmp;
// EVERYTHING has moved up by one
left ++; right ++; mid ++;
}
}
}
Voici le test unitaire
private Integer[] seed;
@Before
public void doBeforeEachTestCase() {
this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
ArrayUtils.<Integer>iterativeMergeSort(seed);
Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
assertThat(seed, equalTo(result));
}
- 1. Puis-je utiliser un comparateur sans implémenter comparable?
- 2. mergesort tableau d'int utilisant des pointeurs
- 3. Mergesort qui sauve la mémoire
- 4. Vérifiez si un tableau est vide sans utiliser de boucle?
- 5. Comment faire pour compresser un tableau Perl sans utiliser foreach?
- 6. Faire pivoter un tableau 2D sur place sans utiliser un nouveau tableau - la meilleure solution C++?
- 7. Comment implémenter l'opérateur [] pour un tableau dynamique?
- 8. trouver inorder successeur en BST sans utiliser d'espace supplémentaire
- 9. Rechercher un cadre pour implémenter un tableau de bord
- 10. Existe-t-il une fonction PHP pour implémenter un tableau associatif sans perdre les clés?
- 11. Mergesort pour easy68k
- 12. obtenir un tableau utiliser paramètres
- 13. formulaire PHP sans fichier supplémentaire
- 14. algorithme mergesort en C++
- 15. Pouvez-vous implémenter un accès par tableau paresseux dans QtScript?
- 16. Comment puis-je "implémenter" deux fois un tableau imbriqué?
- 17. mergesort nonrecursive en C++
- 18. mergesort C mise en œuvre
- 19. Comment remplacer NSString utiliser le tableau à un autre tableau
- 20. Possibilités de conserver un tableau de chaînes dans un flux sans utiliser la sérialisation?
- 21. Comment implémenter un programme d'exécution périodique 'sûr' sans utiliser les aides Rails?
- 22. Pourquoi utiliser un tableau pour implémenter une "liste" au lieu d'une table de hachage?
- 23. Ajouter un graphique supplémentaire à un UITableViewCell
- 24. Définir un double tableau sans taille fixe?
- 25. Actualiser ajouter un paramètre supplémentaire
- 26. Comment implémenter singleton sans utiliser statique/variable globale? Possible?
- 27. Comment implémenter la pagination en utilisant un tableau HTML?
- 28. Comment implémenter un tableau de bits dans C/Objective C
- 29. Supprimer des éléments d'une liste en cours d'itération sans utiliser de mémoire supplémentaire en Python
- 30. Temps d'exécution de Mergesort BigO
Pour mémoire, il est très difficile de prouver un négatif. –