Insertion Sort in Python


The Insertion sort is a straightforward and more efficient algorithm than the previous bubble sort algorithm. The insertion sort algorithm concept is based on the deck of the card where we sort the playing card according to a particular card. It has many advantages, but there are many efficient algorithms available in the data structure.

While the card-playing, we compare the hands of cards with each other. Most of the player likes to sort the card in the ascending order so they can quickly see which combinations they have at their disposal.

The insertion sort implementation is easy and simple because it’s generally taught in the beginning programming lesson. It is an in-place and stable algorithm that is more beneficial for nearly-sorted or fewer elements.

Another thing to note: Insertion Sort doesn’t need to know the entire array in advance before sorting. The algorithm can receive one element at a time. Which is great if we want to add more elements to be sorted – the algorithm only inserts that element in it’s proper place without “re-doing” the whole sort.

How Insertion Sort Works

The array spilled virtually in the two parts in the insertion sort – An unsorted part and sorted part.

The sorted part contains the first element of the array and other unsorted subpart contains the rest of the array. The first element in the unsorted array is compared to the sorted array so that we can place it into a proper sub-array.

It focuses on inserting the elements by moving all elements if the right-side value is smaller than the left side.

It will repeatedly happen until the all element is inserted at correct place.

To sort the array using insertion sort below is the algorithm of insertion sort.

  • Spilt a list in two parts – sorted and unsorted.
  • Iterate from arr[1] to arr[n] over the given array.
  • Compare the current element to the next element.
  • If the current element is smaller than the next element, compare to the element before, Move to the greater elements one position up to make space for the swapped element.

Let’s understand the following example.

We will consider the first element in the sorted array in the following array.

[10, 4, 25, 1, 5]

The first step to add 10 to the sorted subarray

[10, 4, 25, 1, 5]

Now we take the first element from the unsorted array – 4. We store this value in a new variable temp. Now, we can see that the 10>4 then we move the 10 to the right and that overwrite the 4 that was previously stored.

[10, 10, 25, 1, 5] (temp = 4)

Here the 4 is lesser than all elements in sorted subarray, so we insert it at the first index position.

[4, 10, 25, 1, 5]

We have two elements in the sorted subarray.

Now check the number 25. We have saved it into the temp variable. 25> 10 and also 25> 4 then we put it in the third position and add it to the sorted sub array.

[4, 10, 25, 1, 5]

Again we check the number 1. We save it in temp. 1 is less than the 25. It overwrites the 25.

[4, 10, 25, 25, 5] 10>1 then it overwrites again

[4, 25, 10, 25, 5]

[25, 4, 10, 25, 5] 4>1 now put the value of temp = 1

[1, 4, 10, 25, 5]

Now, we have 4 elements in the sorted subarray. 5<25 then shift 25 to the right side and pass temp = 5 to the left side.

[1, 4, 10, 25, 25] put temp = 5

Now, we get the sorted array by simply putting the temp value.

[1, 4, 5, 10, 25]

The given array is sorted.


Like it? Share with your friends!

What's Your Reaction?

hate hate
0
hate
confused confused
0
confused
fail fail
0
fail
fun fun
0
fun
geeky geeky
0
geeky
love love
0
love
lol lol
0
lol
omg omg
0
omg
win win
0
win
Choose A Format
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Poll
Voting to make decisions or determine opinions
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Countdown
The Classic Internet Countdowns
Open List
Submit your own item and vote up for the best submission
Ranked List
Upvote or downvote to decide the best list item
Meme
Upload your own images to make custom memes
Video
Youtube and Vimeo Embeds
Audio
Soundcloud or Mixcloud Embeds
Image
Photo or GIF
Gif
GIF format