Quicksort problems

[Invertedzero]

Hi, I've been struggling to find the problem in my code for quicksorting a list from an input file. It gets stuck in and endless loop displaying strange numerical values. I've lost what's going on as its something i've returned to

#include <iostream>
#include <cmath>
#include <fstream>
#include <cstdlib>
using namespace std;

struct person {
char firstname[14];
char surname[14];
int mobile;
};




// prototype function declaration(s)


void QuickSort(person** arr, int left, int right);


int main(){




char inputfilename[50];
char outputfilename[50];
// read the input and output filenames

//char sorttype;

cout << "Please enter the input file name: " << endl;
cin >> inputfilename;

cout << "\nPlease enter the output file name: " << endl;
cin >> outputfilename;


// declare arrays, open input file and read numbers into arrays


//declared data1 as the input array struct



ifstream inp(inputfilename);// Open inputfilename

// Error Check
if(!inp){
cerr << "Could not open input file " << inputfilename << endl;
exit(1);
}


int i=0;
while(inp){
if(i >= 1000000){
break;
}
else {
i++;
}
}

int eye = i;
const int FL = eye;

// close the input file and open the output file [llater]

inp.seekg(0, ios::beg);

//Allocate Dynamics memory database datadyn of size length FL as determined above
person* datadyn = new person[FL];

//Read all Inputfile values into Datadyn

i=0;
while(inp){
if(i >= FL+1){
break;
}
else {
inp >> datadyn[i].firstname;
inp >> datadyn[i].surname;
inp >> datadyn[i].mobile;
i++;
}
}
//Close input, reset counter i to zero
inp.clear();
inp.close();
i = 0;

/* TEST FOR READ INTO DYNAMIC MEMORY WORKING
cout << "Person 2 has surname " << datadyn[2].surname << endl;
cout << "Person 2 has mobile " << datadyn[2].mobile << endl;
cout << "Person 1 has firstname " << datadyn[1].firstname << endl;
cout << "Person 4 has firstname " << datadyn[4].firstname << endl;
cout << "Person 5 has mobile " << datadyn[5].mobile << endl;
*/
//TEST WORKS - KICK ARSE!

//Now for the Sorting Mechanism

person** pointerset = new person*[FL];

for (int w = 0; w < FL; w++){
pointerset[w] = &datadyn[w];
}

/*TEST FOR POINTERS
cout << "Person 2 has surname " << (*(pointerset[2])).surname << endl;
cout << "Person 2 has mobile " << (*(pointerset[2])).mobile << endl;
cout << "Person 1 has firstname " << (*(pointerset[1])).firstname << endl;
cout << "Person 4 has firstname " << (*(pointerset[4])).firstname << endl;
cout << "Person 5 has mobile " << (*(pointerset[5])).mobile << endl;
*/
//TEST WORKS! - KICK ARSE^2

char sorttype;

//Sorting Choice
cout << "Do you wish to sort by [f]irst name, [s]econd name, or [m]obile number?" << endl;
cin >> sorttype;

switch (sorttype){

case 'f':
case 'F': // treat upper and lower case as equivalent
//run lettersort
break;

case 's':
case 'S':
//run lettersort on surname

break;

case 'm':
case 'M':

//run numbersort on mobile

break;

default: // if you haven't chosen any valid option
cout << "Your Choice was invalid" << endl;
}

// sort the array

QuickSort(pointerset, 0, FL - 1); //sort array from first to last element
//TEST FOR POINTERS


//TEST WORKS! - KICK ARSE^2

/* PrintArray(datap, eye);

cin.get();
cin.get();
return 0;
*/

ofstream outp(outputfilename);

if(!outp){
cerr << "Failed to open output file " << outputfilename << endl;
exit(2);
}



}

// function definition(s) here

void QuickSort(person** arr, int left, int right) {

int i = left, j = right;

person* tmp;
//pivot is abritrary middle value
double pivot = (**(arr + ((left + right)/ 2))).mobile;
//

cout << "Person 2 has mobile " << pivot << endl;

/* partition */

while (i <= j) {

while ((*(arr[i])).mobile < pivot)

i++;

while ((*(arr[j])).mobile > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};



/* recursion */

if (left < j)

QuickSort(arr, left, j);

if (i < right)

QuickSort(arr, i, right);

}

[Jikax]

use code tags!

[hua052011]

Hi,

Good ideal, pls try to keep posting. I like this topic very much and I will digged this one. Tks again.
If you want to get more materials that related to this topic, you can visit: http://interviewquestionsandanswers.biz/computer-architecture-interview-questions/

Best regards.

[Perman]

Used qsort() from the library.
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

[Gaminic]

@Perman:
He's trying to implement a sort, not smply trying to sort something.

Also, is there any case where qsort() will outperform std::sort?

[Perman]

@Gaminic:

Good question. I don't know. But I would think that Sort() use a call to qsort() to sort a string in alphabetic order. That's a google question. I have been using qsort to sort random numbers and it works great. After been going through google about all the sorting ways it came out that quick sort is the best all around sorting way.

[Perman]

Hi Invertedzero:

When you copy code to your question then highlight it and go on the right side in format and select <>. That will set your file up right. It's tough to read without all the right tabs/spaces.

[Perman]

@Gaminic:
Found it on google. Seem like sort() is better than qsort(). I'm getting old. Ha Ha

sort() can be compared to the qsort() function in the C standard library (in stdlib.h). sort is templated, so it uses the correct comparison function for whatever data type you are sorting, which is already implemented for standard data types. Otherwise you can specify your own comparison function, which can be type-checked by the compiler; whereas for qsort, you must manually cast pointers to the desired type in an unsafe way. Also, qsort accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, which can take a lot of time; whereas in C++, comparison functions are usually inlined, removing the need for function calls. In practice, C++ code using sort is often many times faster at sorting simple data like integers than equivalent C code using qsort.