Hello again. I am frustrated, because none of the code in my textbook will actually compile, making it harder for me to figure out how to do some of this stuff! Anyway, I have an assignment whereby I have to write a non-recursive version of quicksort. The instructor did post some info, but I don't quite understand, and went my own way. However, I have come to a stop. I know that I have to change the value of the rightStart variable once I partition, but I am not sure where I should do this.
I can get it to compile, but I know there are some logical errors in there somewhere. If it's easier for you to find any logical errors, I can include all code so that you can simply compile it. For now, I am just including the 2 main functions. Also, I am wondering if, by doing it this way, I have made the assignment more difficult than is necessary? I appreciate any and all help I can get on this.
CODE
#include <cstdlib>
#include <iostream>
#include <stack>
using namespace std;
#define ARRAY_SIZE 20
// Prototype Declarations
void fillArray(int numArray[]);
void quickSortNR(int data[]);
void medianToLeft(int data[], int left, int right);
void sortSide(int data[], int &start, const int end);
int main (void)
{
// Local Declarations
int i;
int ary[ARRAY_SIZE];
// Statements
fillArray(ary);
quickSortNR(ary);
return 0;
} // main
void fillArray(int numArray[])
{
for(int x = 0; x < ARRAY_SIZE; x++)
{
numArray[x] = rand() % 49 + 1;
}
} // end fillArray
/* =============== medianToLeft ================
Find the median value of an array, data[left..right],
and place it in the location data[left].
Pre data is an array of at least three elements
left and right are the boundaries of the array
Post median value placed at data[left]
*/
void medianToLeft (int data[],
int left,
int right)
{
// Local Definitions
int mid;
int hold;
// Statements
// Rearrange sortData so median is in middle location
mid = (left + right) / 2;
if (data[left] > data[mid])
{
hold = data[left];
data[left] = data[mid];
data[mid] = hold;
} // if
if (data[left] > data[right])
{
hold = data[left];
data[left] = data[right];
data[right] = hold;
} // if
if (data[mid] > data[right])
{
hold = data[mid];
data[mid] = data[right];
data[right] = hold;
} // if
// Median is in middle. Exchange with left.
hold = data[left];
data[left] = data[mid];
data[mid] = hold;
return;
} // medianToLeft
/* ================ quickSortNR =================
Array data[] is sorted without recursion.
@pre data is an array of data to be sorted
@post data array is sorted
*/
void quickSortNR (int data[])
{
// Local Definitions
int sorted = 0; // keeps track of the number of sorted items
// and also determines start for next sort.
int rightStart = ARRAY_SIZE; // Starting point of the
// right partition
medianToLeft(data, sorted, rightStart);
sortSide(data, sorted, rightStart); // split to left and right
while(sorted <= rightStart)
{
medianToLeft(data, sorted, rightStart);
sortSide(data, sorted, rightStart); // sort left side
}
while(sorted < ARRAY_SIZE)
{
medianToLeft(data, sorted, ARRAY_SIZE);
sortSide(data, sorted, ARRAY_SIZE); // sort right side
} // end while
} // end quickSortNR
/* ========== sortSide ================
This function will 'partition' the array using a stack.
If either partition has 3 or less items, then those are
automatically sorted.
@pre There are items in the array
@post Items in the array are placed in order of
< pivot; pivot; > pivot */
void sortSide(int data[], int &start, int end)
{
// Local Declarations
int pivotVal = data[start-1]; // temporary variable to
// hold the value of the pivot
stack<int> lStack;
stack<int> rStack;
int stSize = 0; // # of items in stack
int cur = start + 1;
int temp;
// Statements
while(cur < end) // traverse through the items
// in the array (skip pivot)
{
// separate items into left and right stacks
if(data[cur] < pivotVal)
lStack.push(data[cur]);
else
rStack.push(data[cur]);
cur++;
} // end while
cur = start; // reset cur variable
stSize = lStack.size(); // get size of stack before
// moving back to array.
while (!lStack.empty())
{
data[cur] = lStack.top();
lStack.pop();
cur++;
}
/* If there are 3 or less items in the stack,
sort them without using another stack */
switch(stSize)
{
case 3:
start+= 4; //items in left stack
//and pivot are sorted.
if(data[cur] > data[cur+1])
{
int temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
if(data[cur] > data[cur+1])
{
temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
if(data[cur+1] > data[cur+2])
{
temp = data[cur+1];
data[cur+1] = data[cur+2];
data[cur+2] = temp;
}
break;
case 2:
start += 3;
if(data[cur] > data[cur+1])
{
int temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
break;
case 1:
start += 2;
break;
case 0:
start++;
break;
} // end switch
data[cur] = pivotVal;
start++;
cur++;
// SORT THE RIGHT SIDE
stSize = rStack.size(); // get size of stack before
// moving back to array.
while (!rStack.empty())
{
data[cur] = rStack.top();
rStack.pop();
cur++;
}
/* If there are 3 or less items in the stack,
sort them without using another stack */
switch(stSize)
{
case 3:
start+= 4; //items in left stack
//and pivot are sorted.
if(data[cur] > data[cur+1])
{
int temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
if(data[cur] > data[cur+1])
{
temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
if(data[cur+1] > data[cur+2])
{
temp = data[cur+1];
data[cur+1] = data[cur+2];
data[cur+2] = temp;
}
break;
case 2:
start += 3;
if(data[cur] > data[cur+1])
{
int temp = data[cur];
data[cur] = data[cur+1];
data[cur+1] = temp;
}
break;
case 1:
start += 2;
break;
case 0:
start++;
break;
} // end switch
data[cur] = pivotVal;
start++;
cur++;
} // end sortSide
This post has been edited by dmd1120: 7 Jan, 2008 - 04:21 PM
7 Jan, 2008 - 03:55 PM
| 