Sort while keeping duplicates together

Question

I have three vectors

vector<string> a_words0(75000);
vector<string> a_words1(75000);
vector<string> a_words2(75000);

Consider below how the elements look like of the same row:

.
.
.
It's    raining  outside
The     warrior  is
It's    raining  heavily
It's    raining  outside
.
.
.

I was using the quicksort function to sort according to the first vector, and it's giving me the following results

.
.
.
It's    raining  outside
It's    raining  heavily
It's    raining  outside
The     warrior  is
.
.
.

The thing is I want the duplicates to be together like this:

.
.
.
It's    raining  outside
It's    raining  outside
It's    raining  heavily
The     warrior  is
.
.
.

This is my quick sort function:

void quicksort(vector<string> &arr0, vector<string> &arr1,vector<string> &arr2,int low, int high)
{
int i = low;
int j = high;
string y = "Z";
/* compare value */
string z = arr0[(low + high) / 2];

/* partition */
do {
    /* find member above ... */
    while(arr0[i] < z) i++;

    /* find element below ... */
    while(arr0[j] > z) j--;

    if(i <= j) {
        /* swap two elements */
        y = arr0[i];
        arr0[i] = arr0[j]; 
        arr0[j] = y;
        y = arr1[i];
        arr1[i] = arr1[j]; 
        arr1[j] = y;
        y = arr2[i];
        arr2[i] = arr2[j]; 
        arr2[j] = y;
        i++; 
        j--;

    }
} while(i <= j);


/* recurse */
if(low < j) 
    quicksort(arr0,arr1,arr2, low, j);

if(i < high) 
    quicksort(arr0,arr1,arr2, i, high); 
}

I want to sort it according to the first column and in the same time I want the duplicates to be together — user1804029, Dec 01 '14 at 13:45
That's not a question. You just said what you wanted to do and dumped your code. — Borgleader, Dec 01 '14 at 13:46
If you don't know, it's alright. I have no idea what do you want — user1804029, Dec 01 '14 at 13:54
someone did and gave me what I wanted, now go and play with your dolls. — user1804029, Dec 01 '14 at 14:39
With that attitude, I wish I could downvote your question more than once. — AAT, Dec 01 '14 at 15:10
Related to: http://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl — Jarod42, Dec 01 '14 at 16:10
@AAT my attitude?! how about those who commented with the philosophy of what a question might be?! well excuse me I stand up for myself when I sense sarcasm. Plus if they don't get the question, I didn't force anyone to answer it. They can simply ignore it if they are that brilliant. — user1804029, Dec 02 '14 at 09:36

score 1 · Answer 1 · answered Dec 01 '14 at 14:20

You can change the compare to compare two elements of arr0 and if the same, then compare two elements of arr1 and if still the same, compare two elements of arr2. You might consider changing the name of Y to T (for temp), and then using X, Y, Z as the pivot points for arr0, arr1, and arr2.

Quick sort isn't stable, so you can't use multiple sort passes from least significant to most signifcant. You could use std::stable_sort() (normally implemented as a merge sort), and again use a custom compare that compares arr0, arr1, and arr2 if needed, or sort the data 3 times, by arr2 first, then arr1, then arr0.

Sort while keeping duplicates together

1 Answers1