Сортировка слиянием, комп зависает

124

31 июля 2021, 02:50

Есть код для сортировки слиянием массива из n рандомных элементов. При n > 10000 комп просто зависает на 10 минут и никак на мои действия не реагирует. В чем может быть проблема?

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;
int n = 80000;
long *arr;

void mergeSort(int l, int h) {
    int mid = (h + l) / 2;
    if (l == h)
        return;
    if (h - l == 1) {
        if (arr[h] < arr[l])
            swap(arr[h], arr[l]);
        return;
    }
    mergeSort(l, mid);
    mergeSort(mid + 1, h);
    long *A = new long[n];
    int i, j, k;
    i = l;
    k = l;
    j = mid + 1;
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j]) {
            A[k] = arr[i];
            k++;
            i++;
        }
        else {
            A[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) {
        A[k] = arr[i];
        k++;
        i++;
    }
    while (j <= h) {
        A[k] = arr[j];
        k++;
        j++;
    }
    for (i = l; i < k; i++) {
        arr[i] = A[i];
    }
}
int main() {
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    srand(time(0));
    arr = new long[n];
    for (int i = 0; i < n; i++)
        arr[i] = rand();
    mergeSort(0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%ld ", arr[i]);
    cout << endl << "runtime = " << clock() / 1000.0 << endl;
    system("pause");
    delete[] arr;
    return 0;
}

Answer 1

Проблемы вашей рекурсии - экспоненциальный а не линейный рост числа операций и памяти. При n => 10000 представьте сколько операций нужно сделать чтобы это посчитать. А сколько выделить памяти?

Неправильное использование рекурсии может привести к переполнению стека и к огромным вычислительным затратам.

Если это учебное задание перепишите ваш код без рекурсии, что будет выполняться в n^1000 раз быстрее чем ваш код.

Через рекурсию:

/* C program for Merge Sort */
#include<stdlib.h> 
#include<stdio.h> 
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
    /* create temp arrays */
    int L[n1], R[n2]; 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 
        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
        merge(arr, l, m, r); 
    } 
} 
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
/* Driver program to test above functions */
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
    mergeSort(arr, 0, arr_size - 1); 
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 
}

Без рекурсии:

float a[50000000],b[50000000];
void mergesort (long num)
{
    int rght, wid, rend;
    int i,j,m,t;
    for (int k=1; k < num; k *= 2 ) {       
        for (int left=0; left+k < num; left += k*2 ) {
            rght = left + k;        
            rend = rght + k;
            if (rend > num) rend = num; 
            m = left; i = left; j = rght; 
            while (i < rght && j < rend) { 
                if (a[i] <= a[j]) {         
                    b[m] = a[i]; i++;
                } else {
                    b[m] = a[j]; j++;
                }
                m++;
            }
            while (i < rght) { 
                b[m]=a[i]; 
                i++; m++;
            }
            while (j < rend) { 
                b[m]=a[j]; 
                j++; m++;
            }
            for (m=left; m < rend; m++) { 
                a[m] = b[m]; 
            }
        }
    }
}

где a- вход и выход, б - временное хранилище