Thread: Problems implementing quicksort function

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    5

    Problems implementing quicksort function

    Below is the file I'm using. The sorting algorithm is from numerical recipes. http://www.library.cornell.edu/nr/bookcpdf/c8-2.pdf

    In the file there are 2 arrays, mol_nr and time. Now I want to sort the time array from low to high and the mol_nr array must change in the same way. An example can indeed be found in numerical recipes and i have place it in the file.

    Now the thing does not run. I get the following error:
    1 C:\Dev-Cpp\include\nrutil.h parm types given both in parmlist and separately

    Can anybody out here help me. MAybe the prob is very simple, but because i am sort of a newby, I cannot find the solution.
    Thanks a lot.

    Regards,

    Richard

    /*================================================= ==================*/
    /* Program 'test' */
    /* */
    /* This program computes the self-diffusion on a lattice square */
    /*-------------------------------------------------------------------*/
    /* Author: Richard van Beusichem */
    /* Email: [email protected] */
    /*================================================= ==================*/

    /*===== Include files ===============================================*/
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <nrutil.h>
    #define ROW 5
    #define COL 5
    #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
    #define M 7
    #define NSTACK 50

    /*===== Function prototypes =========================================*/
    double expon(double x); // Returns an exponential random variable
    double Random(); // Returns an uniformly distributed random number
    int rand_int(int a, int b); // Returns random integer from interval [a,b]
    void sort2(unsigned long n, float arr[], float brr[]);

    /* Define the number of molecules */
    const int MOL= 5;

    /*====== Main Program ===============================================*/
    int main() {
    int i,e,a,b,lattice[ROW][COL]; /* array that represents the lattice */
    double residence[ROW][COL]; /* array that holds exponential residence times */
    double res_mol[MOL][2];
    float mol_nr[MOL];
    float time[MOL];
    double exp_rv; /* exponential random variable */
    double tau; /* mean residence time */
    int x,y; /* x,y coordinates on lattice */
    int j;
    /* Initialize array */
    for (i=0; i<COL; i++)
    {
    for (e=0; e<ROW; e++)
    lattice[i][e]=0;
    }
    /* Initialize array */
    for (i=0; i<COL; i++)
    {
    for (e=0; e<ROW; e++)
    residence[i][e]=0;
    }
    /* Initialize array */
    for (i=0; i<MOL; i++)
    {
    for (e=0; e<2; e++)
    res_mol[i][e]=0;
    }

    a=0;
    b=ROW-1;
    tau=10.0;

    /* Place molecules randomly on the lattice */
    for (i=1;i<=MOL; i++)
    {
    x=rand_int(a,b);
    y=rand_int(a,b);
    while (lattice[x][y]>0)
    {
    x=rand_int(a,b);
    y=rand_int(a,b);
    }
    lattice[x][y]=i;
    }

    for (i=0;i<ROW;i++)
    { for(e=0;e<COL;e++)
    printf("%3d",lattice[i][e]);
    printf("\n");

    }

    /* Generate and output exponential random variables */
    for (i=0; i<ROW; i++)
    {
    for (e=0; e<COL; e++)
    {
    exp_rv = expon(1.0 / tau);
    residence[i][e]=exp_rv;
    }
    }
    for (i=0; i<ROW; i++)
    {
    for (e=0; e<COL; e++)
    {
    for (j=0; j<MOL; j++)
    {
    if (lattice[i][e]==j+1)
    {
    res_mol[j][0]=j+1;
    res_mol[j][1]=residence[i][e];
    }
    }
    }
    }
    for (i=0; i<MOL; i++)
    {
    mol_nr[i]=res_mol[i][0];
    }
    for (i=0; i<MOL; i++)
    {time[i]=res_mol[i][1];
    }
    sort2(MOL,mol_nr,time);

    for (i=0;i<ROW;i++)
    { for(e=0;e<COL;e++)
    printf("%f",residence[i][e]);
    printf("\n");

    }
    for (i=0;i<MOL;i++)
    { for(e=0;e<2;e++)
    printf("%f",res_mol[i][e]);
    printf("\n");

    }
    for (i=0; i<MOL; i++)
    {
    printf("%f",mol_nr[i]);
    }
    system("PAUSE");
    return 0;
    }
    //================================================== =========================
    //= Function to generate Exponentially Distributed Random Variables =
    //= - Input: Mean value of distribution =
    //= - Output: Returns with exponentially distributed random variable =
    //================================================== =========================
    double expon(double x)
    {
    double exp_value; // Computed exponential value to be returned

    // Compute exponential random variable using inversion method
    exp_value = -x * log(Random());

    return(exp_value);
    }
    //================================================== =========================
    //= Function to generate a random integer on a specified interval =
    //= - Input: Interval [a,b] =
    //= - Output: Returns with random integer from the interval =
    //================================================== =========================
    int rand_int(int a, int b)
    {
    return rand()%(b-a+1) + a;
    }
    //================================================== =========================
    //= Function to generate Uniformly Distributed Random Numbers =
    //= =
    //= - Output: Returns uniformly distributed random numbers =
    //================================================== =========================

    static unsigned long int uliSeed = 1;

    void InitRandom( long int iMySeed ) {
    uliSeed = iMySeed;
    }

    double Random() {
    long int liA = 16807;
    long int liM = 2147483647;
    long int liQ = 127773;
    long int liR = 2836;
    long int liTempSeed;

    liTempSeed = liA*( uliSeed%liQ ) - liR*( uliSeed/liQ );
    if( liTempSeed >= 0 )
    uliSeed = liTempSeed;
    else
    uliSeed = liTempSeed + liM;

    return( ((double) uliSeed)/liM );
    }
    //================================================== =========================
    //= Function to sort an array arr[1..n] into ascending order =
    //= using Quicksort, while making the corresponding rearrangement =
    //= of the array brr[1..n]. =
    //= =
    //= - Input: Arrays =
    //= - Output: Arrays sorted based on exponential residence times =
    //================================================== =========================

    void sort2(unsigned long n, float arr[], float brr[])
    #include <nrutil.h>
    {
    unsigned long i,ir=n,j,k,l=1,*istack;
    int jstack=0;
    float a,b,temp;

    istack=lvector(1,NSTACK);
    for (;;) { /* Insertion sort when subarray small enough. */
    if (ir-l < M) {
    for (j=l+1;j<=ir;j++) {
    a=arr[j];
    b=brr[j];
    for (i=j-1;i>=l;i--) {
    if (arr[i] <= a) break;
    arr[i+1]=arr[i];
    brr[i+1]=brr[i];
    }
    arr[i+1]=a;
    brr[i+1]=b;
    }
    if (!jstack) {
    free_lvector(istack,1,NSTACK);
    return;
    }
    ir=istack[jstack]; /* Pop stack and begin a new round of partitioning.*/
    l=istack[jstack-1];
    jstack -= 2;
    } else {
    k=(l+ir) >> 1; /* Choose median of left, center and right elements
    as partitioning element a. Also
    rearrange so that a[l] = a[l+1] = a[ir]. */
    SWAP(arr[k],arr[l+1])
    SWAP(brr[k],brr[l+1])
    if (arr[l] > arr[ir]) {
    SWAP(arr[l],arr[ir])
    SWAP(brr[l],brr[ir])
    }
    if (arr[l+1] > arr[ir]) {
    SWAP(arr[l+1],arr[ir])
    SWAP(brr[l+1],brr[ir])
    }
    if (arr[l] > arr[l+1]) {
    SWAP(arr[l],arr[l+1])
    SWAP(brr[l],brr[l+1])
    }
    i=l+1; /*Initialize pointers for partitioning.*/
    j=ir;
    a=arr[l+1]; /*Partitioning element.*/
    b=brr[l+1];
    for (;;) { /*Beginning of innermost loop.*/
    do i++; while (arr[i] < a); /*Scan up to find element > a.*/
    do j--; while (arr[j] > a); /*Scan down to find element < a.*/
    if (j < i) break; /*Pointers crossed. Partitioning complete.*/
    SWAP(arr[i],arr[j]) /*Exchange elements of both arrays.*/
    SWAP(brr[i],brr[j])
    } /*End of innermost loop.*/
    arr[l+1]=arr[j]; /*Insert partitioning element in both arrays.*/
    arr[j]=a;
    brr[l+1]=brr[j];
    brr[j]=b;
    jstack += 2;
    /*Push pointers to larger subarray on stack, process smaller subarray immediately.*/
    if (jstack > NSTACK) nrerror("NSTACK too small in sort2.");
    if (ir-i+1 >= j-l) {
    istack[jstack]=ir;
    istack[jstack-1]=i;
    ir=j-1;
    } else {
    istack[jstack]=j-1;
    istack[jstack-1]=l;
    l=i;
    }
    }
    }
    }

    Below used header nrutil.h

    void nrerror(char error_text[]);
    float *vector(long nl, long nh);
    int *ivector(long nl,long nh);
    unsigned long *lvector(long nl,long nh);
    double *dvector(long nl, long nh);
    double **dmatrix(long nrl, long nrh, long ncl, long nch);
    void free_vector(float *v, long nl, long nh);
    void free_ivector(int *v, long nl,long nh);
    void free_lvector(unsigned long *v, long nl,long nh);
    void free_dvector(double *v, long nl, long nh);
    void free_dmatrix(double **m, long nrl, long nrh, long ncl, long nch);

  2. #2
    ---
    Join Date
    May 2004
    Posts
    1,379
    Nobody is going to read your code until you use CODE TAGS

  3. #3
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    and till u make proper indentations in your code.its really a headache to read something like what you have written.please use code tags

  4. #4
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    How can a quicksort be that big????????

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  2. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  3. C++ compilation issues
    By Rupan in forum C++ Programming
    Replies: 1
    Last Post: 08-22-2005, 05:45 AM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. Problems with str.replace function
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 11-07-2001, 03:35 AM