 C++ Tutorials

# C++ Tutorials

Insertion Sort in C++: Program & Algorithm to Implement. In the insertion sort technique, we start from the second element and compare it with the first element, and put it in a proper place. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands.

## Insertion Sort in C++ using function

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

void insertionSort(int arr[], int n){
for(int i=0; i<=n-1; i++){
int element=arr[i];
//Place the current element at right position in the sorted part
int j=i-1;
while(j>=0 && arr[j]>element){
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=element;
}
}

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cout<<"Enter "<<i+1<<" number of element in the Insertion Sort: ";
cin>>arr[i];
}

insertionSort(arr, n);
for(int i=0; i<n; i++){
cout<<arr[i]<<", ";
}
cout<<endl;

return 0 ;
}``````

## Insertion Sort in C++

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cout<<"Enter "<<i+1<<" number of element in the Insertion Sort: ";
cin>>arr[i];
}

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

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

return 0 ;
}``````

Insertion, Sort Let’s dive right in we’re giving this array, and we want it sorted in increasing order Here’s what we’re going to do. We’ll start at the left and work our way to the right Examining each item and comparing it to the items on its left Will then insert it in the correct position in the array?

You’ll notice that part of our array will be sorted as we progress we’ll mark those items with the green background Let’s begin, and you’ll see what I mean We start it – of course, there are no items to the left of [-] so we mark it assorted Moving on to  we compare it to  and leave it where it is our first two items are now Sorted Next we have five which we can see is out of place We know it needs to be after two so we swap it with eight Our first three items are now sorted on Two-three again, it’s out of place We swap it [with] eight and five until it’s in the correct position We’re at our fifth item 9 and I’m sure you can see that. It’s in the correct spot Let’s move to 4 and insert it in the correct place in the array And that’s it. We’re done insertion. Sort is one of the most straightforward sorting algorithms for your reference.

Here’s the pseudocode Insertion Sort has the worst-case time complexity of big o of n squared where n is the size of the array? for example, when an array starts in decreasing order you need to swap and compare every single item Which leads to big o of N squared?

## Insertion Sort Function

Insertion_sort, that I didn’t necessarily have to do this break. And this is one of those examples that sometimes when you just program something– in the way that, at least, your brain is thinking about it– you don’t always do it in maybe the most elegant way.

And that commenter was right. There was actually maybe a lot more elegant way to actually do this insertion_sort. So over here, if we go into the while loop, I have this while loop happening while i is greater than or equal to 0. But then I want it to essentially break out of that while loop, if the variable value is not less than the i-th element in list. So one way to do this– because really, I’m just defining the parameters on when to do this while loop. Instead of doing this if the value is less than the i-th element, do this and otherwise break. What I could have done– and this would have actually been a more elegant way to do this– while i is greater than or equal to 0 and value is less than the i-th element in list.

So now this is still the same as before. But now I know that value is less than the i-th element in the list. So I will execute this code over here. So I know that this is going to be true. Let me take all of these one level back. And then I don’t have to do an else. And I don’t have to break out of the loop anymore. And so that should simplify the program a good bit. But let’s verify for ourselves that this actually works. So let me save it. And then let me run it. Let me define a list. So I’ll just call it c is equal to 1, 5, 6, 7, 2, 4, 14, and 2. So let’s just define that.

And let’s try our insertion_sort. Insertion_sort on c. So let’s see what we get. So let’s see. Let’s print c now. And there you go. It’s sorted it. So thank you for the comment. I think this does simplify it a little bit. Sometimes you always have to question, especially if you have a while statement, is there a better way instead of using the break. Because that’s essentially– I’m putting a condition on a reason to break out of the while loop.