Need help: Passing array as parameter.
Author Message
Need help: Passing array as parameter.

Source code is below. The whole thing is an 'improved' quicksort. I am
stuck while testing the MOM module (medium of medium)

Compiler is VC++ 5.

What it is supposed to do: when array size is 8, MOM will divide it into
two subgroups: 5 in the first, and the left 3 in the 2nd, find the medium
of each subgroup using the MO5 function (which has be tested OK); then
find the medium of the two mediums.

Problem: in the statement : tempArray[i]=MO5(A, p+(i*5), p+(i*5)+4);

When MO5 is called, and array A is passed to MO5, A loses its elements
with subscrip>=4. (the first 4 elements are OK).

Any ideas? email and followup please. Thanks. Don,

----------- source code -----------------------

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

int size;

//proto

void QUICKSORT(int[], int, int);
//takes an integer array, left limit and right limit;
//returns nothing;
int PARTITION(int[], int, int, int);
//takes an integer array, left limit, right limit and pivot;
//returns the right limit index of the left half.
int SELECT(int[], int, int, int);
//takes an integer array, left limit, right limit and
//'k'-th smallest element. (takes the 'k' value);
//returns the value of the k-th smallest element;
int MOM(int[], int, int);
//medium of medium
//takes an integer array, left limit and right limit;
//returns the value of medium of medium.
int MO5(int[], int, int);
//medium of 5 elements
//takes an integer array, left limit and right limit;
//returns the value fo medium of 5 or less elements

void printArray(int[], int, int);
//takes an integer array, left and right limit;

void QUICKSORT(int A[], int p, int r){
if (p<r){
int q=PARTITION(A, p, r, A[p]);
printArray(A, p, r);
QUICKSORT(A, p, q);
QUICKSORT(A, q+1, r);
}

Quote:
}

int PARTITION(int A[], int p, int r, int pivot){
int i=p-1;
int j=r+1;

for (;;){

do j--; while (A[j]>pivot);
do i++; while (A[i]<pivot);
if (i<j) {
int tempInt=A[i];
A[i]=A[j];
A[j]=tempInt;
}
else return j;
}

Quote:
}

int SELECT(int A[], int p, int r, int kth){

int momPivot=MOM(A, p, r);
PARTITION(A, p, r, momPivot);

int i=p;
while (A[i++]!=momPivot);

if (kth==i) return momPivot;
else    if (kth<i)   return SELECT(A, p, i, kth);
else            return SELECT(A, i+1, r, kth-i);

Quote:
}

int MOM (int A[], int p, int r){

int count=r-p+1;
if ( count<=5 ) return MO5(A, p, r);
else {
int *tempArray;
tempArray = new int( count/5+1 );
for (int i=0; i<=count/5-1; i++){
/*problem is here*/     tempArray[i]=MO5(A, p+(i*5), p+(i*5)+4);
}
//              if ((count%5))
tempArray[i]=MO5(A, p+i*5, r);
return MOM(tempArray, 0, count/5);
}//end of else

Quote:
}

int MO5(int *A, int p, int r){
for (int j=p+1; j<=r; j++){
int key= A[j];
int i=j-1;
while ( (i>=p) && (A[i]>key) ){
A[i+1]=A[i];
i--;
}//end of while
A[i+1]=key;
}//end of for
printArray(A, p, r);
return A[((r-p+1)/2)+p];

Quote:
}

void printArray(int A[], int p, int r){
for (int i=p; i<=r; i++){
cout<<A[i]<<"   ";
}
cout<<endl<<endl<<endl;

Quote:
}

main(){
cout<<"\n\n\n\n\n\n";
size=8;
//      cout<<" size of array?  ";
//      cin>>size;
int *theArray;
theArray=new int(size);
//srand(time(NULL));
for (int i=0; i<=size-1; i++){
theArray[i]=rand()%999;
cout<<theArray[i]<<"  ";
}
cout<<endl;

cout<<MOM(theArray, 0, size-1)<<endl<<endl;
//      QUICKSORT(theArray, 0, size-1);
printArray(theArray, 0, size-1);
return 0;

Quote:
}

Wed, 12 Apr 2000 03:00:00 GMT
Need help: Passing array as parameter.

On further debugging, the problem occur when tempArray is allocated
memory in the MOM function. the de{*filter*} shows the array is already
corrupted. (the original array passed to the MOM function!)

