Search code examples
calgorithmrecursiondata-structuresquicksort

C Quicksort makes the program crash when ordering different kind of arrays

Overview:
I'm implementing a program that uses the quick sort algorithm to order different arrays which have different sizes and are ordered in different ways. Then I print out how long it took for each array to be ordered and how many exchanges and comparisons have been made. It's a homework and I need to know all of the different times, exchanges and comparisons.

What I tried
Reading articles online, I found out that it might be my compiler, it might use too few memory and it blocks the compiling process so I have to compile in release mode. The release mode gives me the same problems. I tried online compilers but none of em work.

How my program works

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

#define CINQUECENTO 500
#define MILLE 1000
#define DUEMILA 2000
#define CINQUEMILA 5000
#define DIECIMILA 10000
#define VENTIMILA 20000
#define CINQUANTAMILA 50000

typedef enum {ORINATO, INVERS, PARZ_ORDINATO, RANDOM} Ordine;
typedef enum{FIVEH, ONET, TWOT, FIVET, TENT, TWENTYT, FIFTYT} Dimensione;
int qconfronti=0, qscambi=0;

int *generaArray(int dimensione, Ordine ordine);
int perno(int* array, int primo, int ultimo);
void quickSort(int* array, int u, int v);
void calculateQuicktime(int *array, int dim);
void automaticQS();

int main(){
    
    automaticQS();

    return 0;
}

int *generaArray(int dimensione, Ordine ordine) {
    int i, j, n;
    int *array = 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;

            }
            printf("\n");break;
        case RANDOM:
            for ( i = 0; i <= dimensione ; i++) {
                array[i] = rand();

            }break;
        case ESCI:
            break;
        default:
            break;
    }
    return array;

}
int perno(int* array, int primo, int ultimo){
    int i=primo;
    int j=ultimo+1;
    int supp=0;
    int pivot=array[primo];

    while(i<j){
        do{
            i=i+1;
            qconfronti++;
        }while(array[i]<=pivot);

        do{
            j=j-1;
            qconfronti++;
        }while(array[j]>pivot);

        if(i<j){
            supp=array[i];
            array[i]=array[j];
            array[j]=supp;
            qscambi++;
        }
    }
    supp=array[primo];
    array[primo]=array[j];
    array[j]=supp;
    qscambi++;
    return j;
}

void quickSort(int* array, int u, int v){
    int q=0;
    if(u==v){
        return ;
    }
    q=perno(array, u, v);
    if(u<q){
        quickSort(array, u, q-1);
    }
    if(q<v){
        quickSort(array, q+1, v);
    }

}

void calculateQuicktime(int *array, int dim){
    clock_t start, end;
    double t;
    qconfronti = 0;
    qscambi = 0;
    start = clock();
    quickSort(array,0, dim);
    end = clock();
    t = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("\nConfronti: %d \t Scambi: %d", qconfronti, qscambi);
    printf("\nTempo impiegato per %d elementi : %lf secondi", dim, t);
}

void automaticQS() {
    printf("\nQuick Sort");

    printf("\n\nOrdinati:\n");
    calculateQuicktime(generaArray(CINQUECENTO, ORINATO), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, ORINATO), MILLE);
    calculateQuicktime(generaArray(DUEMILA, ORINATO), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, ORINATO), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, ORINATO), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, ORINATO), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, ORINATO), CINQUANTAMILA);

    printf("\n\nParzialmente ordinati:\n");
    calculateQuicktime(generaArray(CINQUECENTO, PARZ_ORDINATO), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, PARZ_ORDINATO), MILLE);
    calculateQuicktime(generaArray(DUEMILA, PARZ_ORDINATO), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, PARZ_ORDINATO), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, PARZ_ORDINATO), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, PARZ_ORDINATO), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, PARZ_ORDINATO), CINQUANTAMILA);

    printf("\n\nInversamente ordinati:\n");
    calculateQuicktime(generaArray(CINQUECENTO, INVERS), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, INVERS), MILLE);
    calculateQuicktime(generaArray(DUEMILA, INVERS), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, INVERS), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, INVERS), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, INVERS), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, INVERS), CINQUANTAMILA);

    printf("\n\nCasuali:\n");
    calculateQuicktime(generaArray(CINQUECENTO, RANDOM), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, RANDOM), MILLE);
    calculateQuicktime(generaArray(DUEMILA, RANDOM), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, RANDOM), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, RANDOM), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, RANDOM), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, RANDOM), CINQUANTAMILA);
}
  1. It generates an array which can have ordered numbers (0,1, 2, 3,4, 5...), partially ordered numbers (0,1,2,3,6,64,44...), inverted numbers (...6,5,4,3,2,1,0) and random numbers (42,64,2,7,53,25,1...);
  2. It quick sorts the various arrays;
  3. It prints out the stuff we need.

