GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 05-Sep-2005, 17:58
Elsydeon Elsydeon is offline
Junior Member
 
Join Date: Aug 2005
Posts: 45
Elsydeon is on a distinguished road

Recursion and the confusion that comes with it


Heh, well, here's my newest problem. We've been told to write a recursive method that will take a list of numbers, take the central (or a central) point, and sort them so that the left side is composed of nothing but numbers smaller than the pivot point, and the right side is nothing but numbers greater than the pivot point. Then it cuts the two sides up and repeats. We were given all of the other methods but qksortRecur and told to make it work, so I'm assuming everything else should remain untouched. I've written something I think SHOULD work... and couts before my attempts to call the method within the method work. Why am I getting nothing when I attempt to make the method call itself correctly? A cout at the top of the function shows me the function is at least calling itself fine, it prints out hundreds of times...

CPP / C++ / C Code:
#include <iostream.h>

void qksortRecur (int list[], int first, int last) {
	int pivot; //Central point for dividing into sub-arrays and swapping variables
	int temp, count, left=0, right=last, templ, tempr;
	if(last>=1){
		pivot=(last+1)/2;//So long as there are two or more values to sort
		for(count=0;count<=last;count++){
			while(list[left]<pivot){//Pinpoint outermost value to swap on left side of pivot
				left++;
			}
			while(list[right]>pivot){//pinpoint outermost value to swap on right side of pivot
				right--;
			}
			if(list[left]>pivot){//Swap chosen values
				templ=list[left];
				tempr=list[right];
				list[left]=tempr;
				list[right]=templ;
			}
			else;
			
			
		}
		temp=pivot+1;
		//This is where my code is failing.  Beyond this point nothing happens when I put a cout in
		qksortRecur(list, 0, pivot);
		qksortRecur(list, temp, last);
		

	}
	

} // quicksortRecur


void quicksort(int arr[], int numEntries) {
	// sorts the first numEntries in arr
    qksortRecur(arr, 0, numEntries - 1);
}


void printArray(int array[], int numEntries) {
// outputs the first numEntries in array
    for (int i = 0; i < numEntries; i++)
		cout <<"  " <<array[i];
    cout <<endl;
}

void main(void) {
	int A[] = { 96, 43, 20, 25, 55, 32, 43, 19, 22, 68, 87, 11, 84, 28 };
    cout <<"Before sorting:";
    printArray(A, 14);
    quicksort(A, 14);
    cout <<" After sorting:";
    printArray(A, 14);
}

  #2  
Old 05-Sep-2005, 21:05
maprich maprich is offline
Member
 
Join Date: May 2005
Posts: 163
maprich has a spectacular aura aboutmaprich has a spectacular aura about
Hi Elsydeon,
Your quicksorting fails in two aspects: 1. the recursion is endless -> runtime failure. 2. even if point 1 is fixed still fails to give correct answers..

Your implementation of your function qksortRecur() has following conceptual errors:
  • The function should operate ONLY with array indexes from first to last. However your code systematically always starts the indexes from zero instead of first. Also the selection of pivot is incorrect.
  • Your idea of quick sort is incorrect. What if in your array all values up to PIVOT are smaller than pivot (thus not require moving) and still some value right from the pivot is smaller than the pivot? Imagine if your pivot e.g is the smallest value in your list. You incorrectly assume that you can just flip-flop values from "right" to "left" and from "left" to "right".

For the above reason I do not start to analyze your code.
To write your recursive quick sort you can find the explanation of the concept from wikipedia. Actually there is so detailed pseudo code here, scroll to "Version with in-place partition" that you can convert it directly to C language and have your assignment done in about 10 minutes.
 
 

Recent GIDBlogDeveloping GUIs with wxPython (Part 2) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 18:19.


vBulletin, Copyright © 2000 - 2008, Jelsoft Enterprises Ltd.