对大整数排序时出现递归选择排序错误11

Question

我必须使用递归选择排序来对不同的整数数组进行排序。

这些数组分别由100、1000、10000、100000、200000、500000项组成，可以由有序数、偏序数、倒序数和随机数组成。在此之后，我必须计算算法对数组进行排序所用的时间。

我必须使用递归，这是一个家庭作业。

我创建了一个生成数组的函数：

typedef enum {ORINATO, INVERS, PARZ_ORDINATO, RANDOM} Ordine;

int *generaArray(int dimensione, Ordine ordine) {
int i, j, n;
int *array = (int*)malloc(dimensione * sizeof(int));

if (!array){
    return NULL;
}

switch (ordine){
    case ORINATO:
           for (i = 0; i < dimensione; i++){
            array[i] = i;  
        } break;

    case INVERS:
        n =0;
        for ( i = dimensione-1; i >= 0 ; i--) {
            array[i] = n;
            n++;
        }break;

    case PARZ_ORDINATO:
        for (i = 0; i < dimensione/2 ; i++) {
            array[i] = i;
        }
        for (j = i+1; j <dimensione; j++){
            n = rand();
            array[j] = n;
         };break;
    case RANDOM:
        for ( i = 0; i <= dimensione ; i++) {
            array[i] = rand();

        }break;
    
    default:
        break;
}
return array;
}

它的效果就像奇迹一样。

然后我创建了递归选择排序，如下所示：

void recursiveSelectionSort(int *array, int dim, int start){
int min=0;
if (start >= dim-1){
    return;
}
min = findMin(array, start, start+1, dim);
swap(&array[min], &array[start]);
recursiveSelectionSort(array, dim, start+1);
}

int findMin(int *array, int min, int start, int dim){
     if(start == dim ){
         return min;
     }
     if (array[start]< array[min]){
         min = start;
     }
    return findMin(array, min, start+1, dim);

}
void swap (int* x, int *y){
int temp = *x;
x =  *y;
y = *temp;
}

现在，这也应该是有效的，但显然有些东西是不起作用的。让我们做一个实现的例子，这是我放在我的main中的：

int main() {
    int *array;
    
    clock_t start, end;
    double t;

    array = generaArray(1000, ORINATO);

    start = clock();
    recursiveSelectionSort(array, 1000, 0);
    end = clock();
    t = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nIl tempo impiegato per 1000 elementi è: %lf secondi", t);
    return 0;
   }

这是有效的(但它更慢，因为它应该是这样的)。但是，如果您尝试将维度从1000更改为200000或500000，则会显示错误11。

是什么引起的呢？我什么都试过了，但似乎不管用。

Answer 1

对于初学者来说，为大型数组调用的递归函数可能会导致堆栈溢出。

因此，请使用非递归函数来实现大型数组的方法选择排序。

至于您的实现，例如，函数swap有拼写错误。

void swap (int* x, int *y){
int temp = *x;
x =  *y;
y = *temp;
}

我想你的意思是

void swap (int* x, int *y){
int temp = *x;
*x =  *y;
*y = temp;
}

所有其他函数都有太多的参数。

例如，可以按以下方式声明函数findMin

size_t findMin( const int *a, size_t n );

也可以定义为递归函数(如果您决定编写递归函数，那么这个函数也可以是递归的)

下面是一个演示程序，它展示了如何定义函数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap( int *x, int *y )
{
    int temp = *x;
    *x =  *y;
    *y = temp;
}

size_t findMin( const int a[], size_t n )
{
    if ( n < 2 )
    {
        return 0;
    }
    else
    {
        size_t i = findMin( a + 1, n - 1 ) + 1;
        return a[i] < a[0] ? i : 0;
    }
}

void recursiveSelectionSort( int a[], size_t n )
{
    if ( !( n < 2 ) )
    {
        size_t i = findMin( a + 1, n - 1 ) + 1;
        
        if ( a[i] < a[0] ) swap( &a[0], &a[i] );
        
        recursiveSelectionSort( a + 1, n - 1 );
    }
}

int main(void) 
{
    enum { N = 15 };
    int a[N];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % N;
    }

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    recursiveSelectionSort( a, N );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    return 0;
}

程序输出可能如下所示

11 9 3 5 6 8 2 4 5 3 7 9 2 0 14 
0 2 2 3 3 4 5 5 6 7 8 9 9 11 14