Skip to main content

Python Insertion Sort

Here you’ll learn about Python insertion sort algorithm.

In terms of performance Insertion sort is not the best sorting algorithm. But it is little bit more efficient then the Selection sort and Bubble sort.

To understand the Insertion Sort algorithm easily, we’ll start with an example.

Also Read: Python Selection Sort

Python Insertion Sort

Example

Let’s say we have an array [14,5,18,6,21].

Assume that we have two parts in this array first one is sorted and another one is unsorted.

Python Insertion Sort 1

The  sorted part of array is in the left of orange line and unsorted part is in the right side.

Now all we have to do is pick each element one by one from the unsorted part and add it into the sorted array at its appropriate place.

Python Insertion Sort 2

14 is the only element in our sorted part so it is already sorted.

Now pick the first element from the unsorted part and add it to the sorted part.

Python Insertion Sort 3

As 5 is less than 14 so 14 have to right shift by one place.

Again pick first element from unsorted part and add it into in sorted part.

Python Insertion Sort 4

18 is greater than 14 and there is no need to shifting.

Repeating same

Python Insertion Sort 5

6 is greater than 5 and less than 14.

So we have to right shift 14 and 18 by one place.

At last

Python Insertion Sort 6

21 is greater than 18 doesn’t need to shift. Done.

Algorithm

We have an array ‘Arr[]’ with n elements

Step 1:  set i = 1

Step 2: set value = Arr[i]

Set position = i

Step3 :  if position > 0 and Arr[position-1]>value

Arr[position] = Arr[position-1]

Position = position -1

[Repeat this step until condition become false]

Step 4: Arr[position] = value

Step 5: goto step 2 for (n-1) times.

Program for Insertion Sort in Python

Arr = [5,14,18,6,21]
n= len(Arr)
i = 1
while (i<=n-1):
  value = Arr[i]
  position = i

  while (position>0 and Arr[position-1]>value):
    Arr[position] = Arr[position-1]
    position = position -1 

  i = i+1       
  Arr[position] = value


for i in Arr:
  print i,

Output

5 6 14 18 21

Comment below if you have any queries related to above python insertion sort algorithm.

The post Python Insertion Sort appeared first on The Crazy Programmer.



from The Crazy Programmer https://www.thecrazyprogrammer.com/2017/11/python-insertion-sort.html
Labels:

Comments

Post a Comment

Popular posts from this blog

dotnet sdk list and dotnet sdk latest

Can someone make .NET Core better with a simple global command? Fanie Reynders did and he did it in a simple and elegant way. I'm envious, in fact, because I spec'ed this exact thing out in a meeting a few months ago but I could have just done it like he did and I would have used fewer keystrokes! Last year when .NET Core was just getting started, there was a "DNVM" helper command that you could use to simplify dealing with multiple versions of the .NET SDK on one machine. Later, rather than 'switching global SDK versions,' switching was simplified to be handled on a folder by folder basis. That meant that if you had a project in a folder with no global.json that pinned the SDK version, your project would use the latest installed version. If you liked, you could create a global.json file and pin your project's folder to a specific version. Great, but I would constantly have to google to remember the format for the global.json file, and I'd constan
Post a Comment
Read more

R vs Python for Machine Learning

There are so many things to learn before to choose which language is good for Machine Learning. We will discuss each and everything about R as well as Python and the situation or problem in which situation we have to use which language. Let’s start Python and R are the two most Commonly used Programming Languages for Machine Learning and because of the popularity of both the languages Novice or you can say fresher are getting confused, whether they should choose R or Python language to commence their career in the Machine learning domain. Don’t worry guys through this article we will discuss R vs Python for Machine Learning. So, without exaggerating this article let’s get started. We will start it from the very Basics things or definitions. R vs Python for Machine Learning Introduction R is a programming language made by statisticians and data miners for statistical analysis and graphics supported by R foundation for statistical computing. R also provides high-quality graphics and
1 comment
Read more

Top Tips For PCB Design Layout

Are you thinking about designing a printed circuit board? PCBs are quite complicated, and you need to make sure that the layout that you choose is going to operate as well as you want it to. For this reason, we have put together some top tips for PCB design layout. Keep reading if you would like to find out more about this. Leave Enough Space One of the most important design tips for PCB layout is that you need to make sure that you are leaving enough space between the components. While many people might think that packing components closely is the best route to take, this can cause problems further down the line. This is why we suggest leaving extra space for the wires that will spread. This way, you’ll have the perfect PCB design layout. Print Out Your Layout Struggling to find out if your components sizes match? Our next tip is to print out your layout and compare the printed version to your actual components. Datasheets can sometimes come with errors, so it doesn’t hurt to do
1 comment
Read more