Member Avatar for laNeek

Greetings!

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.
		 ++i;
	 }
	 while(strcmp ((a[j])->fname, (a[pivot])->fname) > 0 ) {
		 --j;
	 }

            if (i <= j) {

				tmp = a[i];

				a[i] = a[j];

				a[j] = tmp;

                  i++;

                  j--;

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

            falphaquickSort(a, left, j);

      if (i < right)

            falphaquickSort(a, i, right);

}
  • 1 Contributor
  • 2 Replies
  • 114 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by laNeek

Dani AI

Generated

A few focused points that explain the behaviour you saw and offer robust fixes.

The symptom " described — the array ending up as two internally sorted halves — commonly means the partition comparisons were being done against an element that moved during the swaps. When the partition compares to a[pivot] but then swaps elements that include a[pivot], the pivot element can relocate and later comparisons are using a different key. The safest quick fix is to copy the pivot key before the partition and always compare to that copy (not to a[pivot]).

Example of copying the pivot key (for an employee** a pointer array):

char pivotKey[32];
std::strcpy(pivotKey, a[(left+right)/2]->fname);

int i = left, j = right;
while (i <= j) {
    while (std::strcmp(a[i]->fname, pivotKey) < 0) ++i;
    while (std::strcmp(a[j]->fname, pivotKey) > 0) --j;
    if (i <= j) {
        std::swap(a[i], a[j]);
        ++i; --j;
    }
}
if (left < j) quickSort(a, left, j);
if (i < right) quickSort(a, i, right);

A better long-term approach is to avoid C-style strings and manual pointer arrays entirely: use std::vector<employee> (or std::vector<std::unique_ptr<employee>>) and std::sort with a comparator that uses std::strcmp (or, even better, change fname/sname to std::string and compare directly). Example comparator:

bool cmp(const employee &A, const employee &B) {
    int r = std::strcmp(A.sname, B.sname);
    return (r < 0) || (r == 0 && std::strcmp(A.fname, B.fname) < 0);
}
std::sort(v.begin(), v.end(), cmp);

Quick checklist for debugging:

  • Make sure any pointer array is populated (pointers point to valid objects) and you do not delete the backing storage before sorting.
  • Ensure name buffers are null-terminated and large enough.
  • If partition loops hang, print i, j, and the pivot key each iteration to see why pointers stop moving.
  • Use modern containers/strings to eliminate many classes of bugs.
Member Avatar for 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!

Member Avatar for laNeek

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...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.