The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Insertion Sorting

Insertion sort is a sorting algorithm commonly used in computer programming. It works by dividing the input list into two parts: the sorted and unsorted sections. The first element of the unsorted section is compared to each element of the sorted section until it finds its correct place, after which it is placed at that position. This process continues until all elements have been sorted.
The implementation of insertion sort may vary slightly depending on the programming language being used such as C, C++, Python or Java. For example, in Python, we can use a for loop to iterate through each element and then use another nested loop to compare and swap elements whereas in Java, arrays are typically iterated using a for loop with index range and nested while loops are used for comparisons and swaps.

(a.) C Code

#include <stdio.h>

      void insertionSort(int arr[], int n) {
          for (int i = 1; i < n; i++) {
              int key = arr[i];
              int j = i - 1;
      
              while (j >= 0 && arr[j] > key) {
                  arr[j + 1] = arr[j];
                  j = j - 1;
              }
              arr[j + 1] = key;
          }
      }
      
      void printArray(int arr[], int size) {
          for (int i = 0; i < size; i++) {
              printf("%d ", arr[i]);
          }
          printf("\n");
      }
      
      int main() {
          int arr[] = {12, 11, 13, 5, 6};
          int n = sizeof(arr) / sizeof(arr[0]);
      
          insertionSort(arr, n);
          printf("Sorted array: ");
          printArray(arr, n);
      
          return 0;
      }
Output:-
Sorted array: 5 6 11 12 13

(b.) C++ Code

#include <iostream>
      using namespace std;
      
      void insertionSort(int arr[], int n) {
          for (int i = 1; i < n; i++) {
              int key = arr[i];
              int j = i - 1;
      
              while (j >= 0 && arr[j] > key) {
                  arr[j + 1] = arr[j];
                  j = j - 1;
              }
              arr[j + 1] = key;
          }
      }
      
      void printArray(int arr[], int size) {
          for (int i = 0; i < size; i++) {
              cout << arr[i] << " ";
          }
          cout << endl;
      }
      
      int main() {
          int arr[] = {12, 11, 13, 5, 6};
          int n = sizeof(arr) / sizeof(arr[0]);
      
          insertionSort(arr, n);
          cout << "Sorted array: " << endl;
          printArray(arr, n);
      
          return 0;
      }
Output:-
Sorted array: 5 6 11 12 13

(c.) Python Code

def insertion_sort(arr):
      for i in range(1, len(arr)):
          key = arr[i]
          j = i - 1
          while j >= 0 and key < arr[j]:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key
  
  def print_array(arr):
      for i in arr:
          print(i, end=" ")
      print()
  
  arr = [12, 11, 13, 5, 6]
  insertion_sort(arr)
  print("Sorted array:")
  print_array(arr)
Output:-
Sorted array: 5 6 11 12 13

(d.) Java Code

public class InsertionSort {
      void insertionSort(int arr[]) {
          int n = arr.length;
          for (int i = 1; i < n; ++i) {
              int key = arr[i];
              int j = i - 1;
  
              while (j >= 0 && arr[j] > key) {
                  arr[j + 1] = arr[j];
                  j = j - 1;
              }
              arr[j + 1] = key;
          }
      }
  
      static void printArray(int arr[]) {
          int n = arr.length;
          for (int i = 0; i < n; ++i) {
              System.out.print(arr[i] + " ");
          }
          System.out.println();
      }
  
      public static void main(String args[]) {
          int arr[] = {12, 11, 13, 5, 6};
          InsertionSort ob = new InsertionSort();
          ob.insertionSort(arr);
          System.out.println("Sorted array:");
          printArray(arr);
      }
  }
Output:-
Sorted array: 5 6 11 12 13

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