不同的C中的数组的大小 [英] Varying the size of an Array in C

问题描述

我已经写它生成一个随机数组，并同时使用插入和快速排序算法进行排序的程序。该方案还测量每个功能的运行时间。数组的大小是在preamble定义为一个参数化宏→。我的问题是：

  

我怎么能在一个单一的执行与测试各种大小的阵列都排序算法？

我想我的程序大小的数组排序 L = 10，100，1000，5000 和 10000 中一个执行。我的程序code详述如下。

的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆time.h中GT;//随机数组的长度
＃定义MAX 100
＃定义微升10无效naive_sort（INT []）;
无效smarter_sort（INT []，INT，INT）;
无效掉期（INT []，INT，INT）;
INT choose_piv（INT []，INT，INT）;诠释主（）{
    INT I，一个[L]，B [L];
    clock_t表示抽动，TOC;    //生成随机数的数组
    对于（i = 0; I＆LT; L，我++）
        一个由[i] =兰特（）％（MAX + 1）;    //定义b全等一个公平的比较
    对于（i = 0; I＆LT; L，我++）
        B〔Ⅰ〕=一个由[i];    //排序的数组
    的printf（\\ nUnsorted数组：）;
    对于（i = 0; I＆LT; L，我++）
            的printf（％d个，一个[我]）;    //插入排序（1E）
    TIC =时钟（）;
    naive_sort（一）;
    的printf（\\ nInsertion排序：）;
            对于（i = 0; I＆LT; L，我++）
                的printf（％d个，一个[我]）;
    TOC =时钟（）;
    的printf（（运行时间：％F秒）\\ n，（双）（TOC-TIC）/ CLOCKS_PER_SEC）;    //快速排序（1F）
    TIC =时钟（）;
    smarter_sort（二，0，L-1）;
    的printf（快速排序：）;
            对于（i = 0; I＆LT; L，我++）
                的printf（％D，B [I]）;
    TOC =时钟（）;
   的printf（（运行时间：％F秒）\\ n，（双）（TOC-TIC）/ CLOCKS_PER_SEC）;   返回0;
}无效naive_sort（int类型的[]）{
    INT I，J，T;
    对于（i = 1; I＆LT; L，我++）{
        T = A [];
        J = I-1;
        而（（T＆LT; A [J]）及及（J＆GT; = 0））{
            一[J + 1] = A [J]。
            j--;
        }
        一[J + 1] = T;
    }
}无效smarter_sort（int类型的[]，int类型l，INT R）{
    如果（R→1）{
        INT PIV = choose_piv（一，L，R）;
        smarter_sort（A，L，PIV-1）;
        smarter_sort（一，PIV + 1，r）的;
    }
}无效掉期（INT A []，INT I，诠释J）{
    诠释T = A [];
    一个由[i] = A [J]。
    一个研究[J] = T;
}INT choose_piv（int类型的[]，int类型l，INT R）{
    INT PL = L，公关= R;
    INT PIV = 1;
    而（PL＆LT; PR）{
        而（A [PL] LT; A [PIV]）
            PL ++;
        而（A [PR]＆gt;将[PIV]）
            pR--;
        如果（PL＆LT; PR）
            掉期（一，PL，PR）;
    }
    掉期（一，PIV，PR）;
    返回的pR;
}


我想AP preciate任何反馈。

---

编辑：我修改了code的建议，和它的工作为小值。但对于快速排序情况下 L = 100 并超越它，我没有得到任何输出：

和，你可以看到，为数不多的输出我得到的是零。什么是错的code？

/ *
 *任务1，问题^ h
 * /
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆time.h中GT;//随机数组的长度
＃定义MAX 100无效perf_routine（INT）;
无效naive_sort（INT []，int）;在
无效smarter_sort（INT []，INT，INT）;
无效掉期（INT []，INT，INT）;
INT choose_piv（INT []，INT，INT）;诠释主（）{
    perf_routine（10）;
    perf_routine（100）;
    perf_routine（1000）;
    perf_routine（5000）;
    perf_routine（10000）;
   返回0;
}无效perf_routine（INT L）{
    INT I，一个[L]，B [L];
        clock_t表示抽动，TOC;        的printf（长度％d个数组：\\ n，L）;        //生成随机数的数组
        对于（i = 0; I＆LT; L，我++）
            一个由[i] =兰特（）％（MAX + 1）;        //定义b全等一个公平的比较
        对于（i = 0; I＆LT; L，我++）
            B〔Ⅰ〕=一个由[i];        //插入排序（1E）
        TIC =时钟（）;
        naive_sort（A，L）;
        TOC =时钟（）;
        的printf（插入排序运行：％F秒的\\ n，（双）（TOC-TIC）/ CLOCKS_PER_SEC）;        //快速排序（1F）
        TIC =时钟（）;
        smarter_sort（二，0，L-1）;
        TOC =时钟（）;
       的printf（快速排序运行：％F秒\\ n，（双）（TOC-TIC）/ CLOCKS_PER_SEC）;
}无效naive_sort（int类型的[]，诠释L）{
    INT I，J，T;
    对于（i = 1; I＆LT; L，我++）{
        T = A [];
        J = I-1;
        而（（T＆LT; A [J]）及及（J＆GT; = 0））{
            一[J + 1] = A [J]。
            j--;
        }
        一[J + 1] = T;
    }
}无效smarter_sort（int类型的[]，int类型l，INT R）{
    如果（R→1）{
        INT PIV = choose_piv（一，L，R）;
        smarter_sort（A，L，PIV-1）;
        smarter_sort（一，PIV + 1，r）的;
    }
}无效掉期（INT A []，INT I，诠释J）{
    诠释T = A [];
    一个由[i] = A [J]。
    一个研究[J] = T;
}INT choose_piv（int类型的[]，int类型l，INT R）{
    INT PL = L，公关= R;
    INT PIV = 1;
    而（PL＆LT; PR）{
        而（A [PL] LT; A [PIV]）
            PL ++;
        而（A [PR]＆gt;将[PIV]）
            pR--;
        如果（PL＆LT; PR）
            掉期（一，PL，PR）;
    }
    掉期（一，PIV，PR）;
    返回的pR;
}


