In this post, we will look into insertion operation in an Array, i.e., how to insert into an Array, such as:
- Inserting Elements in an Array at the End
- Inserting Elements in an Array at any Position in the Middle
- Inserting Elements in a Sorted Array
1. Inserting Elements in an Array at the End
In an unsorted array, the insert operation is faster as compared to a sorted array because we don’t have to care about the position at which the element is to be placed.
Coding implementation of inserting an element at the end:
C++
#include<bits/stdc++.h>// Include the C++ input/output library using namespace std; //Using the standard namespace for convenience // Function to insert a key into an array int insertSorted(int arr[], int n, int key, int capacity) { // Check if the array is already full if (n >= capacity) return n; // Add the key at the end of the array arr[n] = key; // Return the updated size of the array return (n + 1); } int main() { int arr[20] = {12, 16, 20, 40, 50, 70}; int capacity = sizeof(arr) / sizeof(arr[0]); int n = 6; int i, key = 26; cout << "\n Before Insertion: "; for (i = 0; i < n; i++) cout << arr[i] << " "; // Inserting the key into the array n = insertSorted(arr, n, key, capacity); cout << "\n After Insertion: "; for (i = 0; i < n; i++) cout << arr[i] << " "; return 0; //This code is contributed by Dhruv kumar} |
C
// C program to implement insert// operation in an unsorted array.#include <stdio.h>// Inserts a key in arr[] of given capacity.// n is current size of arr[]. This// function returns n + 1 if insertion// is successful, else n.int insertSorted(int arr[], int n, int key, int capacity){ // Cannot insert more elements if n is // already more than or equal to capacity if (n >= capacity) return n; arr[n] = key; return (n + 1);}// Driver Codeint main(){ int arr[20] = { 12, 16, 20, 40, 50, 70 }; int capacity = sizeof(arr) / sizeof(arr[0]); int n = 6; int i, key = 26; printf("\n Before Insertion: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); // Inserting key n = insertSorted(arr, n, key, capacity); printf("\n After Insertion: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0;} |
Java
// Java program to implement insert// operation in an unsorted array.class Main { // Function to insert a given key in // the array. This function returns n+1 // if insertion is successful, else n. static int insertSorted(int arr[], int n, int key, int capacity) { // Cannot insert more elements if n // is already more than or equal to // capacity if (n >= capacity) return n; arr[n] = key; return (n + 1); } // Driver Code public static void main(String[] args) { int[] arr = new int[20]; arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; int capacity = 20; int n = 6; int i, key = 26; System.out.print("Before Insertion: "); for (i = 0; i < n; i++) System.out.print(arr[i] + " "); // Inserting key n = insertSorted(arr, n, key, capacity); System.out.print("\n After Insertion: "); for (i = 0; i < n; i++) System.out.print(arr[i] + " "); }} |
Python3
# Python program for inserting# an element in an unsorted array# method to insert elementdef insert(arr, element): arr.append(element)# Driver's codeif __name__ == '__main__': # declaring array and key to insert arr = [12, 16, 20, 40, 50, 70] key = 26 # array before inserting an element print("Before Inserting: ") print(arr) # array after Inserting element insert(arr, key) print("After Inserting: ") print(arr) # Thanks to Aditi Sharma for contributing # this code |
C#
// C# program to implement insert// operation in an unsorted array.using System;class main { // Function to insert a given // key in the array. This // function returns n + 1 // if insertion is successful, // else n. static int insertSorted(int[] arr, int n, int key, int capacity) { // Cannot insert more elements // if n is already more than // or equal to capacity if (n >= capacity) return n; arr[n] = key; return (n + 1); } // Driver Code public static void Main() { int[] arr = new int[20]; arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; int capacity = 20; int n = 6; int i, key = 26; Console.Write("Before Insertion: "); for (i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); // Inserting key n = insertSorted(arr, n, key, capacity); Console.Write("After Insertion: "); for (i = 0; i < n; i++) Console.Write(arr[i] + " "); }}// This code is contributed by vt_m. |
Javascript
// Javascript program to implement insert // operation in an unsorted array. // Function to insert a given // key in the array. This // function returns n + 1 // if insertion is successful, // else n. function insertSorted(arr, n, key, capacity) { // Cannot insert more elements // if n is already more than // or equal to capacity if (n >= capacity) return n; arr[n] = key; return (n + 1); } let arr = new Array(20); arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; let capacity = 20; let n = 6; let i, key = 26; document.write("Before Insertion: "); for (i = 0; i < n; i++) console.log(arr[i]+" "); console.log("</br>"); // Inserting key n = insertSorted(arr, n, key, capacity); document.write("After Insertion: "); for (i = 0; i < n; i++) console.log(arr[i]+" "); |
PHP
<?php// PHP program to implement insert // operation in an unsorted array. // Inserts a key in arr[] of given // capacity. n is current size of arr[]. // This function returns n + 1 if // insertion is successful, else n. function insertSorted(&$arr, $n, $key, $capacity) { // Cannot insert more elements if n is // already more than or equal to capacity if ($n >= $capacity) return $n; array_push($arr, $key); return ($n + 1); } // Driver Code$arr = array(12, 16, 20, 40, 50, 70); $capacity = 20; $n = 6; $key = 26; echo "Before Insertion: "; for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; // Inserting key $n = insertSorted($arr, $n, $key, $capacity); echo "\nAfter Insertion: "; for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; // This code is contributed by// Rajput-Ji?> |
Output
Before Insertion: 12 16 20 40 50 70 After Insertion: 12 16 20 40 50 70 26
Time Complexity: O(n)
Auxiliary Space: O(1)
Let’s break down the time and space complexity of the provided code step by step:
1. **Array Initialization:**
– The array `arr` is initialized with 20 elements.
– This takes O(1) time and O(20) space, which simplifies to O(1) space.
2. **Array Size Calculation:**
– The size of the array (`capacity`) is calculated using `sizeof(arr) / sizeof(arr[0])`.
– This takes O(1) time.
3. **Loop to Print the Array:**
– There is a loop to print the elements of the array, which has a constant number of iterations (6 in this case).
– This takes O(n) time, where n is the number of elements in the array.
4. **Insertion Function (`insertSorted`):**
– The insertion function itself is very simple and consists of constant time operations:
– Checking if the array is full (`n >= capacity`) takes O(1) time.
– Assigning the key to the array at the end and updating `n` takes O(1) time.
5. **Loop to Print the Array After Insertion:**
– Similar to the loop before insertion, this loop has a constant number of iterations (n + 1 in this case).
– This takes O(n) time.
Therefore, the overall time complexity of the code is dominated by the loop iterations for printing the array, and the insertion and checking operations are constant time. Hence, the time complexity is O(n).
In terms of space complexity, the code uses a constant amount of extra space for variables (`i`, `key`, `capacity`) and the array itself. Thus, the space complexity is O(1).
To summarize:
– Time Complexity: O(n)
– Space Complexity: O(1)
2. Inserting Elements in an Array at any Position
Insert operation in an array at any position can be performed by shifting elements to the right, which are on the right side of the required position
Coding implementation of inserting an element at any position:
C++
// C++ Program to Insert an element// at a specific position in an Array#include <bits/stdc++.h>using namespace std;// Function to insert element// at a specific positionvoid insertElement(int arr[], int n, int x, int pos){ // shift elements to the right // which are on the right side of pos for (int i = n - 1; i >= pos; i--) arr[i + 1] = arr[i]; arr[pos] = x;}// Driver's codeint main(){ int arr[15] = { 2, 4, 1, 8, 5 }; int n = 5; cout << "Before insertion : "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; int x = 10, pos = 2; // Function call insertElement(arr, n, x, pos); n++; cout << "After insertion : "; for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0;} |
C
// C Program to Insert an element// at a specific position in an Array#include <stdio.h>// Function to insert element// at a specific positionvoid insertElement(int arr[], int n, int x, int pos){ // shift elements to the right // which are on the right side of pos for (int i = n - 1; i >= pos; i--) arr[i + 1] = arr[i]; arr[pos] = x;}// Driver's codeint main(){ int arr[15] = { 2, 4, 1, 8, 5 }; int n = 5; printf("Before insertion : "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); int x = 10, pos = 2; // Function call insertElement(arr, n, x, pos); n++; printf("After insertion : "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;// Java Program to Insert an element// at a specific position in an Arrayclass GFG { static void insertElement(int arr[], int n, int x, int pos) { // shift elements to the right // which are on the right side of pos for (int i = n - 1; i >= pos; i--) arr[i + 1] = arr[i]; arr[pos] = x; } public static void main(String[] args) { int arr[] = new int[15]; arr[0] = 2; arr[1] = 4; arr[2] = 1; arr[3] = 8; arr[4] = 5; int n = 5; int x = 10, pos = 2; System.out.print("Before Insertion: "); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); // Inserting key at specific position insertElement(arr, n, x, pos); n += 1; System.out.print("\n\nAfter Insertion: "); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }}// This code is contributed by syedsarfarazahammed |
Python3
# python Program to Insert an element# at a specific position in an Arraydef insertElement(arr, n, x, pos): # shift elements to the right # which are on the right side of pos for i in range(n-1, pos-1, -1): arr[i + 1] = arr[i] arr[pos] = x# Driver's codeif __name__ == '__main__': # Declaring array and key to delete # here -1 is for empty space arr = [2, 4, 1, 8, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1] n = 5 print("Before insertion : ") for i in range(0, n): print(arr[i], end=' ') print("\n") x = 10 pos = 2 # Function call insertElement(arr, n, x, pos) n += 1 print("After insertion : ") for i in range(0, n): print(arr[i], end=' ') # This Code is contributed by aditya942003patil |
C#
// C# program to implement insert// operation in an unsorted array.using System;class main { static void insertElement(int[] arr, int n, int x, int pos) { // shift elements to the right // which are on the right side of pos for (int i = n - 1; i >= pos; i--) arr[i + 1] = arr[i]; arr[pos] = x; } public static void Main() { int[] arr = new int[20]; arr[0] = 2; arr[1] = 4; arr[2] = 1; arr[3] = 8; arr[4] = 5; int x = 10; int n = 5; int pos = 2; Console.Write("Before Insertion: "); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); // Inserting key at specific position insertElement(arr, n, x, pos); n += 1; Console.Write("\n\nAfter Insertion: "); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); }}// This code is contributed by sourabhdalal0001 |
Javascript
// javascript Program to Insert an element// at a specific position in an Array function insertElement(arr, n, x, pos) { // shift elements to the right // which are on the right side of pos var i = n - 1; for (i; i >= pos; i--) { arr[i + 1] = arr[i]; } arr[pos] = x; } var arr = Array(15).fill(0); arr[0] = 2; arr[1] = 4; arr[2] = 1; arr[3] = 8; arr[4] = 5; var n = 5; var x = 10; var pos = 2; console.log("Before Insertion: "); var i = 0; for (i; i < n; i++) { console.log(arr[i] + " "); } // Inserting key at specific position insertElement(arr, n, x, pos); n += 1; console.log("\n\nAfter Insertion: "); i = 0; for (i; i < n; i++) { console.log(arr[i] + " "); } // This code is contributed by sourabhdalal0001. |
PHP
<?php// Function to insert element at a specific positionfunction insertElement(&$arr, $n, $x, $pos) { // shift elements to the right which are on the right side of pos for ($i = $n - 1; $i >= $pos; $i--) { $arr[$i + 1] = $arr[$i]; } // insert the new element at the specified position $arr[$pos] = $x;}// Driver's code$arr = array(2, 4, 1, 8, 5);$n = 5;echo "Before insertion : ";for ($i = 0; $i < $n; $i++) { echo $arr[$i] . " ";}echo "\n";$x = 10;$pos = 2;// Function callinsertElement($arr, $n, $x, $pos);$n++;echo "After insertion : ";for ($i = 0; $i < $n; $i++) { echo $arr[$i] . " ";}?> |
Output
Before insertion : 2 4 1 8 5 After insertion : 2 4 10 1 8 5
Time complexity: O(N)
Auxiliary Space: O(1)
3. Inserting Elements in a Sorted Array
In a sorted array, a search operation is performed for the possible position of the given element by using Binary search, and then an insert operation is performed followed by shifting the elements. And in an unsorted array, the insert operation is faster as compared to the sorted array because we don’t have to care about the position at which the element is placed.
Below is the implementation of the above approach:
C++
// C++ program to implement insert operation in// an sorted array.#include <bits/stdc++.h>using namespace std;// Inserts a key in arr[] of given capacity. n is current// size of arr[]. This function returns n+1 if insertion// is successful, else n.int insertSorted(int arr[], int n, int key, int capacity){ // Cannot insert more elements if n is already // more than or equal to capacity if (n >= capacity) return n; int i; for (i = n - 1; (i >= 0 && arr[i] > key); i--) arr[i + 1] = arr[i]; arr[i + 1] = key; return (n + 1);}/* Driver code */int main(){ int arr[20] = { 12, 16, 20, 40, 50, 70 }; int capacity = sizeof(arr) / sizeof(arr[0]); int n = 6; int i, key = 26; cout << "\nBefore Insertion: "; for (i = 0; i < n; i++) cout << arr[i] << " "; // Function call n = insertSorted(arr, n, key, capacity); cout << "\nAfter Insertion: "; for (i = 0; i < n; i++) cout << arr[i] << " "; return 0;}// This code is contributed by SHUBHAMSINGH10 |
C
// C program to implement insert operation in// an sorted array.#include <stdio.h>// Inserts a key in arr[] of given capacity. n is current// size of arr[]. This function returns n+1 if insertion// is successful, else n.int insertSorted(int arr[], int n, int key, int capacity){ // Cannot insert more elements if n is already // more than or equal to capacity if (n >= capacity) return n; int i; for (i = n - 1; (i >= 0 && arr[i] > key); i--) arr[i + 1] = arr[i]; arr[i + 1] = key; return (n + 1);}/* Driver code */int main(){ int arr[20] = { 12, 16, 20, 40, 50, 70 }; int capacity = sizeof(arr) / sizeof(arr[0]); int n = 6; int i, key = 26; printf("\nBefore Insertion: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); // Function call n = insertSorted(arr, n, key, capacity); printf("\nAfter Insertion: "); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0;} |
Java
// Java program to insert an// element in a sorted arrayclass Main { // Inserts a key in arr[] of given // capacity. n is current size of arr[]. // This function returns n+1 if insertion // is successful, else n. static int insertSorted(int arr[], int n, int key, int capacity) { // Cannot insert more elements if n is already // more than or equal to capacity if (n >= capacity) return n; int i; for (i = n - 1; (i >= 0 && arr[i] > key); i--) arr[i + 1] = arr[i]; arr[i + 1] = key; return (n + 1); } /* Driver code */ public static void main(String[] args) { int arr[] = new int[20]; arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; int capacity = arr.length; int n = 6; int key = 26; System.out.print("\nBefore Insertion: "); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); // Function call n = insertSorted(arr, n, key, capacity); System.out.print("\nAfter Insertion: "); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }} |
Python3
# Python3 program to implement insert# operation in an sorted array.# Inserts a key in arr[] of given capacity.# n is current size of arr[]. This function# returns n+1 if insertion is successful, else n.def insertSorted(arr, n, key, capacity): # Cannot insert more elements if n is # already more than or equal to capacity if (n >= capacity): return n i = n - 1 while i >= 0 and arr[i] > key: arr[i + 1] = arr[i] i -= 1 arr[i + 1] = key return (n + 1)# Driver Codeif __name__ == "__main__": arr = [12, 16, 20, 40, 50, 70] for i in range(20): arr.append(0) capacity = len(arr) n = 6 key = 26 print("Before Insertion: ", end=" ") for i in range(n): print(arr[i], end=" ") # Function call n = insertSorted(arr, n, key, capacity) print("\nAfter Insertion: ", end="") for i in range(n): print(arr[i], end=" ")# This code is contributed by Mohit Kumar |
C#
using System;// C# program to insert an// element in a sorted arraypublic class GFG { // Inserts a key in arr[] of given // capacity. n is current size of arr[]. // This function returns n+1 if insertion // is successful, else n. public static int insertSorted(int[] arr, int n, int key, int capacity) { // Cannot insert more elements if n is already // more than or equal to capacity if (n >= capacity) { return n; } int i; for (i = n - 1; (i >= 0 && arr[i] > key); i--) { arr[i + 1] = arr[i]; } arr[i + 1] = key; return (n + 1); } /* Driver code */ public static void Main(string[] args) { int[] arr = new int[20]; arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; int capacity = arr.Length; int n = 6; int key = 26; Console.Write("\nBefore Insertion: "); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } // Function call n = insertSorted(arr, n, key, capacity); Console.Write("\nAfter Insertion: "); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } }}// This code is contributed by Shrikant13 |
Javascript
// JavaScript program to insert an// element in a sorted array // Inserts a key in arr[] of given // capacity. n is current size of arr[]. // This function returns n+1 if insertion // is successful, else n. function insertSorted( arr, n, key, capacity) { // Cannot insert more elements if n is already // more than or equal to capacity if (n >= capacity) return n; var i; for (i = n - 1; (i >= 0 && arr[i] > key); i--) arr[i + 1] = arr[i]; arr[i + 1] = key; return (n + 1); } /* Driver program to test above function */ var arr = new Array(20); arr[0] = 12; arr[1] = 16; arr[2] = 20; arr[3] = 40; arr[4] = 50; arr[5] = 70; var capacity = arr.length; var n = 6; var key = 26; document.write("\nBefore Insertion: "); for (var i = 0; i < n; i++) console.log(arr[i] + " "); // Inserting key n = insertSorted(arr, n, key, capacity); document.write("<br>" +"\nAfter Insertion: "); for (var i = 0; i < n; i++) console.log(arr[i] + " "); // This code is contributed by shivanisinghss2110 |
Output
Before Insertion: 12 16 20 40 50 70 After Insertion: 12 16 20 26 40 50 70
Time Complexity: O(N) [In the worst case all elements may have to be moved]
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