Question
Why is it that my program only prints out the ordered numbers array and then crashes giving me exit code 11?

Ps. I use CLion

Solution

  • You have a few bugs ...

    The bug you're currently experiencing ...

    In perno, although you have while (i < j), this does not prevent the do/while loop for i from going beyond the end of the array.

    The segfault occurs when primo is 500 and ultimo is 1000, but i will reach 333800.

    I added a fix to the i and j loops to stop when going out of bounds. This may or may not be the correct fix.

    After applying that fix and rerunning the program, you [seem to] recurse indefinitely. quickSort is called with v set to 1000, but u is recursively set to u + 1 (perhaps the pivot value is not set well).

    Eventually, you recurse infinitely with a u value of 0 and a v value of 1

    You return early from quickSort on if (u == v). That [probably] isn't a good enough test.

    I tried if ((v - u) < 2) instead.

    Now it [eventually] recurses infinitely with u==251 and v==455.

    This indicates that the if (u < q) and/or if (q < v) tests in quickSort are [probably] not adequate to prevent the infinite recursion.

    I added some assert calls there to [at least] abort early on the first such recursion.

    When you allocate an array with a dimension (e.g. 500), you allocate that many elements.

    But, passing this value to quickSort is incorrect. That's because the third quickSort argument is the index of the last element and not the length.

    So, in calculateQuicktime, you want:

    quickSort(array,0,dim - 1);

    Side note: calculateQuicktime does not call free on array, so you are leaking memory [I added a free call].

    Anyway, here's my [somewhat] refactored version of your code. I added debug printing with a dbgprt macro.

    But, I really found the above bugs mostly by running under gdb.

    Although this code is not a complete fix, it should give you some ideas:

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

#define CINQUECENTO 500
#define MILLE 1000
#define DUEMILA 2000
#define CINQUEMILA 5000
#define DIECIMILA 10000
#define VENTIMILA 20000
#define CINQUANTAMILA 50000

typedef enum { ORINATO, INVERS, PARZ_ORDINATO, RANDOM } Ordine;
typedef enum { FIVEH, ONET, TWOT, FIVET, TENT, TWENTYT, FIFTYT } Dimensione;
int qconfronti = 0,
    qscambi = 0;

int *generaArray(int dimensione, Ordine ordine);
int perno(int *array, int primo, int ultimo);
void quickSort(int *array, int u, int v);
void calculateQuicktime(int *array, int dim);
void automaticQS();

#ifdef DEBUG
#define dbgprt(_lvl,_fmt...) \
    do { \
        if (opt_d >= _lvl) \
            printf(_fmt); \
    } while (0)
#else
#define dbgprt(_fmt...) \
    do { \
    } while (0)
#endif

int opt_d;
int svlvl;

void
dbgpush(int newlvl)
{

    svlvl = opt_d;
    if (opt_d)
        opt_d = newlvl;
}

void
dbgpop(void)
{

    opt_d = svlvl;
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'd':
            opt_d = (*cp != 0) ? atoi(cp) : 1;
            break;
        }
    }

    setlinebuf(stdout);
    automaticQS();

    return 0;
}

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

    if (!array) {
        return NULL;
    }

    printf("generaArray: %d\n",dimensione);

    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;

        }
        printf("\n");
        break;
    case RANDOM:
        for (i = 0; i <= dimensione; i++) {
            array[i] = rand();

        }
        break;
