Что является лучшим способом для сортировки слиянием? рекурсивная функция или нерекурсивная? - PullRequest
Новая
       11

Что является лучшим способом для сортировки слиянием? рекурсивная функция или нерекурсивная?

1 голос
/ 19 апреля 2019

Я ищу сортировку слиянием и обнаружил два вида функций.

Сначала используется рекурсия, подобная этой. 

#include <stdio.h>

void merge(array, low, mid, high) {
    int temp[MAX];
    int i = low;
    int j = mid + 1;
    int k = low;

    while ((i <= mid) && (j <= high)) {
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }/*End of while*/

    while (i <= mid)
        temp[k++] = array[i++];

    while (j <= high)
        temp[k++] = array[j++];

    for (i = low; i <= high; i++)
        array[i] = temp[i];

}/*End of merge()*/

void merge_sort(int low, int high) {
    int mid;
    if (low != high) {
        mid = (low + high) / 2;
        merge_sort(low, mid);
        merge_sort(mid + 1, high);
        merge(low, mid, high);
    }
}/*End of merge_sort*/

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

Итак, я нашел другой способ сортировки слиянием без рекурсии: 

#include <stdio.h>

#define MAX 30

int main() {
    int arr[MAX], temp[MAX], i, j, k, n, size, l1, h1, l2, h2;

    printf("Enter the number of elements : ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        printf("Enter element %d : ", i + 1);
        scanf("%d", &arr[i]);
    }

    printf("Unsorted list is : ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    /* l1 lower bound of first pair and so on */
    for (size = 1; size < n; size = size * 2) {
        l1 = 0;
        k = 0;  /* Index for temp array */
        while (l1 + size < n) {
            h1 = l1 + size - 1;
            l2 = h1 + 1;
            h2 = l2 + size - 1;
            /* h2 exceeds the limlt of arr */
            if (h2 >= n) 
                h2 = n - 1;

            /* Merge the two pairs with lower limits l1 and l2 */
            i = l1;
            j = l2;

            while (i <= h1 && j <= h2) {
                if (arr[i] <= arr[j])
                    temp[k++] = arr[i++];
                else
                    temp[k++] = arr[j++];
            }

            while (i <= h1)
                temp[k++] = arr[i++];
            while (j <= h2)
                temp[k++] = arr[j++];

            /** Merging completed **/
            /*Take the next two pairs for merging */
            l1 = h2 + 1; 
        }/*End of while*/

        /*any pair left */
        for (i = l1; k < n; i++) 
            temp[k++] = arr[i];

        for (i = 0; i < n; i++)
            arr[i] = temp[i];

        printf("\nSize=%d \nElements are : ", size);
        for (i = 0; i < n; i++)
            printf("%d ", arr[i]);

    }/*End of for loop */

    printf("Sorted list is :\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    printf("\n");

    return 0;
}/*End of main()*/

Я думаю, что это лучше, чем использование рекурсии.Эта функция уменьшала рекурсию до серии циклов for и while!Конечно, они ведут себя по-разному.Я думаю, что рекурсивная функция не годится для компилятора.Я прав?

Ответы [ 3 ]

2 голосов
/ 19 апреля 2019

При условии оптимизированных реализаций, итеративная сортировка слиянием снизу вверх несколько быстрее, чем рекурсивная сортировка слиянием сверху вниз, поскольку она пропускает рекурсивную генерацию индексов. Для больших массивов дополнительные издержки сверху вниз относительно малы, O (log (n)), по сравнению с общим временем O (n log (n)), где в обоих случаях большая часть времени тратится на объединение, которое может быть одинаковыми как снизу вверх, так и сверху вниз. Сортировка сверху вниз слиянием использует пространство стека O (log (n)), в то время как оба используют рабочее пространство O (n). Тем не менее, почти все реализации библиотек стабильной сортировки представляют собой разновидность итеративной сортировки со слиянием снизу вверх, например, гибрид сортировки с вставкой и сортировки снизу вверх.

Ссылка на ответ, показывающая оптимизированную сортировку слиянием сверху вниз с использованием пары взаимно рекурсивных функций для управления направлением слияния во избежание копирования данных:

Реализация слияния медленная

Ссылка на ответ, которая включает быструю сортировку, сортировку с двухсторонним слиянием снизу вверх и сортировку с четырехсторонним восходящим слиянием:

Оптимизированная сортировка слиянием быстрее, чем быстрая сортировка

1 голос
/ 22 апреля 2019

Ваш код для рекурсивного подхода к сортировке слиянием имеет проблемы:

  • прототип для merge не имеет типов аргументов.
  • массив отсутствует в списке аргументов merge_sort
  • Передача high, поскольку индекс последнего элемента подвержен ошибкам и не допускает пустых массивов. Вместо этого вы должны передать индекс первому элементу за концом массива, так что high - low - это количество элементов в срезе для сортировки. Таким образом, первый вызов merge_sort может занять 0 и размер массива.
  • и расточительно, и некорректно выделять полный массив int temp[MAX]; для каждого рекурсивного вызова. Бесполезно, потому что размер может быть намного больше, чем нужно, что может привести к переполнению стека и неверно, если high - low + 1 больше, чем MAX, что приводит к записи за конец массива, вызывая неопределенное поведение.

Эта merge_sort функция будет вызывать себя рекурсивно не более log 2 (high - low) раз, каждый вызов выделяет временный локальный массив. Количество рекурсивных вызовов не является проблемой, только 30 на 1 миллиард записей, но локальные массивы есть! Если вы попытаетесь отсортировать большой массив, в стеке может не хватить места для копии этого массива, а тем более нескольких копий, что приведет к неопределенному поведению, скорее всего к аварийному завершению.

Обратите внимание, что итеративный подход, который вы нашли, имеет ту же проблему, что и temp[MAX] с автоматическим хранением.

Решение состоит в том, чтобы выделить временный массив из кучи вверху и передать его рекурсивной функции.

Вот улучшенная версия: 

#include <stdio.h>

static void merge(int *array, int *temp, int low, int mid, int high) {
    int i = low;
    int j = mid;
    int k = 0;

    while (i < mid && j < high) {
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }

    while (i < mid)
        temp[k++] = array[i++];

    while (j < high)
        temp[k++] = array[j++];

    for (i = low, k = 0; i < high; i++, k++)
        array[i] = temp[k];
}

static void merge_sort_aux(int *array, int *temp, int low, int high) {
    if (high - low > 1) {
        int mid = (low + high) / 2;
        merge_sort_aux(array, temp, low, mid);
        merge_sort_aux(array, temp, mid, high);
        merge(array, temp, low, mid, high);
    }
}

int merge_sort(int *array, int size) {
    if (size > 1) {
        int *temp = malloc(size * sizeof(*temp));
        if (temp == NULL)
            return -1;

        merge_sort_aux(array, temp, 0, size);
        free(temp);
    }
    return 0;
}

// call from main as merge_sort(arr, MAX)
1 голос
/ 19 апреля 2019

Вы несколько правы.Итеративная сортировка по принципу «снизу вверх» выполняется быстрее, чем рекурсивная сортировка по принципу «сверху вниз».Оба метода хороши для компилятора;) но рекурсивный метод требует больше времени для компиляции.

...