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:
}
Need help: Passing array as parameter.