Не могу понять, как рекурсивно объединить сортировку - PullRequest
Новая
       109

Не могу понять, как рекурсивно объединить сортировку

0 голосов
/ 06 августа 2020

В настоящее время самообучающийся C ++ с использованием Даниэля Ляна «Введение в C ++».

На вершине c сортировки слияния, я не могу понять, как его код рекурсивно вызывает сам себя.

Я понимаю общую концепцию сортировки слиянием, но у меня проблемы с пониманием конкретно этого кода.

В этом примере мы сначала передаем список 1, 7, 3, 4, 9, 3, 3, 1, 2 и его размер (9) в функцию mergeSort. Оттуда мы разделим список на два, пока размер массива не достигнет 1. В этом случае мы получим: 1,7,3,4 -> 1,7 -> 1. Затем мы переходим к объединению, сортируя вторую половину. . В этом случае вторая половина массива будет 7. Мы объединяем два массива [1] и [7] и приступаем к удалению двух массивов, которые были динамически выделены для предотвращения утечки памяти.

Я не понимаю, как этот код запускается отсюда ? После удаления [] firstHalf и удаления [] secondHalf. Насколько я понимаю, не должен ли быть еще один вызов функции mergeSort, чтобы объединить сортировку новых firstHalf и secondHalf? 

#include <iostream>
using namespace std;

// Function prototype
void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length);

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[]);

// The function for sorting the numbers 
void mergeSort(int list[], int arraySize)
{
  if (arraySize > 1)
  {
    // Merge sort the first half
    int* firstHalf = new int[arraySize / 2];
    arraycopy(list, 0, firstHalf, 0, arraySize / 2);
    mergeSort(firstHalf, arraySize / 2);

    // Merge sort the second half
    int secondHalfLength = arraySize - arraySize / 2;
    int* secondHalf = new int[secondHalfLength];
    arraycopy(list, arraySize / 2, secondHalf, 0, secondHalfLength);
    mergeSort(secondHalf, secondHalfLength);

    // Merge firstHalf with secondHalf
    merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
      list);

    delete [] firstHalf;
    delete [] secondHalf;
  }
}

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[])
{
  int current1 = 0; // Current index in list1
  int current2 = 0; // Current index in list2
  int current3 = 0; // Current index in temp

  while (current1 < list1Size && current2 < list2Size)
  {
    if (list1[current1] < list2[current2])
      temp[current3++] = list1[current1++];
    else
      temp[current3++] = list2[current2++];
  }

  while (current1 < list1Size)
    temp[current3++] = list1[current1++];

  while (current2 < list2Size)
    temp[current3++] = list2[current2++];
}

void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length)
{
  for (int i = 0; i < length; i++)
  {
    target[i + targetStartIndex] = source[i + sourceStartIndex];
  }
}

int main()
{
  const int SIZE = 9;
  int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2};
  mergeSort(list, SIZE);
  for (int i = 0; i < SIZE; i++)
    cout << list[i] << " ";

  return 0;
}

1 Ответ

0 голосов
/ 07 августа 2020

Насколько я понимаю, не должен ли быть еще один вызов функции mergeSort для объединения сортировки новых firstHalf и secondHalf?

Это происходит неявно во время рекурсивного вызова. Когда вы дойдете до этих двух строк: 

delete [] firstHalf;
delete [] secondHalf;

Это означает, что один вызов mergeSort завершен. Если этот вызов относится к объединению первой половины, то код начинается со следующей строки, то есть с этих строк: 

// Merge sort the second half
int secondHalfLength = arraySize - arraySize / 2;
...

Но, если этот вызов принадлежит объединению второй половины, тогда управление возвращается к строка сразу после этого вызова, то есть эти строки: 

// Merge firstHalf with secondHalf
merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
  list);

И все, если все идет хорошо, как планировалось.

...