#if 0
    case ESCI:
        break;
#endif
    default:
        break;
    }

    return array;
}

int
perno(int *array, int primo, int ultimo)
{
    int i = primo;
    int j = ultimo + 1;
    int supp = 0;
    int pivot = array[primo];

    dbgprt(1,"perno: ENTER primo=%d ultimo=%d pivot=%d\n",primo,ultimo,pivot);

    while (i < j) {
        dbgprt(2,"perno: OUTLOOP i=%d j=%d\n",i,j);

        do {
            i = i + 1;
#if FIX1
            if (i >= j)
                break;
#endif
            dbgprt(3,"perno: ILOOP i=%d array=%d\n",i,array[i]);
            qconfronti++;
        } while (array[i] <= pivot);

        do {
#if FIX1
            if (i >= j)
                break;
#endif
            j = j - 1;
            dbgprt(3,"perno: JLOOP j=%d array=%d\n",j,array[j]);
            qconfronti++;
        } while (array[j] > pivot);

        if (i < j) {
            dbgprt(2,"perno: SWAP\n");
            supp = array[i];
            array[i] = array[j];
            array[j] = supp;
            qscambi++;
        }
    }

    supp = array[primo];
    array[primo] = array[j];
    array[j] = supp;

    qscambi++;

    dbgprt(1,"perno: EXIT j=%d\n",j);

    return j;
}

