0
\$\begingroup\$

The parameters list contain the array that is passed to and the size of the array respectively. Is there anywhere I could improve my code?

void insertionSort(int a[], int s) {
    for (int i = 0; i < s - 1; i++) {
        int j = i + 1;
        int key = a[j];
        while (i >= 0 && a[i] > key) {
            a[i+1] = a[i];
            i--;
        }
        a[i+1] = key;
    }
}
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

In both this and your bubble sort implementation you need to start using C++ idioms (otherwise this is just C code (that's fine C is a great language it's just not C++)).

I would say this is the perfect C implementation of insertion sort.

But usually when you implement these kinds of algorithms in C++ you use iterators to specify the range (as this allows you to sort several types of container including arrays).

Rather than:

void insertionSort(int a[], int s) {

You should probably use:

template<typename I>
void insertionSort(I begin, I end) {

Then you can sort any type of container with:

int  a[] = {1,4,5,27,3,9,1};
insertionSort(std::begin(a), std::end(a));

std::vector<int> v = {1,4,5,27,3,9,1};
insertionSort(std::begin(v), std::end(v));

etc...

Interestingly this also allows you to sort any type (not just integers). As long as your type supports the comparison operator. The standard library tends to implement any comparison in terms of operator<() so to avoid confusion with potential users you should implement your sort using the less than operator and potentially allow the user to specify the actual comparison operator.

// Unless you have an explicit override.
// std::less<T> uses `operator<()` to do the comparison.
// So this means the algorithm will work for type T under three situations.
//    1) operator< is defined for the type T
//    2) There is an specialization of `std::less<>` for type T
//    3) An explicit type is provided to the sort for comparing type T.
template<typename I, typename Comp = std::less<T>>
void insertionSort(I begin, I end) {
    Comp   comp;
    // Stuff
\$\endgroup\$
0
\$\begingroup\$

Encouraged by 200_success, I just repeat that there is nothing to improve in your implementation. It's short, crisp and correct.

Actually, when inserting a current key into its correct position, the basic insertion sort uses swapping routine that takes 3 assignments. Your implementation does not, which is nice (instead, you save the current key, shift to right by one step as far as needed, insert the key). That variant is called straight insertionsort.

If you ask me, however, maybe it would be nice to make a generic version of the same algorithm using random access iterators; just suggesting.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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