Количество сравнений, использующих сортировку слиянием - PullRequest
Новая
       14

Количество сравнений, использующих сортировку слиянием

5 голосов
/ 04 октября 2009

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

Ответы [ 6 ]

6 голосов
/ 04 октября 2009

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

4 голосов
/ 05 октября 2009

Мне интересен этот вопрос, поэтому я решил тщательно его изучить (немного поэкспериментировав с Python).

Я скачал mergesort.py с здесь и изменил его, добавив аргумент 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

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

3 голосов
/ 04 октября 2009

При сортировке слиянием двух списков длины L1 и L2, я предполагаю, что худшее число сравнений - L1 + L2-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]

Изменить:

Вот наивная реализация Erlang. Исходя из этого, количество сравнений составляет 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].
2 голосов
/ 05 октября 2009
1 голос
/ 04 октября 2009

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

0 голосов
/ 09 февраля 2016

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

Предположим, что массив - это a, b, c, d, e

разделить рекурсивно: a, b, c и d, e

разделить рекурсивно: a, b & c и d & e

разделить рекурсивно: a & b & c и d & e

Теперь объединение, которое потребует сравнения, -

a & b: одно сравнение для формирования a, b

a, b & c: два сравнения для формирования a, b, c

d & e: одно сравнение с формой d, e

a, b, c и d, e: четыре сравнения в худшем случае или три сравнения id d - это самый большой элемент массива для формирования a, b, c, d, e

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

...