void
quickSort(int *array, int u, int v)
{
    int q = 0;

    dbgprt(1,"quickSort: ENTER u=%d v=%d\n",u,v);

#if ! FIX2
    if (u == v) {
#else
    if ((v - u) < 2) {
#endif
        dbgprt(1,"quickSort: EXIT\n");
        return;
    }

    q = perno(array, u, v);

    if (u < q) {
        assert(! ((q - 1) == v));
        quickSort(array, u, q - 1);
    }
    if (q < v) {
        assert(! ((q + 1) == u));
        quickSort(array, q + 1, v);
    }

    dbgprt(1,"quickSort: EXIT\n");
}

void
calculateQuicktime(int *array, int dim)
{
    clock_t start,
     end;
    double t;

    qconfronti = 0;
    qscambi = 0;
    start = clock();
    quickSort(array, 0, dim - 1);
    end = clock();
    t = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("\nConfronti: %d \t Scambi: %d", qconfronti, qscambi);
    printf("\nTempo impiegato per %d elementi : %lf secondi", dim, t);

    // NOTE/BUG: array is never freed (i.e. a memory leak)
#if 1
    free(array);
#endif
}

void
automaticQS()
{
    printf("\nQuick Sort");

    printf("\n\nOrdinati:\n");
    dbgpush(2);
    calculateQuicktime(generaArray(CINQUECENTO, ORINATO), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, ORINATO), MILLE);
    calculateQuicktime(generaArray(DUEMILA, ORINATO), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, ORINATO), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, ORINATO), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, ORINATO), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, ORINATO), CINQUANTAMILA);
    dbgpop();

    dbgpush(3);
    printf("\n\nParzialmente ordinati:\n");
    calculateQuicktime(generaArray(CINQUECENTO, PARZ_ORDINATO), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, PARZ_ORDINATO), MILLE);
    calculateQuicktime(generaArray(DUEMILA, PARZ_ORDINATO), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, PARZ_ORDINATO), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, PARZ_ORDINATO), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, PARZ_ORDINATO), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, PARZ_ORDINATO), CINQUANTAMILA);
    dbgpop();

    printf("\n\nInversamente ordinati:\n");
    calculateQuicktime(generaArray(CINQUECENTO, INVERS), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, INVERS), MILLE);
    calculateQuicktime(generaArray(DUEMILA, INVERS), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, INVERS), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, INVERS), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, INVERS), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, INVERS), CINQUANTAMILA);

    printf("\n\nCasuali:\n");
    calculateQuicktime(generaArray(CINQUECENTO, RANDOM), CINQUECENTO);
    calculateQuicktime(generaArray(MILLE, RANDOM), MILLE);
    calculateQuicktime(generaArray(DUEMILA, RANDOM), DUEMILA);
    calculateQuicktime(generaArray(CINQUEMILA, RANDOM), CINQUEMILA);
    calculateQuicktime(generaArray(DIECIMILA, RANDOM), DIECIMILA);
    calculateQuicktime(generaArray(VENTIMILA, RANDOM), VENTIMILA);
    calculateQuicktime(generaArray(CINQUANTAMILA, RANDOM), CINQUANTAMILA);
}

    UPDATE:

    The above was done just with gdb but not desk checking your code against a working [Hoare] algorithm.

    So, using the wikipedia entry for quicksort: https://en.wikipedia.org/wiki/Quicksort a few more bug fixes ...

    In perno, the i loop was failing for two reasons:

    1. The initialization of i was int i = primo; instead of int i = primo - 1; This caused the loop to skip over [ignore] array[primo] as a candidate. See: ORIG3
    2. The i loop termination condition was while (array[i] <= pivot) instead of while (array[i] < pivot). See: ORIG5 Note that your j loop did not have this issue.

    With these fixes, the extra bounds checks I added in the i and j loops are no longer necessary (See: ORIG1).

    The reason that quickSort would recurse infinitely was the fact that the recursive call inside it was: quickSort(array,u,q-1); instead of quickSort(array,u,q); See: ORIG4

    I added a check in calculateQuicktime to check for the final array actually being sorted.

    With this check, some tests wouldn't crash [or recurse infinitely], but the final array would not be in sort.

    This was because my [attempted] fix of changing if (u == v) into if ((v - u) < 2 was incorrect. Your original code was correct. See: ORIG2

    Some additional stylistic suggestions:

    While using a #define for certain constants is a good idea (e.g. #define PI 3.14159), it's less readable for simple numbers (e.g. #define ONE 1 and #define TWO 2). So, I'd eliminate CINQUECENTO, etc.

    I'd replace this with a static/global array for the test lengths (e.g. testlen).

    And, even though they weren't used, the same goes for FIVEH, etc.

    And, the test code in automaticQS is cumbersome. Each section is replicating a fair amount of the code. By creating a helper function (e.g. testall), the test code can be greatly simplified.

    Anyway, here's the fully working code with all the additional changes:

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

#ifndef ORIG1
#define ORIG1   1
#endif

#ifndef ORIG2
#define ORIG2   1
#endif

#ifndef ORIG3
#define ORIG3   0
#endif

#ifndef ORIG4
#define ORIG4   0
#endif

#ifndef ORIG5
#define ORIG5   0
#endif

#if 0
#define CINQUECENTO 500
#define MILLE 1000
#define DUEMILA 2000
#define CINQUEMILA 5000
#define DIECIMILA 10000
#define VENTIMILA 20000
#define CINQUANTAMILA 50000
#else
int testlen[] = {
    500, 1000, 2000, 5000, 10000, 20000, 50000, -1
};
#endif

typedef enum { ORINATO, INVERS, PARZ_ORDINATO, RANDOM } Ordine;
#if 0
typedef enum { FIVEH, ONET, TWOT, FIVET, TENT, TWENTYT, FIFTYT } Dimensione;
#endif
int qconfronti = 0, qscambi = 0;

int *generaArray(int dimensione, Ordine ordine);
int perno(int *array, int primo, int ultimo);
void quickSort(int *array, int u, int v);
void calculateQuicktime(int *array, int dim);
void automaticQS();

#ifdef DEBUG
#define dbgprt(_lvl,_fmt...) \
    do { \
        if (opt_d >= _lvl) \
            printf(_fmt); \
    } while (0)
#else
#define dbgprt(_fmt...) \
    do { \
    } while (0)
#endif

int opt_d;
int svlvl;

void
dbgpush(int newlvl)
{

    svlvl = opt_d;
    if (opt_d)
        opt_d = newlvl;
}

void
dbgpop(void)
{

    opt_d = svlvl;
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'd':
            opt_d = (*cp != 0) ? atoi(cp) : 1;
            break;
        }
    }

    setlinebuf(stdout);
    automaticQS();

    return 0;
}

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

    if (array == NULL)
        return NULL;

    dbgprt(1,"generaArray: %d\n",dimensione);

    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;

        }
        printf("\n");
        break;

    case RANDOM:
        for (i = 0; i <= dimensione; i++)
            array[i] = rand();
        break;

