Количество сравнений с использованием сортировки слияния

Question

Если у вас есть 5 разных чисел, сколько сравнений вам нужно отсортировать, используя сортировку слияния?

Answer 1

Я считаю, вопрос интересный, поэтому я решил исследовать его тщательно (с небольшим количеством экспериментов в Python).

Я скачал mergesort.py с here и модифицировал его, чтобы добавить аргумент cmp для функции компаратора.Тогда:

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

В результате простой гистограммы (начиная с длиной 4, как я сделал для разработки и отладки этого) является:

4 8 
5 16 

Для задачи, как размещены, с длиной 5 вместо 4, я получаю:

5 4 
6 20 
7 48 
8 48 

и длиной 6 (и более широком формате ;-):

7 8 
8 56 
9 176 
10 288 
11 192 

Наконец, с длиной 7 (и даже более широкого формата ;-):

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

Конечно некоторые вполне регулярная комбинаторная формула таится здесь, но я найти его трудно оценить то, что это может быть, либо аналитически или путем подсчета чисел. У кого-нибудь есть предложения?

Answer 2

В соответствии с Wikipedia: В худшем случае, сортировка слиянием делает количество сравнений равно или немного меньше, чем (п ⌈lg n⌉ - 2^⌈lg n⌉ + 1)

Answer 3

Когда слияние -сортировать два списка длины L1 и L2, я полагаю, что наихудшее число сравнений L1 + L2-1.

• Первоначально у вас есть пять 1-длинных списков.
• Вы можете объединить две пары списков с 2 сравнений, в результате чего в списках длиной 2,2 и 1.
• Затем вы можете объединить 2 и 1 длинный список с не более чем еще 1 + 2-1 = 2 сравнения, что дает 2 и 3 длинный список.
• Наконец, вы объедините эти списки не более 2 + 3-1 = 4 сравнения.

Так что, полагаю, ответ 8.

Эта последовательность чисел результатов в приведенном выше: [2], [4], [1], [3], [5] -> [ 2,4], [1,3], [5] -> [2,4], [1,3,5] -> [1,2,3,4,5]

Редактировать:

Вот наивная реализация Эрланг. Исходя из этого, количество сравнений составляет 5,6,7 или 8 для перестановок 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

Что мешает вам кодирование сортировки слияния, сохраняя счетчик для числа сравнений в нем, и пытается его на все перестановки [0,1,2,3,4]?

Answer 5

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

Answer 6

Для всего пять различных чисел для сортировки, максимальное число сравнений вы можете иметь 8 и минимальное количество сравнений 7. Вот почему: -

Пусть массив а, Ь, с, d, е

делят рекурсивно: а, б, в, г, е

делят рекурсивно: а, б & в и г & й

делят рекурсивно: а & б & с и д е &

Теперь, слияние, которое потребует результате сравнения

& б: одно сравнение с образованием а, б

а, б & с: два сравнения с образованием, б , с

д & е: одно сравнение с образованием d, E

A, B, C и d, E: четыре сравнения в худшем случае или трех сравнений идентификатор д является самым большим элементом массива с образованием a, b, c, d, e

Таким образом, общее количество сравнений будет в худшем случае восемь, а семь - в лучшем случае.