C++

Forum

 
Dual Recursive Quicksort?

Cat32 (25)
Hey everyone! So, I'm supposed to be writing a dual recursive quick sort to sort names with the year they were born. I'm given a sample file with names and a year separated by a comma, like this:
"Max,1979
Wade,1935
Hugh,1983"
There aren't any more than 30 names in the file. The program should read the names and years into an array. The dual sort should sort the names alphabetically with the year they were born and then print out the names with the age. It will sort the names with the year born and calculate the ages correctly if I input the information manually into a Point array. I just can't figure out how to read in the names and years separately. Is there a way to read in from a file until there's a comma? Thank you in advance for your help!
Here's all of my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
  #include <iostream>
#include <string>
#include <ctime>
#include <fstream>
#include <cstdlib>
#include <stdio.h>
using namespace std;

struct Point {
        string x;
        int y;

        bool operator<(const Point& b) {
                if (this->x < b.x)
                        return true;
                else if (this->x == b.x && this->y <= b.y)
                        return true;

                return false;
        }
};

void quickSort(Point [], int, int);
int partition(Point [], int, int);
void swap(Point &, Point &);

int main()
{
    ifstream inputFile;
    string filename;

    cout << "Please enter the filename: ";
    cin >> filename;
    inputFile.open(filename.c_str());
    Point array[32];
    int arraySize = 0;
    int num=0;
    string name;
    int year;
    string data;
    while (inputFile)
    {
        if ((num%2)==0)
        {
        inputFile >> data;
        array[arraySize].x=data;
        }
        else
        {
        inputFile >> data;
        year=atoi(data.c_str());
        array[arraySize].y=year;
        }
        arraySize++;
        num++;
    }
    inputFile.close();
    time_t now = time(0);
    struct tm* today = localtime(&now);
    int curr_year=today->tm_year+1900;

        int count;
        cout << "Names" << "         " << "Year Born" << endl;
        for (count=0; count < arraySize; count++)
        cout << array[count].x << "          " << array[count].y << endl;

        quickSort(array, 0, arraySize-1);

        cout << "Names" << "         " << "Ages" << endl;
        for (count = 0; count <arraySize; count++)
        cout << array[count].x << "          " << curr_year - array[count].y << endl;
        return 0;
}

void quickSort (Point set[], int start, int end)
{
        int pivotPoint;

        if (start < end)
        {
                pivotPoint = partition (set, start, end);
                quickSort(set, start, pivotPoint-1);
                quickSort(set, pivotPoint+1, end);
        }
}

int partition(Point set[], int start, int end)
{
        Point pivotValue;
        int pivotIndex, mid;

        mid = (start + end)/2;
        swap(set[start], set[mid]);
        pivotIndex=start;
        pivotValue = set[start];
        for (int scan = start +1; scan<=end; scan++)
        {
                if (set[scan] < pivotValue)
                {
                        pivotIndex++;
                        swap(set[pivotIndex], set[scan]);
                }
        }
        swap(set[start], set[pivotIndex]);
        return pivotIndex;

}

void swap(Point &value1, Point &value2)
{
        Point temp = value1;

        value1= value2;
        value2 = temp;
}


Here's the output I get:
Please enter the filename: names.txt
Names Year Born
Wade,1935 -60265736
0
Eric,1936 -1407053432
0
Perry,2010 -1295925223
0
James,2010 6
0
Daryl,1955 4196671
0
Guy,1981 0
0
Bob,1969 -1292948112
0
Albert,1963 -1292977344
0
Ian,1972 -1
0
Dwight,1975 0
0
Clay,1982 -1409228608
0
Marion,1990 -1405057544
0
Kirk,1951 6299648
0
Names Ages
2015
2015
2015
2015
2015
2015
2015
2015
2015
2015
2015
2015
2015
Albert,1963 1292979359
Bob,1969 1292950127
Clay,1982 1409230623
Daryl,1955 -4194656
Dwight,1975 2015
Eric,1936 1407055447
Guy,1981 2015
Ian,1972 2016
James,2010 2009
Kirk,1951 -6297633
Marion,1990 1405059559
Perry,2010 1295927238
Wade,1935 60267751

Again, thank you!
Smac89 (1727)
Not sure why you call the struct Point. Now if only C++ has std::string::split built in. Possible solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>
#include <vector>


class Person {
    std::string name;
    int year;
public:
    Person(){}
    Person (std::string name, int year) : name(name), year(year) {}

    friend std::istream &operator >> (std::istream& iss, Person& person) {
        std::getline(iss, person.name, ',');
        iss >> person.year;
        return iss;
    }
    
    friend std::ostream &operator << (std::ostream& oss, const Person& p) {
        return oss << p.name << ' ' << p.year;
    }
};


int main() {
    std::vector<Person> people;
    std::copy(std::istream_iterator<Person>(std::cin),
        std::istream_iterator<Person>(),
        std::back_inserter(people));

    for (Person &p : people) {
        std::cout << p << '\n';
    }
   return 0;
}



Demo:
http://coliru.stacked-crooked.com/a/caced5c140ea5155
Last edited on
Cat32 (25)
I called it point because originally I wrote this with a 2 dimensional array of numbers. They were x,y points. I was trying to see if I could get everything to work before dealing with names and reading from a file.

I still don't really understand how to use this method to read from a file with commas? I'm sorry, I'm really new to c++.
Smac89 (1727)
This is your code. The interesting part is:
1
2
 
std::getline(inputFile, array[i].x, ',');
inputFile >> array[i].y;


The first line reads a string until it encounters the character specified in the 3rd parameter
The second line reads the rest of the input as an integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <string>

int main() {
    ifstream inputFile;
    string filename;

    cout << "Please enter the filename: ";
    cin >> filename;
    inputFile.open(filename.c_str());

    Point array[32];
    
    for (int i = 0; inputFile; i++) {
        std::getline(inputFile, array[i].x, ',');
        inputFile >> array[i].y;
    }

    ...
}


Also add this after the second line:
inputFile.ignore('\n', std::numeric_limits<std::streamsize>::max());

Be sure to #include <limits>
The reason you include this is so that the reading starts from the next line afterwards. If you notice from the one I posted before, the output had spaces between each thing printed. The reason being that this line was not used

http://www.cplusplus.com/reference/istream/istream/getline/
http://www.cplusplus.com/reference/istream/istream/ignore/
Last edited on
Cat32 (25)
Hm. I added everything you said and it compiles fine, but it doesn't print out anything. Just the "Names", "Year Born", "Names", and "Ages". I must've done something wrong.
Thank you for your time and patience! I really appreciate it.
Cat32 (25)
I'm so dumb. I forgot to increment the arraySize variable. It works. Thank you SO much. I've been struggling with this stupid program all day! I really appreciate it!!!
Topic archived. No new replies allowed.