Nombre de comparaisons utilisant le tri par fusion

Question

Si vous avez 5 nombres distincts, combien de comparaisons au maximum avez-vous besoin de trier en utilisant le tri par fusion?

Answer 1

Je trouve la question intéressante, donc je décidé d'explorer à fond (avec un peu d'expérimentation en Python). J'ai téléchargé mergesort.py depuis here et l'ai modifié pour ajouter un argument cmp pour une fonction de comparateur.Puis:

import collections 
import itertools 
import mergesort 
import sys 

class CountingComparator(object): 
    def __init__(self): 
    self.count = 0 
    def __call__(self, a, b): 
    self.count += 1 
    return cmp(a, b) 

ms_histo = collections.defaultdict(int) 

for perm in itertools.permutations(range(int(sys.argv[1]))): 
    cc = CountingComparator() 
    lperm = list(perm) 
    mergesort.mergesort(lperm, cmp=cc) 
    ms_histo[cc.count] += 1 

for c in sorted(ms_histo): 
    print "%d %2d" % (c, ms_histo[c]) 

L'histogramme simple, résultant (en commençant par une longueur de 4, comme je l'ai fait pour le développement et le débogage de ce) est:

4 8 
5 16 

Pour le problème affiché, avec une longueur de 5 au lieu de 4, je reçois:

5 4 
6 20 
7 48 
8 48 

et d'une longueur de 6 (et un format plus large ;-):

7 8 
8 56 
9 176 
10 288 
11 192 

Enfin, avec une longueur de 7 (et même le format plus large ;-):

9 16 
10 128 
11 480 
12 1216 
13 1920 
14 1280 

Sûrement une formule combinatoire parfaitement régulière se cache ici, mais je trouve qu'il est difficile d'évaluer ce qu'il pourrait être, que ce soit analytiquement ou en se penchant sur les chiffres. Quelqu'un a des suggestions?

Answer 2

Selon Wikipedia: Dans le pire des cas, fusion ne sorte une quantité de comparaisons égale ou légèrement inférieure à (n ⌈lg n⌉ - 2^⌈lg n⌉ + 1)

Answer 3

Lorsque la fusion -sorting deux listes de longueur L1 et L2, je suppose que le nombre le plus défavorable de comparaisons est L1 + L2-1.

• Initialement, vous avez cinq listes d'une longueur.
• Vous pouvez fusionner deux paires de listes avec 2 comparaisons, ce qui dans les listes de longueur et 2,2 1.
• Ensuite, vous pouvez fusionner une longue liste 2 et 1 avec au plus une autre 1 + 2-1 = 2 comparaisons, ce qui donne une liste de 2 et 3 longues.
• Enfin, vous fusionnez ces listes avec au plus 2 + 3-1 = 4 comparaisons.

Je suppose que la réponse est 8.

Cette séquence de nombres résultats dans ce qui précède: [2], [4], [1], [3], [5] -> [ 2,4], [1,3], [5] -> [2,4], [1,3,5] -> [1,2,3,4,5]

Édition:

Voici une implémentation Erlang naïve. Sur cette base, le nombre de comparaisons est de 5,6,7 ou 8 pour les permutations de 1..5.

-module(mergesort). 

-compile(export_all). 


test() -> 
    lists:sort([{sort(L),L} || L <- permutations()]). 

sort([]) -> {0, []}; 
sort([_] = L) -> {0, L}; 
sort(L) -> 
    {L1, L2} = lists:split(length(L) div 2, L), 
    {C1, SL1} = sort(L1), {C2, SL2} = sort(L2), 
    {C3, RL} = merge(SL1, SL2, [], 0), 
    {C1+C2+C3, RL}. 

merge([], L2, Merged, Comps) -> {Comps, Merged ++ L2}; 
merge(L1, [], Merged, Comps) -> {Comps, Merged ++ L1}; 
merge([H1|T1], [H2|_] = L2, Merged, Comps) when H1 < H2 -> merge(T1, L2, Merged ++[H1], Comps + 1); 
merge(L1, [H2|T2], Merged, Comps) -> merge(L1, T2, Merged ++[H2], Comps + 1). 


permutations() -> 
    L = lists:seq(1,5), 
    [[A,B,C,D,E] || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A =/= E, B =/= C, B =/= D, B =/= E, C =/= D, C =/= E, D =/= E]. 

Answer 4

Qu'est-ce qui vous empêche de coder une sorte de fusion, en gardant un compteur pour le nombre de comparaisons, et l'essayer sur toutes les permutations de [0,1,2,3,4]?

Answer 5

http://www.sorting-algorithms.com/

Answer 6

Pour seulement cinq numéros distincts pour trier, le nombre maximum de comparaisons, vous pouvez avoir est 8 et le nombre minimum de comparaisons est 7. Voici pourquoi: -

Supposons que le tableau est a, b, c, d, e

division récursive: a, b, c et d, e

division récursive: a, b et c & & d e

division récursive: a & b & c et d e &

Maintenant, la fusion qui nécessitera comparison-

un & b: une comparaison afin de former a, b

a, b & c: deux comparaisons afin de former a, b , c

d & e: une comparaison pour former d, e

a, b, c et d, e: quatre comparaisons dans le pire des cas ou trois comparaisons id d est le plus grand élément Ainsi, le nombre total de comparaisons sera de 8 dans le pire des cas et de 7 dans le meilleur des cas.