Изменение размера массива в C

Question

Я написал программу, которая генерирует случайный массив и сортирует его, используя алгоритмы вставки и быстрой сортировки. Программа также измеряет время выполнения каждой функции. Размер массива определяется в преамбуле как параметризованный макрос L. Мой вопрос:

Как я могу проверить оба алгоритма сортировки с массивами разных размеров за одно исполнение?

Я хочу, чтобы моя программа для сортировки массивов размером L=10, 100, 1000, 5000 и 10000 в одном исполнении. Мой код программы подробно описан ниже.

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

//Random Array Length 
#define MAX 100 
#define L 10 

void naive_sort(int[]); 
void smarter_sort(int[],int,int); 
void swap(int[],int,int); 
int choose_piv(int[],int,int); 

int main(){ 
    int i, a[L], b[L]; 
    clock_t tic, toc; 

    //Generate an array of random numbers 
    for(i=0; i<L; i++) 
     a[i]= rand() % (MAX+1); 

    //Define b identical to a for fair comparison 
    for(i=0; i<L; i++) 
     b[i]=a[i]; 

    //Unsorted Array 
    printf("\nUnsorted array: "); 
    for(i=0; i<L; i++) 
      printf("%d ", a[i]); 

    //Insertion Sort (1e) 
    tic = clock(); 
    naive_sort(a); 
    printf("\nInsertion Sort: "); 
      for(i=0; i<L; i++) 
       printf("%d ", a[i]); 
    toc = clock(); 
    printf(" (Runtime: %f seconds)\n", (double)(toc-tic)/CLOCKS_PER_SEC); 

    //Quicksort (1f) 
    tic = clock(); 
    smarter_sort(b,0,L-1); 
    printf("Quicksort:  "); 
      for(i=0; i<L; i++) 
       printf("%d ", b[i]); 
    toc = clock(); 
    printf(" (Runtime: %f seconds)\n", (double)(toc-tic)/CLOCKS_PER_SEC); 

    return 0; 
} 

void naive_sort(int a[]){ 
    int i, j, t; 
    for(i=1; i < L; i++){ 
     t=a[i]; 
     j=i-1; 
     while((t < a[j]) && (j >= 0)){ 
      a[j+1] = a[j]; 
      j--; 
     } 
     a[j+1]=t; 
    } 
} 

void smarter_sort(int a[], int l, int r){ 
    if(r > l){ 
     int piv = choose_piv(a, l, r); 
     smarter_sort(a, l, piv-1); 
     smarter_sort(a, piv+1, r); 
    } 
} 

void swap(int a[], int i, int j){ 
    int t=a[i]; 
    a[i]=a[j]; 
    a[j]=t; 
} 

int choose_piv(int a[], int l, int r){ 
    int pL = l, pR = r; 
    int piv = l; 
    while (pL < pR){ 
     while(a[pL] < a[piv]) 
      pL++; 
     while(a[pR] > a[piv]) 
      pR--; 
     if(pL < pR) 
      swap(a, pL, pR); 
    } 
    swap(a, piv, pR); 
    return pR; 
} 

Буду признателен за любые отзывы.

---

EDIT: Я изменил код, как предложено, и он работал для малых значений. Но для случая L=100 быстрой сортировки и за его пределами, я не получаю никакого вывода:

и, как вы можете видеть, несколько выходов, которые я получаю равны нулю. Что не так с кодом?

/* 
* Task 1, question h 
*/ 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

//Random Array Length 
#define MAX 100 

void perf_routine(int); 
void naive_sort(int[],int); 
void smarter_sort(int[],int,int); 
void swap(int[],int,int); 
int choose_piv(int[],int,int); 

int main(){ 
    perf_routine(10); 
    perf_routine(100); 
    perf_routine(1000); 
    perf_routine(5000); 
    perf_routine(10000); 
    return 0; 
} 

void perf_routine(int L){ 
    int i, a[L], b[L]; 
     clock_t tic, toc; 

     printf("Arrays of Length %d:\n", L); 

     //Generate an array of random numbers 
     for(i=0; i<L; i++) 
      a[i]= rand() % (MAX+1); 

     //Define b identical to a for fair comparison 
     for(i=0; i<L; i++) 
      b[i]=a[i]; 

     //Insertion Sort (1e) 
     tic = clock(); 
     naive_sort(a, L); 
     toc = clock(); 
     printf("Insertion Sort Runtime: %f seconds\n", (double)(toc-tic)/CLOCKS_PER_SEC); 

     //Quicksort (1f) 
     tic = clock(); 
     smarter_sort(b,0,L-1); 
     toc = clock(); 
     printf("Quicksort Runtime: %f seconds\n", (double)(toc-tic)/CLOCKS_PER_SEC); 
} 

