C++ quicksort with 2 requirements

Question

My goal is to sort a list of words according to two criteria:

• the primary criterion is increasing word length,
• the secondary criterion is alphabetical order

For example:

{red,a,three,b,four,aeoli}

should be sorted as:

{a,b,red,four,aeoli,three}.

I have two separate quicksorts: one on length followed by one on alphabetical.

I was just curious how to merge these two? The main problem I am encountering is I don't know how to sort alphabetically while taking the length into mind, and running through the whole list.

Any advice is appreciated, the following code is my main and the quicksort functions:

Vector<String> words;
    String word;
    ifstream inFile;
    inFile.open("practice.txt");
    while(!inFile.eof()){
        getLine(inFile,word);
        words.push_back(word);
    }
    inFile.close();
    String pivot = "qog";
    if(words[2] < pivot)
        cout << "Bigger" << endl;
    words.quicksort(2,words.length()-2);
    words.quicksort2(2,words.length()-2);

the quicksort for length

template <typename T>
void Vector<T>::quicksort(int left, int right)
{
    int i = left;
    int j = right;
    String pivot = data[(left+right)/2];

    if(i <= j)
    {
        while(data[i].getLength() < pivot.getLength())
        i++;
        while(pivot.getLength() < data[j].getLength())
        j--;

    }

    if(i <= j)
    {
        String temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        i++;
        j--;
    }

    if(left < j)
        quicksort(left,j);
    if(i < right)
        quicksort(i,right);

}

and the one for letters

template <typename T>
void Vector<T>::quicksort2(int left, int right)
{
    int i = left;
    int j = right;
    String pivot = data[(left+right)/2];

    if(i <= j)
    {
        while(data[i] < pivot)
        i++;
        while(pivot < data[j])
        j--;

    }

    if(i <= j)
    {
        String temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        i++;
        j--;
    }

    if(left < j)
        quicksort2(left,j);
    if(i < right)
        quicksort2(i,right);


}

NOTE: This is done with my own custom Vector and String classes, both versions run perfectly, so my main problem is the logic of the sort itself -- how to get them to run together.

Also I can only use iostream, fstream and cstring, along with anything else I implement myself.

Thanks in advance.

Answer 1

Just work backwards from a sensible implementation using std, re-implementing (cut down) versions of the things you use.

sort(vec.begin(), vec.end(), [](auto & lhs, auto & rhs){ return tie(lhs.size(), lhs) < tie(rhs.size(), rhs); });

We then need implementations of tuple, sort and tie

struct tuple
{
    const int & first;
    const String & second;
};

bool operator<(const tuple & lhs, const tuple & rhs)
{
    if (lhs.first < rhs.first) return true;
    if (rhs.first < lhs.first) return false;
    return lhs.second < rhs.second;
}

tuple tie(const int & first, const String & second)
{
    return { first, second };
}

We can then adapt your implementation of Vector::quicksort

template <typename Iter, typename Comp>
void quicksort(Iter left, Iter right, Comp comp)
{
    auto distance = (right - left) / 2
    Iter l = left;
    Iter pivot = left + distance;
    Iter r = right;

    if(l <= r)
    {
        for(;comp(*l, *pivot); ++l);
        for(;comp(*pivot, *r); --j);
    }

    if(i <= j)
    {
        String temp = *i;
        *i = *j;
        *j = temp;
        ++i;
        --j;
    }

    if(left < j)
        quicksort(left, j, comp);
    if(i < right)
        quicksort(i, right, comp);
}

Or we can instead look at this Q&A, and also implement partition, find_if_not, etc

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = distance(first, last);
    if (N <= 1) return;
    auto const pivot = *next(first, N / 2);
    auto const middle1 = partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = find_if_not(first, last, p);
    if (first == last) return first;

    for (ForwardIt i = next(first); i != last; ++i) {
        if (p(*i)) {
            iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

template<class InputIt, class UnaryPredicate>
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q)
{
    for (; first != last; ++first) {
        if (!q(*first)) {
            return first;
        }
    }
    return last;
}

template<class InputIt>
void iter_swap(InputIt a, InputIt b)
{
    using value_type = typename InputIt::value_type;
    value_type temp = static_cast<value_type&&>(*a); // aka std::move
    *a = static_cast<value_type&&>(*b);
    *b = static_cast<value_type&&>(temp);
}

template<class T>
void iter_swap<T*>(T * a, T * b)
{
    T temp = static_cast<T&&>(*a); // aka std::move
    *a = static_cast<T&&>(*b);
    *b = static_cast<T&&>(temp);
}

template<class InputIt>
InputIt next(InputIt it, int distance)
{
    return it + distance;
}

Answer 2

I guess eventually, you would want it to be sorted by min value of a word. a short word has less "value" than a long one and because letters weight less than words I would sort it by the total ascii value of each word. In this case you don't need to use 2 sorts and merge, calc the ascii value of each object and sort by it.

Answer 3

If you must chain the two algorithms together, for a school assignment or whatever, you will need to implement stable partition (or use std::stable_partition).

EDIT - After reading your "NOTE", I should mention that another way to appease the teacher would be to implement a third version of quicksort that uses both criteria in the predicate. See shorter_less below. Better yet, pass the predicate as a function pointer into a single, unified quicksort, the way std::sort and std::stable_sort do it. I.e. ...

Here's the C++ way of doing it all in one go ...

#include <string>
#include <algorithm>
#include <vector>

using std::string;

static bool shorter_less( const string& L, const string &R) {
    if (L.length() == R.length()) return L<R;
    else return L.length() < R.length();
}

int main() {
    using str_vec = std::vector<string>;
    str_vec vec{ "xxzy" , "Alphonse", "Betty", "pea", "nuts", "z" };
    std::sort(vec.begin(), vec.end(), shorter_less);
}