7
\$\begingroup\$

My implementation of insertion, merge, and quick sort, with some utility testing functions. I just wanted to know how I can improve the efficiency and general cleanliness of my code.

(note: I know C++ has partition, but I want to do most of the implementation myself)

In particular, my main algorithms take iterators [first, last], but STL container's v.begin() and v.end() go 1 over the last element, so I have wrappers that call the main algorithm with first and end - 1.

How can I restructure this into the main algorithm (if that would be better)?

#include <iterator>
#include <vector>
using namespace std;

// Insert sort O(n^2) time O(1) space
template <typename Iterator>
void ins_sort(Iterator first, Iterator end) {
    for (Iterator cur = first; cur < end; ++cur) {
        auto key = *cur;
        Iterator ins = cur - 1;
        for (; first <= ins && key < *ins; --ins)
            *(ins + 1) = *ins;    // move 1 to right until correct position's found
        *(ins + 1) = key;
    }
}

// Merge sort O(nlogn) time O(n) space
template <typename Iterator>
void merge(Iterator first, Iterator middle, Iterator last) {
    using T = typename iterator_traits<Iterator>::value_type;
    vector<T> left(first, middle + 1);
    vector<T> right(middle + 1, last + 1);
    left.push_back(0xFFFFFFF); // sentinel
    right.push_back(0xFFFFFFF);
    for (int i = 0, j = 0, k = 0; k <= last - first; ++k) {
        if (left[i] < right[j]) first[k] = left[i++];
        else first[k] = right[j++];
    }
}

template <typename Iterator>
void merge_helper(Iterator first, Iterator last) {
    if (first < last) {
        Iterator pivot = first + (last - first)/2;   // half way point rounded down
        merge_helper(first, pivot);
        merge_helper(pivot + 1, last);
        merge(first, pivot, last);
    }
}

template <typename Iterator>
void mer_sort(Iterator first, Iterator end) {
    merge_helper(first, end - 1);
}


// Quick sort O(nlogn) time O(n) space
template <typename Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first > 0) {
        auto pivot = *(first + (last - first) / 2); 
        Iterator left {first};
        Iterator right {last};
        while (left <= right) {
            while (*left < pivot) ++left;
            while (pivot < *right) --right;
            if (left <= right) { swap(*left, *right); ++left; --right; }
        }
        quick_sort(first, right);
        quick_sort(left, last);
    }
}
template <typename Iterator>
void qck_sort(Iterator first, Iterator end) {
    quick_sort(first, end - 1);
}

Testing code

#include <random>
#include <vector>
#include <iostream>
using namespace std;

class Rand_int {
public:
    Rand_int(int low, int high) : distribution{low, high} {
    }
    int operator()() {
        return distribution(engine);
    }

private:
    default_random_engine engine;
    uniform_int_distribution<> distribution;
};

template <typename T>
void print(vector<T> v) {
    for (auto x : v)
        cout << x << ' ';
    cout << '\n';
}

vector<int> randgen(int max, int num) {
    static Rand_int die{0, max};
    vector<int> res(num);
    for (int i = 0; i < num; ++i)
        res[i] = die();
    return res;
}
\$\endgroup\$
3
\$\begingroup\$
  • There are few problems with merge:

    There is no guarantee that T can be constructed from an integral constant (how about sorting strings?). Even if it could, 0xFFFFFFF (BTW, what is this number?) is not necessarily a largest possible value (e.g.T could be 64 bit wide, or 16 bit wide); besides this value may legitimately belong to user data. Bottom line it, using an artificial sentinel is wrong.

    (left[i] < right[j]) condition breaks merge sort stability (which is very important reason of using merge sort in the first place).

    Calculating pivot as first + (last - first)/2 assumes a random access iterator, which rules out merge sorting linked lists (which is a second important reason for merge sort to be used). Take a look at std::distance and std::advance.

  • C++ has partition for a reason: it is very important algorithm of its own. I strongly recommend to factor it out as a function, and call it from quick_sort.

  • I don't see the reason for qck_sort and mer_sort to exist.

    Take a look on how all std:: algorithms operate on semi-open ranges. One of the reasons for that is that last (in STL sense) serves as a natural sentinel. For example, merging may look along the lines of

    void merge(I first1, I last1, I first2, I last2, O dst)
    {
        while ((first1 < last1) && (first2 < last2)) {
            if (*first1 <= *first2) {
                *dst++ = *first1++;
            } else {
                *dst++ = *first2++;
            }
        }
        while (first1 < last1) *dst++ = *first1++;
        while (first2 < last2) *dst++ = *first2++;
    }
    
\$\endgroup\$
  • \$\begingroup\$ Fixed sentinel with merge (I tested with data with largest valid value and it works now); I'll take a look at effective partitioning; qck_sort and mer_sort just wrap the respective sorts by passing end - 1 for last iterator (can you recommend a better way of dealing with end being 1 after last elem)? \$\endgroup\$ – LemonPi Oct 7 '14 at 18:33
  • \$\begingroup\$ It is against CR rules to edit the code: it invalidates the review. Consider rolling your changes back. You are welcome to post the new version in a follow-up question. \$\endgroup\$ – vnp Oct 7 '14 at 18:36
  • \$\begingroup\$ Ah, that would make sense; done. But my previous questions remain regarding end being 1 after last element \$\endgroup\$ – LemonPi Oct 8 '14 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.