##string sorting problem##I spent more than 7hour

i am a beginner.
My assignment is due tonight:(
please help me w/ this:

read the input file(input.txt)
the file is like this(number of data,then uid,name,gender,score):
20
2012019109 Proadan Legeaf Coaa Female 65
2009675341 Payloth Legeragord Nydiragan Female 82
2009277197 Grardosh Astaym Male 93
2012205829 Kigon Habwyn Weramas Female 52
2006366045 Wudric Legauseth Male 75
2010022169 Etewyn Cadela Male 52
2011717606 Dwelil Arear Nydoitrem Female 51
2007450802 Dwelictred Ciaand Adraugan Male 54
2012780768 Abiaf Elelgrin Legulgrin Male 65
2007810296 Traewan Oleralath Eowireldric Female 74
2011145267 Aboi Arendatrem Male 95
2008160596 Kendatlan Chali Female 50
2010793260 Araew Jererraldan Kililith Male 99
2012075038 Gwalenwan Charer Ae Male 81
2007517117 Gleisean Eleimas Lareap Female 50
2009722021 Wiradan Oniranyth Nydirag Male 62
2008272089 Boiloth Chilimond Male 98
2006387263 Wiranwan Eowaoctred Helidon Female 83
2010442942 Dreath Tareg Male 89
2007449576 Wiraa Wicalesh Female 89

then output a file arragned according to alphabetical order.
some restrictions: use array for uid,name,gender,score

i am ok with the input ,output
but cannot tackle the sorting problem
selection sort, bubble sort and insertion sort are too inefficient
because the sample size is 10^5.
i tried bucket sort and heap sort. they work well with integer but fail when it comes to string.
also, the default sort operator works, but they cannot swap other arrays(uid,gender,score) accordingly.
Wait, you got several parallen arrays instead of defining a struct and one array of said struct?

If you do, change it to using struct and use default sort function with custom comparators

EDIT: I mean, something like that:
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
struct PersonInfo
{
    unsigned long ID;
    std::string name;
    bool /*or string*/ sex;
    int score;
}

bool sortByScore(PersonInfo& lhs, PersonInfo& rhs)
{
    return lhs.score < rhs.score;
}

bool sortById(PersonInfo& lhs, PersonInfo& rhs)
{
    return lhs.ID< rhs.ID;
}

bool sortByName(PersonInfo& lhs, PersonInfo& rhs)
{
    return lhs.name < rhs.name;
}

/*...*/

PersonInfo persons[size];
//fill persons

std::sort(persons, persons + size, sortById);
Last edited on
but that is the constraint :(
i have to use arrays:(((( wt a waste of time!
You still using arrays. At least one.

EDIT: You can use quick sort. Most implementation you will find should suffice. Only change you should do is change swap function you are using to affect all arrays at once.
Last edited on
i'ms sorry, i didnt make it clear.
the exact instruction is :

Keep the students' information on di fferent attributes (e.g., Name, Gender) into separate arrays, i.e.,
you have to create an array for each of these attributes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void swapAll(size_t i, size_t j)
{
    std::swap(uid[i], uid[j]);
    std::swap(name[i], name[j]);
    std::swap(gender[i], gender[j]);
    std::swap(score[i], score[j]);
}

void sortById(unsigned long uid[])
{
    //Sorting alghoritm decided which values should be swapped, their indexes is i and j
        swapAll(i, j);
    //Alghoritm continues
}

Something like that
This code above swaps the positions of 2 entries in the array, but it does not assign a condition indicating exactly when the entries should be swapped, could you please gimme a hand on that?

I have looked up many different sorting methods online, however they do not work for sorting string arrays (most sorting algorithms are for sorting integers only).
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
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>

void write_arrays_sorted_on_name( std::size_t n, // number of elements
                                  std::string uid[], std::string name[],
                                  std::string gender[], int score[],
                                  const char* output_file_name )
{
   // create a vector if indices 0 .. n-1
   std::vector< std::size_t > indices(n) ;
   for( std::size_t i = 0 ; i < n ; ++i ) indices[i] = i ;

   // sort the indices on the name
   // for example
   const auto compare_names = [name] ( std::size_t i, std::size_t j )
                                { return name[i] < name[j] ; } ;
   std::sort( indices.begin(), indices.end(), compare_names ) ;

   std::ofstream file(output_file_name) ; // open the output file

   // write out uid, name, gender, score in order of sorted indices
   for( std::size_t index : indices ) // for each index in indices
   {
        file << uid[index] << ' ' << name[index] << ' ' << gender[index]
             << ' ' << score[index] << '\n' ;
   }
}
Last edited on
Wait, do you have char* array instead of std::string? Is this another requirement?

swapAll function swaps all entries at once (if name is std::string) to preserve relations between them.

All sorting algoritms uses swap function somewhere, that is where you should use your custom function.

EDIT: JLBorges this soution will lose it attractiveness when teacher will ask him what the hell is happening on line 17 :)

Another Idea: Create arrays like assigment instructed but doexn't do anything with them; instead, create array of struct, like I suggested, and do all operations with it.
All instructions done to the letter. Nobody told we should use these arrays, right? :)
Last edited on
lets have a look at the exact assignment here
https://www.dropbox.com/s/l2evuc4uq6lctum/Assignment3.pdf
i cannot use vector...i have to use arrays:(
> i cannot use vector...i have to use arrays:(

Why?

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
#include <string>
#include <algorithm>
#include <fstream>

void write_arrays_sorted_on_name( std::size_t n, // number of elements
                                  std::string uid[], std::string name[],
                                  std::string gender[], int score[],
                                  const char* output_file_name )
{
   // create an array if indices 0 .. n-1
   // I presume you aren't allowed to use std::unique_ptr<> either
   std::size_t* indices = new std::size_t[n] ;
   for( std::size_t i = 0 ; i < n ; ++i ) indices[i] = i ;

   // sort the indices on the name
   // for example
   const auto compare_names = [name] ( std::size_t i, std::size_t j )
                                { return name[i] < name[j] ; } ;
   std::sort( indices, indices+n, compare_names ) ;

   std::ofstream file(output_file_name) ; // open the output file

   // write out uid, name, gender, score in order of sorted indices
   for( std::size_t i = 0 ; i < n ; ++i ) // for each index in indices
   {
        std::size_t index = indices[i] ;
        file << uid[index] << ' ' << name[index] << ' ' << gender[index]
             << ' ' << score[index] << '\n' ;
   }

   delete [] indices ;
}


> this soution will lose it attractiveness when teacher will ask him what the hell is happening on line 17 :)

I suppose that lok05 won't be blindly copying the code without understanding it. And if the professor is afflicted with standardC++ophobia, as long as the logic is understood, lok05 would be able to replace the lambda function with something that is more palatable to the teacher.
Last edited on
the restriction by professor
std::array :)
Who say it isn't an array, cast the first stone :)
A custom bottom up merge sort implementation:

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
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

int mergesort(int n, string *id, string *name, string *gender, int *score);


int main()
{
    const int NSIZE = 5;
    string id[NSIZE] = {
        "2012019109", "2009675341", "2009277197", "2012205829", "2006366045"
    };
    string name[NSIZE] = {
        "Proadan Legeaf Coaa", "Payloth Legeragord Nydiragan",
        "Grardosh Astaym", "Kigon Habwyn Weramas", "Wudric Legauseth"
    };
    string gender[NSIZE] = {
        "Female", "Female", "Male", "Female", "Male"
    };
    int score[NSIZE] = {65, 82, 93, 52, 75};

    if (mergesort(NSIZE, id, name, gender, score))
    {
        for (int i=0; i<NSIZE; ++i)
            cout << left << setw(12) << id[i]
                 << setw(30) << name[i]
                 << setw(8) << gender[i]
                 << score[i] << endl;
    } else  cout << "Out of memory\n";
}


//---------------------------------
void mergehelper(string *id, string *name, string *gender, int *score,
                 int beg, int end,
                 string *nid, string *nname, string *ngender, int *nscore)
{
    if(end == beg+1) return;

    int mid = (beg+end)/2;
    int i0 = beg;
    int i1 = mid;

    mergehelper(id, name, gender, score,
                beg, mid,
                nid, nname, ngender, nscore);
    mergehelper(id, name, gender, score,
                mid, end,
                nid, nname, ngender, nscore);

    for (int i = 0; i < end - beg; i++)
    {
        bool smallLeft = (i0 < mid && (i1 >= end || name[i0] < name[i1]));
        int j = (smallLeft ? i0 : i1)++;
        nid[i] = id[j];
        nname[i] = name[j];
        ngender[i] = gender[j];
        nscore[i] = score[j];
    }
    for(int i = beg; i < end; i++)
    {
        int j = i - beg;
        id[i] = nid[j];
        name[i] = nname[j];
        gender[i] = ngender[j];
        score[i] = nscore[j];
    }
}
//---------------------------------
int mergesort(int n, string *id, string *name, string *gender, int *score)
{
    string *nid = new string[n];
    if(!nid) return 0;
    string *nname = new string[n];
    if(!nname) return 0;
    string *ngender = new string[n];
    if(!ngender) return 0;
    int *nscore = new int[n];
    if(!nscore) return 0;

    mergehelper(id, name, gender, score,
                0, n,
                nid, nname, ngender, nscore);
    delete [] nid;
    delete [] nname;
    delete [] ngender;
    delete [] nscore;
    return 1;
}
And all of the above answers won't work without some modification if char* arrays are used insted of std::string.
So I still waiting for answer: how are data arrays are defined?
tntxtnt,
your source code works.
Thank you.
Can you add some description coz i cannot get what's going on,,,
many thanks
mergehelper() is the main sort function. It requires a working array (has same size with original array) so it doesnt have to allocate new arrays everytime it divides old array into 2 sub arrays.
line 40: if array size = 1 we dont need to sort anything
line 42-44: divide array into 2 sub arrays left & right
line 46-48: merge sort left array
line 49-51: merge sort right array
line 53-61: merge left array & right array into a new sorted array
line 62-69: copy the new sorted array to the original array

mergesort() allocates memory for the working array and calls mergehelper then cleans up the working array.
Last edited on
Topic archived. No new replies allowed.