I've been messing around with a bit of code for a while now and I've got it compiling etc etc. The only problem is with perfecting the quicksort function (probably trivial, but then I'm not very skilled). From the output file, it seems to 'sort of' sort the string arrays that are fed in. I suspect the problem lies with the string compare function - which I'll admit I don't fully understand - but further fiddling has just given me a bunch of compilation errors.

Here is the quicksort, integrated to give some context (though if there's still too much unnecessary code, please tell me!):

#include <iostream>
#include <iomanip>
#include <cctype>
#include <cmath>   
#include <cstdlib>
#include <fstream>

using namespace std;

struct employee {
	char fname[20];
	char sname[20];
	int mnum;

void falphaquickSort (employee** a, int left, int right);// function declaration

int main(void){

	employee* details = new employee[count];
	employee** pdetails = new employee*[count];

	for(int i=0; i < count; i++){// creates array (of structs to hold all persons in the file	
		in >> details[i].fname >> details[i].sname >> details[i].mnum;
}// etc etc. this part of the code works just fine.

delete [] details;

void falphaquickSort(employee** a, int left, int right) {

      int i = left, j = right;

	 employee* tmp;
	 int pivot = (left + right)/2;

	 while(strcmp ((a[i])->fname, (a[pivot])->fname) < 0 ) {// start of partition. I'm told 'strcmp' gives a zero, -ve or +ve value depending on the relative values of the pointers but I'm stuck on how to utilise this to perfect the sort.
	 while(strcmp ((a[j])->fname, (a[pivot])->fname) > 0 ) {

            if (i <= j) {

				tmp = a[i];

				a[i] = a[j];

				a[j] = tmp;



			};// end of partition
	  if (left < j) // start of recursion 

            falphaquickSort(a, left, j);

      if (i < right)

            falphaquickSort(a, i, right);

8 Years
Discussion Span
Last Post by laNeek

I forgot to mention that earlier in the main section of code, 'count' is defined as the number of records read in.

I also want to apologise for being the hundredth student to give in a (relatively trivial) quicksort related problem. I have been working on this code for a week or so and been checking through the forums for about as long to the point where now it makes me almost sick to look at it!


The code has been fixed! The first thing I realised was that the quicksort as above leaves the input data in two 'sorted' halves, which meant I needed to implement another quicksort to sort the two halves into one completely sorted array eg.

void falphaqs (employee** pdetails, int count) {

	falphaquickSort (pdetails, 0, count-1);


I also ditched the use of a 'pivot' value and used 'left' instead for a comparison value. I don't quite know why this worked better but it did the trick - I suppose I just need to study it more! On the plus side, I figured out what to do with the strcmp function so my programming is slightly improving...

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.