Подтвердить что ты не робот

Нерекурсивная сортировка слияния с двумя вложенными циклами - как?

Первый вопрос здесь, и да, это вопрос домашней работы. Нам поручено выполнить сортировку слияния в массиве (с которым я знаком), но в некотором роде я не уверен, как это сделать. Обычно у меня была бы отдельная функция сортировки слияния и слияния, а также использование двух. Однако, похоже, он хочет все в одном методе? Я просто надеялся, что, может быть, кто-то может помочь мне разобраться в чем-то или использовать их в терминах, которые я могу лучше понять.

Из задания:

вам потребуется реализовать нерекурсивную версию слияния-сортировки алгоритм. Устройте два вложенных цикла для выполнения этой задачи. Внешний цикл должен обеспечивать размер сегментов для слияния. Внутренняя петля должен заботиться о выборе позиций сегментов. Внутренняя петля должен начинаться с левого края и перемещать сегменты вправо. Расположите соответствующие значения переменных слева, в середине, вправо, чтобы сортировка выполняется только путем повторения вызова слияния (а, левый, средний, справа).

Я ненавижу быть таким расплывчатым, но я действительно не понимаю, что он говорит. Во-первых, что означает "внешний цикл должен обеспечивать размер сегментов"? Как цикл обеспечивает что-нибудь? Как насчет следующего предложения - что он имеет в виду по сегментам? Данные?

Я не прошу код, но любой psuedocode будет действительно полезен.

Если бы кто-нибудь мог попробовать и расшифровать то, что он имеет в виду, я был бы признателен. Я уже отправил ему по электронной почте об этом, но прошло несколько часов, и я еще не слышал.

Спасибо!

4b9b3361

ОТВЕТЫ

Ответ 1

Это не так сложно. Рассмотрим рекурсивное слияние:

       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
            /     \               split
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
      /   \         /  \          split
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
  / \     / \     / \     / \     split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

Если вы заметите, что когда вы разделитесь, вы на самом деле ничего не делаете. Вы просто говорите рекурсивной функции, чтобы частично отсортировать массив. Сортировка массива состоит из первой сортировки обеих половин, а затем слияния. Итак, в основном, что у вас есть:

+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

Теперь отсюда должно быть очевидно. Сначала вы объединяете элементы массива 2 на 2, затем 4 на 4, затем 8 на 8 и т.д. Это внешний for дает вам 2, 4, 8, 16, 32,... (это то, что он вызывает размер сегмента, так как i цикла содержит это число), а внутренний for (скажем, с итератором j) перебирает массив, i на i слияние array[j...j+i/2-1] с array[j+i/2..j+i-1].

Я бы не написал код, так как это домашнее задание.

Изменить: изображение того, как работает for

Представьте, что если i равно 4, значит, вы находитесь на этом этапе:

  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+

у вас будет for, который дает вам 0 (который 0*i) как j, а затем 4 (который 1*i) как j. (если i равно 2, вы бы имели j, как 0, 2, 4, 6)

Теперь, когда вам нужно объединить array[0..1] с array[2..3] (который сформулирован array[j..j+i/2-1] и array[j+i/2..j+i-1] с j = 0), а затем array[4..5] с array[6..7] (который сформулирован тем же формулы array[j...j+i/2-1] и array[j+i/2..j+i-1], потому что теперь j = 4) То есть:

i = 4:
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
        ^ ^ ^ ^ ^ ^ ^ ^
        | | | | | | | |
       / / / /   \ \ \ \
     (j  =  0)   (j  =  4)
      | | | |     | | | |
      j | | |     j | | |
      | | | j+i-1 | | | j+i-1
      | | j+i/2   | | j+i/2
      | j+i/2-1   | j+i/2-1
      | | | |     | | | |
      | | | |     | | | |
      \ / \ /     \ / \ /
       v   v       v   v
       merge       merge

Надеюсь, это по крайней мере понятно.

Боковая помощь: Просто подсказка, если вы действительно не знаете, как работает for:

for (statement1; condition; statement2)
{
    // processing
}

похож на запись

statement1;
while (condition)
{
    // processing
    statement2;
}

Итак, если вы всегда писали

for (int i = 0; i < 10; ++i)

