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 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 program to insert an
// element in a sorted array
class 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 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 Code
if __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
using System;
// C# program to insert an
// element in a sorted array
public 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 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;
console.log("\nBefore Insertion: ");
for (var i = 0; i < n; i++)
console.log(arr[i] + " ");
// Inserting key
n = insertSorted(arr, n, key, capacity);
console.log("<br>" +"\nAfter Insertion: ");
for (var i = 0; i < n; i++)
console.log(arr[i] + " ");
// This code is contributed by shivanisinghss2110
// 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
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)
Inserting Elements in an Array | Array Operations
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
Contact Us