解决方案

当数组传递给函数，它们是作为（或衰变成），指向他们的第一个元素来传递。没有办法知道数组的大小。

因此​​，它是非常常见的通过实际长度作为附加参数的功能。与若跌破大小不同的三个阵列的天真之类的一个实例。

当然，必须注意保持同步阵列和长度。路过的长度过大可能会导致不确定的行为。例如，调用填写（微小，LARGE）在下面的例子中，可能会导致灾难。

（旁白：数组可以有一个最大长度或容量与实际长度例如，如果你想读了从文件十个数，你必须通过长度为10的数组，但如果有只有四个。数字阅读，你面对的两个额外的参数在这里：可能的数组长度，10和实际长度，4，这里不是这种情况，虽然）

那么，这里去。所有这三个阵列功能具有相同的签名：他们把一个数组，其长度

。

 的#include＆LT;＆stdlib.h中GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆time.h中GT;无效的排序（int类型的[]，为size_t LEN）
{
    为size_t I，J;    对于（i = 1; I＆LT; LEN，我++）{
        诠释T = A [];        J =  -  1;        而（J＆GT; = 0＆放大器;＆amp; T公司＆LT; A [J]）{
            一[J + 1] = A [J]。
            j--;
        }        一[J + 1] = T;
    }
}空隙填充（int类型的[]，为size_t LEN）
{
    为size_t我;    对于（i = 0; I＆LT; LEN，我++）{
        一个由[i] = RAND（）/（1.0 + RAND_MAX）* 100;
    }
}无效打印（int类型的[]，为size_t LEN）
{
    为size_t我;    对于（i = 0; I＆LT; LEN，我++）{
        如果（ⅰ）的printf（，）;
        的printf（％d个，一个[我]）;
    }    卖出期权（）;
}＃定义TINY 3
＃定义介质10
大的#define 15INT主要（无效）
{
    INT微小[TINY]
    INT中等[中];
    INT大[大];    函数srand（时间（NULL））;    填写（很小，很小）;
    填写（中型，中型）;
    补（大，大）;    打印（很小，很小）;
    打印（中型，中型）;
    打印（大，大）;    排序（很小，很小）;
    排序（中型，中型）;
    排序（大，大）;    打印（很小，很小）;
    打印（中型，中型）;
    打印（大，大）;    返回0;
}
 

I have written a program which generates a random array and sorts it by using both the insertion and quicksort algorithms. The program also measures the runtime of each function. The size of the array is defined in the preamble as a parameterised macro L. My question is:

How can I test both sorting algorithms with arrays of various sizes in a single execution?

I want my program to sort arrays of size L=10, 100, 1000, 5000 and 10000 in one execution. My program code is detailed below.

#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;
}

I would appreciate any feedback.

---

EDIT: I modified the code as suggested, and it worked for the small values. But for the quicksort case L=100 and beyond it, I don't get any output:

and as you can see, the few outputs I get are zero. What's wrong with the code?

/*
 * 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;
}

解决方案

When arrays are passed to functions, they are passed as (or "decay into") pointer to their first element. There is no way to know about the size of the array.

It is therefore very common to pass the actual length as additional parameter to the function. An example of your naive sort with three arrays of different size if below.

Of course, one must take care to keep the array and length in sync. Passing a length that is too big may result in undefined behaviour. For example, calling fill(tiny, LARGE) in the example below may result in disaster.

(Aside: An array may have a maximum length or capacity and an actual length. For example if you want to read up to ten numbers from a file, you must pass an array of length 10, but if there are only four numbers read, you are dealing with two additional parameters here: the possible array length, 10, and the actual length, 4. That's not the case here, though.)

Well, here goes. All three array functions have the same signature: They take an array and its length.

#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;
}

这篇关于不同的C中的数组的大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！