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

Question

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

Из задания:

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

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

Я не прошу код, но любой psuedocode был бы очень полезен.

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

Спасибо!

Answer 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, который я вам написал)

Answer 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;
}

Answer 3

Вот 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 ++;
        }
    }       
}

Вот модульный тест 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));  
}

Answer 4

Вот C # версия восходящего слияния (некоторые подробности вы можете найти в моем блоге @ http://dream -er.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);
            }
        }