Insertion Sort Program code in C

Insertion sort in C is one of the sorting technique used to sort a data structure like an array.

The general idea of the insertion sort is to partition array into two parts

  1. Sorted Partition
  2. Unsorted Partition.

As the sorting progress, the sorted partition grows and the unsorted portion shrinks. And finally, we get a sorted array.

Algorithm

At the start. The array is unsorted.

So we assume the first element (array[0]) to be sorted. And rest of the elements are unsorted.

Now we compare first element (array[0]) with the second element (array[1]) of the array. And arrange them accordingly.

Now we have first two elements sorted.

Again we repeat the process with the third element of the array.

By doing this sorted partition grows and the array gets finally sorted.

Code

Online Compiler

Output

Insertion Sort in C

  • In-place algorithm (No need of extra arrays).
  • O(n²) time complexity – quardratic.
  • Stable algorithm (Doesn’t interchange same values in the array).

Also look Shell sort in c++. Which is more efficient than insertion sort.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.