: Source code is below. The whole thing is an 'improved' quicksort. I am
: stuck while testing the MOM module (medium of medium)
:
: Compiler is VC++ 5.
:
: What it is supposed to do: when array size is 8, MOM will divide it into
: two subgroups: 5 in the first, and the left 3 in the 2nd, find the medium
: of each subgroup using the MO5 function (which has be tested OK); then
: find the medium of the two mediums.
:
: Problem: in the statement : tempArray[i]=MO5(A, p+(i*5), p+(i*5)+4);
:
: When MO5 is called, and array A is passed to MO5, A loses its elements
: with subscrip>=4. (the first 4 elements are OK).
:
: Any ideas? email and followup please. Thanks. Don,
:
: ----------- source code -----------------------
:
: #include <iostream.h>
: #include <stdlib.h>
: #include <time.h>
:
:
: int size;
:
: //proto
:
:
: void QUICKSORT(int[], int, int);
:       //takes an integer array, left limit and right limit;
:       //returns nothing;
: int PARTITION(int[], int, int, int);
:       //takes an integer array, left limit, right limit and pivot;
:       //returns the right limit index of the left half.
: int SELECT(int[], int, int, int);
:       //takes an integer array, left limit, right limit and
:       //'k'-th smallest element. (takes the 'k' value);
:       //returns the value of the k-th smallest element;
: int MOM(int[], int, int);
:       //medium of medium
:       //takes an integer array, left limit and right limit;
:       //returns the value of medium of medium.
: int MO5(int[], int, int);
:       //medium of 5 elements
:       //takes an integer array, left limit and right limit;
:       //returns the value fo medium of 5 or less elements
:
: void printArray(int[], int, int);
:       //takes an integer array, left and right limit;
:
:
: void QUICKSORT(int A[], int p, int r){
:       if (p<r){
:               int q=PARTITION(A, p, r, A[p]);
:               printArray(A, p, r);
:               QUICKSORT(A, p, q);
:               QUICKSORT(A, q+1, r);
:       }
: }
:
: int PARTITION(int A[], int p, int r, int pivot){
:       int i=p-1;
:       int j=r+1;
:
:       for (;;){
:
:               do j--; while (A[j]>pivot);
:               do i++; while (A[i]<pivot);
:               if (i<j) {
:                       int tempInt=A[i];
:                       A[i]=A[j];
:                       A[j]=tempInt;
:               }
:               else return j;
:       }
: }
:
:
: int SELECT(int A[], int p, int r, int kth){
:
:       int momPivot=MOM(A, p, r);
:       PARTITION(A, p, r, momPivot);
:
:       int i=p;
:       while (A[i++]!=momPivot);
:
:       if (kth==i) return momPivot;
:       else    if (kth<i)   return SELECT(A, p, i, kth);
:                       else            return SELECT(A, i+1, r, kth-i);
: }
:
:
: int MOM (int A[], int p, int r){
:
:       int count=r-p+1;
:       if ( count<=5 ) return MO5(A, p, r);
:       else {
:               int *tempArray;
:               tempArray = new int( count/5+1 );
:               for (int i=0; i<=count/5-1; i++){
: /*problem is here*/   tempArray[i]=MO5(A, p+(i*5), p+(i*5)+4);
:               }
: //            if ((count%5))
:                       tempArray[i]=MO5(A, p+i*5, r);
:               return MOM(tempArray, 0, count/5);
:       }//end of else
: }
:
:
: int MO5(int *A, int p, int r){
:       for (int j=p+1; j<=r; j++){
:               int key= A[j];
:               int i=j-1;
:               while ( (i>=p) && (A[i]>key) ){
:                       A[i+1]=A[i];
:                       i--;
:               }//end of while
:               A[i+1]=key;
:       }//end of for
:       printArray(A, p, r);
:       return A[((r-p+1)/2)+p];
: }
:
:
: void printArray(int A[], int p, int r){
:       for (int i=p; i<=r; i++){
:               cout<<A[i]<<"   ";
:       }
:       cout<<endl<<endl<<endl;
: }
:
: main(){
:       cout<<"\n\n\n\n\n\n";
:       size=8;
: //    cout<<" size of array?  ";
: //    cin>>size;
:       int *theArray;
:       theArray=new int(size);
:       //srand(time(NULL));
:       for (int i=0; i<=size-1; i++){
:               theArray[i]=rand()%999;
:               cout<<theArray[i]<<"  ";
:       }
:       cout<<endl;
:
:       cout<<MOM(theArray, 0, size-1)<<endl<<endl;
: //    QUICKSORT(theArray, 0, size-1);
:       printArray(theArray, 0, size-1);
:       return 0;
: }
:
:
:

Wed, 12 Apr 2000 03:00:00 GMT
Need help: Passing array as parameter.

Hi Donald,

Your program is in C++, and the newsgroup comp.lang.c discusses
the C programming language, which is not the same as C++.  Try

--

Jack

"Think twice, post once."

Thu, 13 Apr 2000 02:00:00 GMT
Need help: Passing array as parameter.

Quote:

> [snip]

>     tempArray = new int( count/5+1 );

> [snip]

>     theArray=new int(size);

> [snip]

First of all, you need to post to comp.lang.c++.

In any case, you're going to kick yourself...  You are using the wrong
syntax for the new operator.  It should be:

tempArray = new int [count/5+1];
...
theArray = new int[size];

By using parenthesis instead of square brackets you were asking the compiler
to allocate a single integer and initialize it with the given value instead
of allocating an array of the given size.

Note, you will want to add a corresponding "delete" for the arrays,
especially tempArray, in order to avoid memory leaks.

-- Tom

/==================================================================\
Thomas W. Brown                         Director of Development

Phone: (619)676-7854               10875 Rancho Bernardo Rd., #200
Fax  : (619)676-7710                      San Diego, CA  92127
\==================================================================/

Fri, 14 Apr 2000 03:00:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages