insertion sort c code example

Example 1: insertion sort in c

#include<stdio.h>
int main(){

   /* Here i & j for loop counters, temp for swapping,
    * count for total number of elements, number[] to
    * store the input numbers in array. You can increase
    * or decrease the size of number array as per requirement
    */
   int i, j, count, temp, number[25];

   printf("How many numbers u are going to enter?: ");
   scanf("%d",&count);

   printf("Enter %d elements: ", count);
   // This loop would store the input numbers in array
   for(i=0;i<count;i++)
      scanf("%d",&number[i]);

   // Implementation of insertion sort algorithm
   for(i=1;i<count;i++){
      temp=number[i];
      j=i-1;
      while((temp<number[j])&&(j>=0)){
         number[j+1]=number[j];
         j=j-1;
      }
      number[j+1]=temp;
   }

   printf("Order of Sorted elements: ");
   for(i=0;i<count;i++)
      printf(" %d",number[i]);

   return 0;
}

Example 2: insertion sort python

def insertion_sort(lst):
    for i in range(1,len(lst)):
        while i > 0 and lst[i - 1] >lst[i] :
            lst[i - 1], lst[i] = lst[i] , lst[i - 1]
            ## swapping
            i = i -1
    return lst
print(insertion_sort([4,2,2,3,4,3,1,1,1,2]))

Example 3: insertion sort java

Insertion program
public class InsertionSortExample
{
   public void sort(int[] arrNum)
   {
      int number = arrNum.length;
      for(int a = 1; a < number; ++a)
      {
         int keyValue = arrNum[a];
         int b = a - 1;
         while(b >= 0 && arrNum[b] > keyValue)
         {
            arrNum[b + 1] = arrNum[b];
            b = b - 1;
         }
         arrNum[b + 1] = keyValue;
      }
   }
   static void displayArray(int[] arrNum)
   {
      int num = arrNum.length;
      for(int a = 0; a < num; ++a)
      {
         System.out.print(arrNum[a] + " ");
      }
      System.out.println();
   }
   public static void main(String[] args)
   {
      int[] arrInput = { 50, 80, 10, 30, 90, 60 };
      InsertionSortExample obj = new InsertionSortExample();
      obj.sort(arrInput);
      displayArray(arrInput);
   }
}

Example 4: program for insertion sort

# another method similar to insertion sort

def insertionSort(arr):
    for i in range(1, len(arr)):
        k = i
        for j in range(i-1, -1, -1):
            if arr[k] < arr[j]:  # if the key element is smaller than elements before it
                temp = arr[k]  # swapping the two numbers
                arr[k] = arr[j]
                arr[j] = temp

                k = j  # assigning the current index of key value to k
        

arr = [5, 2, 9, 1, 10, 19, 12, 11, 18, 13, 23, 20, 27, 28, 24, -2]

print("original array \n", arr)
insertionSort(arr)
print("\nSorted array \n", arr)

Example 5: insertion sort

// Por ter uma complexidade alta,
// não é recomendado para um conjunto de dados muito grande.
// Complexidade: O(n²) / O(n**2) / O(n^2)
// @see https://www.youtube.com/watch?v=TZRWRjq2CAg
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function insertionSort(vetor) {
    let current;
    for (let i = 1; i < vetor.length; i += 1) {
        let j = i - 1;
        current = vetor[i];
        while (j >= 0 && current < vetor[j]) {
            vetor[j + 1] = vetor[j];
            j--;
        }
        vetor[j + 1] = current;
    }
    return vetor;
}

insertionSort([1, 2, 5, 8, 3, 4])