A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Insertion Sort in C++ page! Here, you'll find the source code for this program as well as a description of how the program works.

```
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
void insertSort(std::vector<int> &v)
{
int n = v.size();
int i = 0, j = 0, temp = 0;
for (i = 1; i < n; i++)
{
int store = v[i];
j = i - 1;
while (store < v[j] && j >= 0)
{
v[j + 1] = v[j];
j--;
}
v[j + 1] = store;
}
return;
}
int main(int argc, char *argv[])
{
std::vector<int> numbers;
if (argc != 2)
{
std::cout << "Usage: please provide a list of at least two "
"integers to sort in the format \"1, 2, 3, 4, 5\""
<< std::endl;
return 1;
}
std::string str = argv[1];
int i = 0, num = 0;
if (str.size() < 2)
{
std::cout << "Usage: please provide a list of at least two "
"integers to sort in the format \"1, 2, 3, 4, 5\""
<< std::endl;
return 1;
}
std::stringstream ss(str);
while (ss >> num)
{
numbers.push_back(num);
if (ss.peek() == ',')
{
ss.ignore();
ss.ignore();
}
else if (ss.tellg() != -1)
{
std::cout << "Usage: please provide a list of at least two "
"integers to sort in the format \"1, 2, 3, 4, 5\""
<< std::endl;
return 1;
}
}
insertSort(numbers);
for (i = 0; i < numbers.size() - 1; i++)
{
std::cout << numbers[i] << ", ";
}
std::cout << numbers[i] << std::endl;
return 0;
}
```

Insertion Sort in C++ was written by:

- Jeremy Grifski
- Prasun Kumar

If you see anything you'd like to change or update, please consider contributing.

**Note**: The solution shown above is the current solution in the Sample Programs repository as of Oct 10 2022 16:05:09. The solution was first committed on Oct 09 2019 21:10:56. As a result, documentation below may be outdated.

Let's walk through each line of code.

In our sample, we include a single standard library utility:

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
```

Here, we can see that we include of `iostream`

which contains the standard I/O
functions for printing messages onto the screen and for taking the inputs from the user.
The `bits/stdc++.h`

includes common C++ header files.

This function is called when the command-line arguments are invalid. It displays the usage statement and exits the program.

```
void handle_error()
{
cout << "Usage: please provide a list of at least two integers to sort in the format \"1, 2, 3, 4, 5\"" << endl;
exit(0);
}
```

```
vector<int> convert(string s)
{
vector<int> v;
string num = "";
for (int i = 0; i < s.size(); i++)
{
if ((int)s[i] >= 48 && (int)s[i] <= 57 || s[i] == ' ')
{
num += s[i];
}
else if (s[i] == ',')
{
v.push_back(check(num));
num = "";
}
else
{
handle_error();
}
}
if (num.size() > 0)
{
v.push_back(check(num));
}
return v;
}
```

This function take a string containing a comma-separated list of integers
to sort and validate it. The `for`

loop go through each character in the
string. When a number (from 48 to 57 – from ASCII `0`

to ASCII `9`

) or a space is
detected, it appended to the `num`

variable. When a comma is detected the
`check`

function is called to convert it to an integer, and `push_back`

is
called to append the integer to the vector `v`

. If any other character is
detected, `handle_error`

is called.

When the loop exits, `num`

will either be empty, or it will contain the last
value. If ```
num is not empty, the last number is converted to an integer and
appended to the vector
```

v`.

Finally, the vector is returned to the caller.

```
int check(string s)
{
int x1 = 0, x2 = s.size() - 1;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != ' ')
{
x1 = i;
break;
}
}
for (int i = s.size() - 1; i >= x1; i--)
{
if (s[i] != ' ')
{
x2 = i;
break;
}
}
for (int i = x1; i <= x2; i++)
{
if (s[i] == ' ')
{
handle_error();
}
}
return stoi(s);
}
```

This function is giving a string containing an individual value. It strips
off leading and trailing spaces. If there is no valid value, `handle_error`

is called.

In our sample, this function is responsible for sorting the array according to the insertion sort algorithm:

```
void insertion_sort(string str, vector<int> arr)
{
stringstream ss;
ss << str;
string temp;
int found;
while (!ss.eof())
{
ss >> temp;
if (stringstream(temp) >> found)
{
arr.push_back(found);
}
temp = "";
}
int t,j;
for(int i=1;i<arr.size();i++){
t = arr[i];
j = i-1;
while(j >= 0 && t<=arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = t;
}
int i;
for (i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
```

