5 Replies - 30000 Views - Last Post: 07 January 2008 - 06:15 PM Rate Topic: -----

#1 dmd1120  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 21-November 07

Non-Recursive QuickSort (using Stack)

Post icon  Posted 07 January 2008 - 04:55 PM

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.


#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: 07 January 2008 - 05:21 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Non-Recursive QuickSort (using Stack)

#2 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Non-Recursive QuickSort (using Stack)

Posted 07 January 2008 - 05:07 PM

It would be more helpful if we could see all the code.

On a separate note, what errors are you getting trying to compile the examples in your book?
Was This Post Helpful? 0
  • +
  • -

#3 dmd1120  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 21-November 07

Re: Non-Recursive QuickSort (using Stack)

Posted 07 January 2008 - 05:31 PM

View PostTom9729, on 7 Jan, 2008 - 05:07 PM, said:

It would be more helpful if we could see all the code.

On a separate note, what errors are you getting trying to compile the examples in your book?



Ok, I just edited my original post to include all the code from the program.

In regards to the book, I guess I'm disappointed because there are no actual example programs that I can type in to see it work. It's all just little snippets, and although I don't remember the compile errors I had been getting, I still have yet to get any of them to work properly. My brother recently gave me one of his old textbooks from a Data Structures class, and that has been helpful. However, I've spent so much time on this horrible book, that I don't have much more time to complete the class... therefore, I don't know how much time I'll have to read the better book. the book he gave me is older, though... published in 2000. The quicksort in that book is actually rather different from the quicksort code in my textbook, too. I intend to comment on the poor quality of the book when I fill out my end-of-class survey. The school has been pretty receptive to my comments in the past, so hopefully they'll change this book for future students.
Was This Post Helpful? 0
  • +
  • -

#4 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Non-Recursive QuickSort (using Stack)

Posted 07 January 2008 - 05:50 PM

There are lots of nice tutorials online if you know where to look. :)

By the way, I haven't looked through your code extensively but it just segfaulted when I tried to run it.

Program received signal SIGSEGV, Segmentation fault.
0x0804918e in main () at h.c:27
27	  }	// main


Was This Post Helpful? 0
  • +
  • -

#5 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Non-Recursive QuickSort (using Stack)

Posted 07 January 2008 - 06:12 PM

I threw in a method to print the array out and it's over writing with huge negative values, i'm assuming are garbage or an address and not generated by your code. Seems there is an address written to the array somewhere, i'm not positive on that, but i'll look into it more a little later
Was This Post Helpful? 0
  • +
  • -

#6 dmd1120  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 21-November 07

Re: Non-Recursive QuickSort (using Stack)

Posted 07 January 2008 - 06:15 PM

View PostTom9729, on 7 Jan, 2008 - 05:50 PM, said:

There are lots of nice tutorials online if you know where to look. :)

By the way, I haven't looked through your code extensively but it just segfaulted when I tried to run it.

Program received signal SIGSEGV, Segmentation fault.
0x0804918e in main () at h.c:27
27	  }	// main



I don't get any errors when compiling, but I hadn't tried to actually run the program until you mentioned the Segfault. I don't get that error, but I get
Run-Time Check Failure #2 - Stack around the variable 'ary' was corrupted.


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1