void naive_sort(int a[], int L){ 
    int i, j, t; 
    for(i=1; i < L; i++){ 
     t=a[i]; 
     j=i-1; 
     while((t < a[j]) && (j >= 0)){ 
      a[j+1] = a[j]; 
      j--; 
     } 
     a[j+1]=t; 
    } 
} 

void smarter_sort(int a[], int l, int r){ 
    if(r > l){ 
     int piv = choose_piv(a, l, r); 
     smarter_sort(a, l, piv-1); 
     smarter_sort(a, piv+1, r); 
    } 
} 

void swap(int a[], int i, int j){ 
    int t=a[i]; 
    a[i]=a[j]; 
    a[j]=t; 
} 

int choose_piv(int a[], int l, int r){ 
    int pL = l, pR = r; 
    int piv = l; 
    while (pL < pR){ 
     while(a[pL] < a[piv]) 
      pL++; 
     while(a[pR] > a[piv]) 
      pR--; 
     if(pL < pR) 
      swap(a, pL, pR); 
    } 
    swap(a, piv, pR); 
    return pR; 
} 

Answer 1

Когда массивы передаются в функции, они передаются как (или «распадаются») на первый элемент. Нет никакого способа узнать размер массива.

Поэтому очень часто передавать фактическую длину в качестве дополнительного параметра функции. Пример вашей наивной сортировки с тремя массивами разного размера, если ниже.

Конечно, необходимо следить за тем, чтобы массив и длина синхронизировались. Передача слишком большой длины может привести к неопределенному поведению. Например, вызов fill(tiny, LARGE) в приведенном ниже примере может привести к катастрофе.

(Кроме того: массив может иметь максимальную длину или емкость и фактическую длину. Например, если вы хотите прочитать до десяти чисел из файла, вы должны передать массив длиной 10, но если есть только четыре числа читаются, вы имеете дело с двумя дополнительными параметрами здесь: возможная длина массива, 10 и фактическая длина, 4. Однако здесь дело не в этом.)

Ну, вот и все. Все три функции массива имеют одну и ту же подпись: они берут массив и его длину.

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

void sort(int a[], size_t len) 
{ 
    size_t i, j; 

    for (i = 1; i < len; i++) { 
     int t = a[i]; 

     j = i - 1; 

     while (j >= 0 && t < a[j]) { 
      a[j + 1] = a[j]; 
      j--; 
     } 

     a[j + 1] = t; 
    } 
} 

void fill(int a[], size_t len) 
{ 
    size_t i; 

    for (i = 0; i < len; i++) { 
     a[i] = rand()/(1.0 + RAND_MAX) * 100; 
    } 
} 

void print(int a[], size_t len) 
{ 
    size_t i; 

    for (i = 0; i < len; i++) { 
     if (i) printf(", "); 
     printf("%d", a[i]); 
    } 

    puts(""); 
} 

#define TINY 3 
#define MEDIUM 10 
#define LARGE 15 

int main(void) 
{ 
    int tiny[TINY]; 
    int medium[MEDIUM]; 
    int large[LARGE]; 

    srand(time(NULL)); 

    fill(tiny, TINY); 
    fill(medium, MEDIUM); 
    fill(large, LARGE); 

    print(tiny, TINY); 
    print(medium, MEDIUM); 
    print(large, LARGE); 

    sort(tiny, TINY); 
    sort(medium, MEDIUM); 
    sort(large, LARGE); 

    print(tiny, TINY); 
    print(medium, MEDIUM); 
    print(large, LARGE); 

    return 0; 
} 

Answer 2

Я бы, в каждой функции дает длину массива в параметрах и убедитесь, что вы не пытаетесь достичь элемента за пределами массива, например, замена станет:

int swap(int *a, int length, int i, int j) 
{ 
    if(i>=length || j>=length) 
     return -1; 
    int t=a[i]; 
    a[i]=a[j]; 
    a[j]=t; 
    return 0; 
} 

Также обратите внимание, что возврат -1 или 0 указывает на сбой. Примените это к остальной части кода, и у вас будет что-то, что можно применить к любому массиву.