Following are the explanation for the respective code snippets.

```
stringstream ss;
ss << str;
string temp;
int found;
while (!ss.eof())
{
ss >> temp;
if (stringstream(temp) >> found)
{
arr.push_back(found);
}
temp = "";
}
```

This section is responsible for extracting the numbers from the string and adding them to a vector, so that easy iterative approach to insertion sort can be used.

```
int t,j;
for(int i=1;i<arr.size();i++){
t = arr[i];
j = i-1;
while(j >= 0 && t<=arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = t;
}
```

This section accepts the input array and the size of the array from the `main`

function
Here we virtually divide the array into two parts i.e., the sorted and the unsorted part,
initially, the first element in the array is considered as sorted, even if it is not sorted.
Further, each element in the array is checked with the previous elements for the strict
inequality with each iteration, the sorting algorithm removes one element at a time and
finds the appropriate location within the sorted array and inserts it there. The iteration
continues until the unsorted array is empty, and get's it finally sorted.

Above you can see, that the variable `t`

holds the unsorted array's first element and `j`

here keeps track of the index of the last element of the sorted array. Now we iterate
throughout the remaining unsorted array one by one, finding a relevant position for the
the value stored in 't' throughout the sorted array, as soon we get the desired location we
place it there and then increment the sorted array end marker 'i' by unity.
This process continues until the array unsorted array size is reduced to zero.

It's quite self-explanatory that it displays the new altered array:

```
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
```

It takes the altered array and then prints it by iterating through it.

This function swaps two values `x`

and `y`

. It is used for as part of the insertion sort
algorithm:

```
void swap(int *x, int *y)
{
int t = *x;
*x = *y;
*y = t;
}
```

As usual, C++ programs cannot be executed without a `main`

function:

```
int main(int argc, char *argv[])
{
...
}
```

The first part of the `main`

function validates the number of command-line
arguments. If there are too few, `handle_error`

is called.

```
if (argc < 2)
{
handle_error();
}
```

Next, the command-line argument is converted to a vector of integer values. If there are too few values, the usage statement is displayed and the program exits:

```
vector<int> v = convert(argv[1]);
if (v.size() < 2)
{
cout << "Usage: please provide a list of at least two integers to sort in the format \"1, 2, 3, 4, 5\"" << endl;
exit(0);
}
```

In our sample, this function is responsible for sorting the array according to the insertion sort algorithm:

```
int n = v.size();
int min_idx;
for (int i = 0; i < n - 1; i++)
{
min_idx = i;
for (int j = i + 1; j < n; j++)
{
if (v[j] < v[min_idx])
{
min_idx = j;
}
}
swap(v[min_idx], v[i]);
}
```

Here we virtually divide the array into two parts: the sorted and the unsorted part. Initially, the first element in the array is considered as sorted, even if it is not sorted. Further, each element in the array is checked with the previous elements for the strict inequality with each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the unsorted array is empty, and get's it finally sorted.

Above you can see, that the variable `min_index`

starts out as the index of the sorted
array's first element (`i`

). The variable `j`

loops over the unsorted portion of the array.
By the end of the `for j`

loop, `min_index`

contains the index of the minimum unsorted
value. The `swap`

function swaps the minimum value in the unsorted portion of the array
at `min_index`

with the current value in the sorted portion of the array at `i`

.

We continue to iterate `i`

until the array is sorted.

Finally, the sorted vector is displayed:

```
for (int i = 0; i < n - 1; i++)
{
cout << v[i] << ", ";
}
cout << v[n - 1];
```

And that's it!

One can run the code on C++ IDE's like CodeBlocks, Turboc++, Eclipse for C/C++, etc. Their installation is guided by the setup wizards and once install can allow you to run the locally on your machine, all these IDE's are available free of cost on their respective websites.

Perhaps the easiest way to run the solution is to leverage the online gdb compiler.

Alternatively, you can try to run the C++ code in a similar way described in the last article. Honestly, it's pretty easy to write and run C/C++ code on most platforms:

```
gcc -o insertion-sort reverse-string.cpp
```

Unfortunately, Windows pretty much requires the use of Visual Studio. So, instead of sharing platform-specific directions, I'll fall back on my online compiler recommendation.