Thread: Quicksort problem, now with clear code

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

    Quicksort problem, now with clear code

    Hi everybody,

    I have two arrays, A and B. A contains [9,8,7.....,0]. Array B [0,1,2....,9]. Now I want to sort array A so that it goes from 0 to 9 and array B must change in the same way. Note that this is just an example to get it work. Later I will implement this in arrays that are randomly filled. I got a code from numerical recipes that should do the job, but I cannot get it to work. (http://www.library.cornell.edu/nr/bookcpdf/c8-2.pdf).

    The errors that I get are:

    1 C:\Dev-Cpp\include\nrutil.h parm types given both in parmlist and separately.

    Below are the program code and the used header file. I would really appreciate it if someone can give me a hand here.

    Code:
    #include <stdio.h>
    #include <math.h>
    #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
    #define M 7
    #define NSTACK 50
    void sort2(unsigned long n, float arr[], float brr[]);
    
    int main()
    {
        float A[10];
        float B[10];
        int i;
        
      for (i=0; i<10; i++)
      {
        A[i]=10-i;  
      }
      for (i=0; i<10; i++)
      {
        B[i]=i;
      }    
    sort2(10,A,B);
    system("PAUSE");   
    }
    
    void sort2(unsigned long n, float arr[], float brr[])
    /*Sorts an array arr[1..n] into ascending order using Quicksort, 
    while making the corresponding rearrangement of the array brr[1..n].*/
    #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;
                }
            }
        }    
    }
    Header file nrutil.h

    Code:
    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
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Move this
    Code:
    #include <nrutil.h>
    to a more sensible location first.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 05:20 AM
  3. Problem : Threads WILL NOT DIE!!
    By hanhao in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2004, 01:37 PM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM