How do I fix the second value of insertion sorting in tuple to work as well with the first value

Fernando Goncalves 0
Viewed 39

Basically, I am trying to do Insertion Sorting on a tuple which is stored inside a vector, and I have a function to do it, when I only use the first value (get<0>(tupleVector[i])) it works, but when I try to add the second value (get<1>(tupleVector[i])) it doesn't, here's the whole function code.

void sort(vector<tuple<size_t, size_t>>& tupleVector, vector<int> idVector){
    // insertionSort
    for (int i = 1; i < tupleVector.size(); i++) {
        int key = get<0>(tupleVector[i]);
        int key2 = get<1>(tupleVector[i]);
        int j = i;

        while (j > 0 && get<0>(tupleVector[j - 1]) > key && get<1>(tupleVector[j - 1]) > key2) {
            get<0>(tupleVector[j]) = get<0>(tupleVector[j - 1]);
            get<1>(tupleVector[j]) = get<1>(tupleVector[j - 1]);
            j--;
        }

        get<0>(tupleVector[j]) = key;
        get<1>(tupleVector[j]) = key2;
    }
    cout << "Sorted" << endl;
}

EDIT:

I forgot to give examples of how it doesn't work, if I use values like ([500, 100], [700, 100], [100, 100], [500, 200]) it just doesn't sort anymore, but if I remove the (get<1>(tupleVector[i])) then it sorts based on the first value, but I need to sort for both, there's no compiler error or anything, it just doesn't sort

vector tuples c++
2 Answers

Assuming you intend a lexicographical comparison then your comparison operator fails to do so.

Assume you want to compare ordinary strings lexicographically:

Your operator would then accept xx as smaller to zz, as both characters in first string are smaller than the ones in second string – however this requirement fails to compare one of xz and zx as smaller than the other, as in neither string both characters are smaller as in the other one; thus neither of xz < zx nor zx < xz applies meaning both strings are considered equivalent with the consequence that when being sorted they are allowed to appear in arbitrary order.

Lexicographically one of these strings is already smaller if just the first of these characters is smaller, i.e. xy is smaller than both zx and zz, no matter if second character is smaller, equal or larger. On the other hand one string cannot be smaller if already first character is greater (obviously…) – i.e. to be smaller even if first character is not then first character needs to be equal. In this case the second character being smaller defines the entire string being smaller: xy is smaller than xz, but neither than xy nor than xx.

So as summary, you compare lexicographically two values by x[0] < y[0] || x[0] == y[0] && x[1] < y[1] – and you can apply this analogously to your tuples.

Generalised to arbitrary length then you can iterate over all characters of the strings x and y (testing x < y) or all members of the tuple respectively, returning true immediately if you encounter a value smaller in x than in y, false if you encounter a value greater and just continue iterating otherwise – until you encounter the end of one of the strings/tuples. If then y has further characters/members x still is smaller, otherwise not. Solely that iterating over tuples more complicated than with strings…

Aconcagua0

Turns out that (get<0>(tupleVector)) wasn't needed at all, I just changed it so that it sorted the tuple without needing to use two comparison checks, here's the updated code

void sort(vector<tuple<size_t, size_t>>& tupleVector){
    // insertionSort
    for (int i = 1; i < tupleVector.size(); i++) {
        tuple<size_t, size_t> key = (tupleVector[i]);
        int j = i;

        while (j > 0 && (tupleVector[j - 1]) > key) {
            (tupleVector[j]) = (tupleVector[j - 1]);
            j--;
        }

        (tupleVector[j]) = key;
    }
    cout << "Sorted" << endl;
}
Fernando Goncalves0
Related