1
\$\begingroup\$

I was wondering if this implementation of insertion sort could be improved. Are there any things that I have done wrong?

template<typename Element>
void insertion_sort(Element arr[], size_t size) {
    size_t index, index_sorted;
    for (index = 0u; index < size; ++index) {
        auto temp = arr[index];
        index_sorted = index - 1;
        while (arr[index_sorted] >= 0 && arr[index_sorted] > temp) {
            arr[index_sorted + 1] = arr[index_sorted--];
        }
        arr[index_sorted + 1] = temp;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Are you using C++17? If yes, please add the c++17 tag. If not, the line arr[index_sorted + 1] = arr[index_sorted--]; is undefined behavior. More info \$\endgroup\$ – hoffmale Nov 14 '17 at 8:16
3
\$\begingroup\$

Small nitpicks

  • The for loop can be started from 1, as the iteration with 0 doesn't actually do anything.
  • Prefer to reduce the scope of variables if possible. This allows better reasoning for the compiler/optimizer, and makes the code more readable because the variable declaration is nearer to the actual usage.
  • The check arr[index_sorted] >= 0 in the while loop should probably be index_sorted >= 0u (after all, Element might not be comparable to integers), but this is true in all cases (-1 for an unsigned integer type is equal to that type's maximum value). However, even checking this becomes unnecessary if the first iteration starts at 1.
  • The array elements could possibly be moved to their new locations (this might improve performance in some cases).


template<typename Element>
void insertion_sort(Element arr[], size_t size) {
    for (auto index = 1u; index < size; ++index) {
        auto temp = std::move(arr[index]);
        auto index_sorted = index - 1;
        while (arr[index_sorted] > temp) {
            arr[index_sorted + 1] = std::move(arr[index_sorted--]);
        }
        arr[index_sorted + 1] = std::move(temp);
    }
}

Technically, the size of the array could be deduced automatically by taking a reference (though it has an ugly syntax). However, by taking an explicit size parameter one can sort a partial array, so I'd prefer the flexibility of this approach.

\$\endgroup\$

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.