Anzahl der Vergleiche mit Mergesort

Question

Wenn Sie 5 verschiedene Zahlen haben, wie viele Vergleiche in den meisten brauchen Sie dies mit Mergesort sortieren?

Answer 1

ich die Frage interessant finden, so dass ich es gründlich zu erforschen entschieden (mit einem wenig Experimentieren in Python).

Ich heruntergeladen mergesort.py von hier und modifiziert es hinzufügen cmp Argument für eine Komparator-Funktion. Dann gilt:

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])

Das resultierende einfache Histogramm (mit einer Länge von 4 durch, da ich für die Entwicklung und das Debuggen dies tat) ist:

4  8
5 16

Für das Problem, wie geschrieben, mit einer Länge von 5 statt 4, erhalte ich:

5  4
6 20
7 48
8 48

und mit einer Länge von 6 (und ein breiteren Format; -):

7    8
8   56
9  176
10 288
11 192

Schließlich mit einer Länge von 7 (und noch breiterem Format; -):

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

Sicher einig vollkommen regelmäßig kombinatorische Formel lauert hier, aber ich finde es schwer zu beurteilen, was es sein könnte, entweder analytisch oder über die Zahlen brüten. Niemandes bekam Anregungen?

Answer 2

Was halten Sie davon ab Codieren einen Mergesort, einen Zähler für die Anzahl der Vergleiche darin zu halten, und es heraus auf allen Permutationen von [0,1,2,3,4] versuchen?

Answer 3

Wenn merge sortier zwei Listen der Länge L1 und L2, nehme ich an der schlimmste Fall Anzahl der Vergleiche ist L1 + L2-1.

• Am Anfang haben Sie fünf 1-lange Listen.
• Sie können mit zwei Paaren von Listen zusammenführen 2 Vergleiche , die sich in Listen der Länge 2,2 und 1.
• Dann können Sie eine 2 und 1 lange Liste verschmelzen mit höchstens noch 1 + 2-1 = 2 Vergleichen , eine 2 und 3 lange Liste ergeben.
• Schließlich fusionieren Sie diese Listen mit höchstens 2 + 3-1 = 4 Vergleiche .

Also ich denke, die Antwort ist 8.

Diese Zahlenfolge ergibt die oben: [2], [4], [1], [3], [5] -> [2,4], [1,3], [5] -> [2,4], [1,3,5 ] -> [1,2,3,4,5]

Edit:

Hier ist eine naive Erlang-Implementierung. Auf dieser Grundlage ist die Anzahl der Vergleiche 5,6,7 oder 8 für Permutationen von 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

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

Answer 5

Nach Wikipedia : Im schlimmsten Fall merge tut Art eine Menge die Vergleiche gleich oder etwas kleiner als (n ⌈lg n⌉ - 2 ^ ⌈lg n⌉ + 1)

Answer 6

Für nur fünf verschiedene Zahlen zu sortieren, die maximale Anzahl von Vergleichen Sie haben können, ist 8 und die minimale Anzahl von Vergleichen ist 7. Hier ist warum: -

Angenommen

das Array a, b, c, d, e

divide rekursiv: a, b, c und d, e

divide rekursiv: a, b und c und d & e

divide rekursiv: A & B & C und D & E

Nun, Verschmelzung, die einen Vergleich erfordern -

a & b: ein Vergleich eine bilden, b

a, b & c: zwei Vergleiche a, b, c

zu bilden

d & e: ein Vergleich zu Form d, e

a, b, c und d, e: vier Vergleich im schlimmsten Fall oder drei Vergleiche id d ist das größte Element des Arrays A, b, c, d zu bilden, e

Die Gesamtzahl der Vergleiche wird acht Also, im schlimmsten Fall und sieben im besten Fall.