это означало, начиная с 0, а i меньше 10, сделать что-то с i, а затем увеличить его. Теперь, если вы хотите, чтобы i изменился по-другому, вы просто изменяете statement2, например:

for (int i = 1; i < 1024; i *= 2)

(Попробуйте понять, как работает этот окончательный for на основе его эквивалента while, который я написал вам)

Ответ 2

Здесь моя ленивая, итеративная/восходящая реализация слияния, использующая std::merge:

template<class InIt, class OutIt>
OutIt mergesort(InIt begin, InIt const end, OutIt o /* auxiliary buffer */)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        {
            o = std::merge(o - n * 2, o - n, o - n, o, begin - n * 2);
            o = std::swap_ranges(begin - n * 2, begin, o - n * 2);
        }
        *o = *begin;
        ++o;
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            o = std::merge(o - (m + n), o - m, o - m, o, o - (m + n));
            o = std::swap_ranges(begin - (m + n), begin, o - (m + n));
            m += n;
        }
    }
    return o;
}

Здесь версия на месте, использующая std::inplace_merge:

template<class InIt>
InIt inplace_mergesort(InIt begin, InIt const end)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        { std::inplace_merge(begin - n * 2, begin - n, begin); }
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            std::inplace_merge(begin - (m + n), begin - m, begin);
            m += n;
        }
    }
    return begin;
}

Ответ 3

Вот версия С# снизу вверх-mergesort (для получения более подробной информации вы можете обратиться к моему блогу @http://dream-e-r.blogspot.com/2014/07/mergesort-arrays-and-lists.html)

void BottomUpMergesort(int[] a)
        {
            int[] temp = new int[a.Length];
            for (int runWidth = 1; runWidth < a.Length; runWidth = 2 * runWidth)
            {
                for (int eachRunStart = 0; eachRunStart < a.Length; 
                    eachRunStart = eachRunStart + 2 * runWidth)
                {
                    int start = eachRunStart;
                    int mid = eachRunStart + (runWidth - 1);
                    if(mid >= a.Length)
                    {
                        mid = a.Length - 1;
                    }
                    int end = eachRunStart + ((2 * runWidth) - 1);
                    if(end >= a.Length)
                    {
                        end = a.Length - 1;
                    }

                    this.Merge(a, start, mid, end, temp);
                }
                for (int i = 0; i < a.Length; i++)
                {
                    a[i] = temp[i];
                }
            }

И слияние определяется как:

void Merge(int[] a, int start, int mid, int end, int[] temp)
        {
            int i = start, j = mid+1, k = start;
            while((i<=mid) && (j<=end))
            {
                if(a[i] <= a[j])
                {
                    temp[k] = a[i];
                    i++;
                }
                else
                {
                    temp[k] = a[j];
                    j++;
                }
                k++;
            }
            while(i<=mid)
            {
                temp[k] = a[i];
                i++;
                k++;
            }
            while (j <= end)
            {
                temp[k] = a[j];
                j++;
                k++;
            }
            Assert.IsTrue(k == end+1);
            Assert.IsTrue(i == mid+1);
            Assert.IsTrue(j == end+1);
        }

        }

Только для справки: TopDownMergesort:

void TopDownMergesort(int[] a, int[] temp, int start, int end)
        {
            if(start==end)
            {
                //run size of '1'
                return;
            }
            int mid = (start + end) / 2;
            this.TopDownMergesort(a, temp, start, mid);
            this.TopDownMergesort(a, temp, mid + 1, end);
            this.Merge(a, start, mid, end, temp);
            for(int i = start;i<=end;i++)
            {
                a[i] = temp[i];
            }
        }

UnitTests

[TestMethod]
        public void BottomUpMergesortTests()
        {
            int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
            this.BottomUpMergesort(a);
            int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
            Assert.IsTrue(a.Length == b.Length);
            for (int i = 0; i < a.Length; i++)
            {
                Assert.IsTrue(a[i] == b[i]);
            }
            List<int> l = new List<int>();
            for (int i = 10; i >= 1; i--)
            {
                l.Add(i);
            }
            var la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= 10; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
            l.Clear();
            for (int i = 16; i >= 1; i--)
            {
                l.Add(i);
            }
            la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= l.Count; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
        }

Ответ 4

Вот реализация 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 ++;
        }
    }       
}

Вот Unit Test  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));  
}