HACKER RANK Algorithms Sorting Challenges - Insertion Sort - Part I Solution.'C++'

Algorithms Sorting Challenges - Insertion Sort - Part I Solution

Problem Statement

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with an already sorted list.

Insert element into sorted list
Given a sorted list with an unsorted number e in the rightmost cell, can you write some simple code to insert e into the array so that it remains sorted?

Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

Guideline: You can copy the value of e to a variable and consider its cell "empty". Since this leaves an extra cell empty on the right, you can shift everything over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace it with e.

Input Format
There will be two lines of input:

• Size - the size of the array
• Arr - the unsorted array of integers

Output Format
On each line, output the entire array every time an item is shifted in it.

Constraints
1≤Size≤1000
−10000≤e≤10000,e∈Arr

Sample Input

5
2 4 6 8 3

Sample Output

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
2 3 4 6 8 

Explanation

3 is removed from the end of the array.
In the 1st line 8>3, so 8 is shifted one cell to the right.
In the 2nd line 6>3, so 6 is shifted one cell to the right.
In the 3rd line 4>3, so 4 is shifted one cell to the right.
In the 4th line 2<3, so 3 is placed at position 2.

Task

Complete the method insertionSort which takes in one parameter:

• Arr - an array with the value e in the right-most cell.

Next Challenge

In the next Challenge, we will complete the insertion sort itself!

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void insertionSort(vector <int>  ar) {
    int array_size = ar.size(); // the original size of the vector ar
 
    for (int i = array_size - 1; i >= 1; i--){
        for (int j = i - 1; j >= 0; j--){
            if (ar.size() == array_size && ar.at(i) < ar.at(j) ){
                ar.insert(ar.begin() + i, ar.at(j));
                ar.push_back(ar.at(i + 1));
                ar.erase(ar.begin() + i + 1);
 
                for (int k = 0; k < array_size; k++){
                    cout << ar.at(k) << " ";
                }
                cout << endl;
            }
            else if (ar.size() == array_size + 1 && ar.at(j) < ar.back()){
                ar.insert(ar.begin() + j + 1, ar.back());
                ar.erase(ar.begin() + j + 2);
                ar.pop_back();
 
                for (int k = 0; k < array_size; k++){
                    cout << ar.at(k) << " ";
                }
                cout << endl;
                i++;
                break;
            }
            else if (ar.size() == array_size + 1 && j == 0){
                ar.insert(ar.begin() + j, ar.at(j));
                ar.erase(ar.begin() + j + 2);
                
                for (int k = 0; k < array_size; k++){
                    cout << ar.at(k) << " ";
                }
                cout << endl;
 
                ar.insert(ar.begin(), ar.back());
                ar.erase(ar.begin() + 2);
                ar.pop_back();
 
                for (int k = 0; k < array_size; k++){
                    cout << ar.at(k) << " ";
                }
                cout << endl;
                i++;
            }
            else if (ar.size() == array_size + 1 && ar.at(j) > ar.back()){
                ar.insert(ar.begin() + j, ar.at(j));
                ar.erase(ar.begin() + j + 2);
 
                for (int k = 0; k < array_size; k++){
                    cout << ar.at(k) << " ";
                }
                cout << endl;
            }
        }
    }
}
 
int main(void) {
    vector <int>  _ar;
    int _ar_size;
    cin >> _ar_size;
    for (int _ar_i = 0; _ar_i<_ar_size; _ar_i++) {
        int _ar_tmp;
        cin >> _ar_tmp;
        _ar.push_back(_ar_tmp);
    }
 
    insertionSort(_ar);
 
    return 0;
}

Thanks for Visiting, Hope this helps you....

Copyright © 2015 HackerRank.
All Rights Reserved