HackerRank - Insertion Sort - Part 2

Question

This is the problem statement for Insertion Sort - Part 2.

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an element with just the first element - that is already "sorted" since there's nothing to its left that is smaller than it.

In this challenge, don't print every time you move an element. Instead, print the array every time an element is "inserted" into the array in (what is currently) its correct place. Since the array composed of just the first element is already "sorted", begin printing from the second element and on.

Actually just an insertion sort implementation with ints and vector. How can I make this code faster? How can I improve this code?

#include <vector>
#include <iostream>

void print(const std::vector<int>& v) {
    for (auto x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

int main() {
    int s;
    std::cin >> s;
    std::vector<int> sorted(s);
    int i = 0;
    while (std::cin && i != s) {
        std::cin >> sorted[i++];
    }
    for (std::size_t i= 1; i < sorted.size(); ++i) {
        std::size_t j = i;
        for (std::size_t k = 0; k < j; ++k) {
            if (sorted[j] < sorted[k]) {
                std::swap(sorted[j],sorted[k]);
            }
        }
        print(sorted);
    }
}

Answer 1

Probably the single biggest (or most obvious, anyway) improvement would be to write an actual insertion sort. What you have right now appears to be a bubble sort rather than an insertion sort.

Rather than swapping elements that are out of order an insertion sort divides the array into a sorted part and an unsorted part. In the beginning, the sorted part is just the first element. Then it looks at the first element of the unsorted part, copies it into a temporary location, and copies elements in the sorted part "forward" a spot until it gets to an element smaller than the temporary. That makes a "hole" for the new element to go into, and it puts that element there (then repeats for the remaining unsorted elements).

Given an array v of n elements, the loops look something like this:

for (int i=1; i<n; i++) {
    tmp = v[i];
    int j;
    for (j=i; j>0 && tmp<v[j-1]; j--)
        v[j] = v[j-1];
    v[j] = tmp;
}