#if 0
    case ESCI:
        break;
#endif

    default:
        break;
    }

    return array;
}

int
perno(int *array, int primo, int ultimo)
{
#if ORIG3
    int i = primo;
#else
    int i = primo - 1;
#endif
    int j = ultimo + 1;
    int supp = 0;
    int pivot = array[primo];

    dbgprt(1,"perno: ENTER primo=%d ultimo=%d pivot=%d\n",primo,ultimo,pivot);

    while (i < j) {
        dbgprt(2,"perno: OUTLOOP i=%d j=%d\n",i,j);

        do {
            i = i + 1;
#if (! ORIG1)
            if (i >= j)
                break;
#endif
            dbgprt(3,"perno: ILOOP i=%d array=%d\n",i,array[i]);
            qconfronti++;
#if ORIG5
        } while (array[i] <= pivot);
#else
        } while (array[i] < pivot);
#endif

        do {
#if (! ORIG1)
            if (i >= j)
                break;
#endif
            j = j - 1;
            dbgprt(3,"perno: JLOOP j=%d array=%d\n",j,array[j]);
            qconfronti++;
        } while (array[j] > pivot);

        if (i < j) {
            dbgprt(2,"perno: SWAP\n");
            supp = array[i];
            array[i] = array[j];
            array[j] = supp;
            qscambi++;
        }
    }

    supp = array[primo];
    array[primo] = array[j];
    array[j] = supp;

    qscambi++;

    dbgprt(1,"perno: EXIT j=%d\n",j);

    return j;
}

void
quickSort(int *array, int u, int v)
{
    int q = 0;

    dbgprt(1,"quickSort: ENTER u=%d v=%d\n",u,v);

#if ORIG2
    if (u == v) {
#else
    if ((v - u) < 2) {
#endif
        dbgprt(1,"quickSort: EXIT\n");
        return;
    }

    q = perno(array, u, v);

    if (u < q) {
        assert((q - 1) != v);
#if ORIG4
        quickSort(array, u, q - 1);
#else
        quickSort(array, u, q);
#endif
    }
    if (q < v) {
        assert((q + 1) != u);
        quickSort(array, q + 1, v);
    }

    dbgprt(1,"quickSort: EXIT\n");
}

void
calculateQuicktime(int *array, int dim)
{
    clock_t start, end;
    double t;

    qconfronti = 0;
    qscambi = 0;
    start = clock();
    quickSort(array, 0, dim - 1);
    end = clock();
    t = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Confronti: %d \t Scambi: %d\n", qconfronti, qscambi);
    printf("Tempo impiegato per %d elementi : %lf secondi\n", dim, t);

    // check array to ensure it's sorted
    int err = 0;
    int old = array[0];
    for (int idx = 1;  idx < dim;  ++idx) {
        int cur = array[idx];
        if (cur < old) {
            printf("calculateQuicktime: BADSORT idx=%d old=%d cur=%d\n",
                idx,old,cur);
            err = 1;
        }
        old = cur;
    }
    if (err)
        exit(1);

    // NOTE/BUG: array is never freed (i.e. a memory leak)
#if 1
    free(array);
#endif
}

void
testall(Ordine order,const char *reason)
{

    printf("\n\n%s:\n",reason);

    for (int *len = testlen;  *len >= 0;  ++len) {
        printf("\n");
        int *arr = generaArray(*len,order);
        calculateQuicktime(arr,*len);
    }
}

void
automaticQS()
{
    printf("\nQuick Sort");

    testall(ORINATO,"Ordinati");
    testall(PARZ_ORDINATO,"Parzialmente ordinati");
    testall(INVERS,"Inversamente ordinati");
    testall(RANDOM,"Casuali");
}