Arrays in C/C++ : Part 2

Arrays in C/C++ : Part 2
Arrays in C/C++ : Part 2

Introduction

This blog will discuss the operations that we can perform on Arrays in C/C++ programming languages. If you have prior knowledge of Arrays, you may proceed further.

Okay, now let’s get started with Operations on Arrays in C/C++.

Operations on Arrays in C/C++

Insertion:- Insert an element at a particular index in an array.

Consider an array with 5 indices from 0 to 4, and each index is currently holding fruits like a watermelon, a strawberry, a mango, a banana, and a pear. Say hi to all of them!

illustrative_diagram

Suppose we want to add a new fruit pineapple from the basket at index 2. To accommodate pineapple at index 2, firstly, we need to make this index accessible. So, we will have to shift mango, banana, and pear to the right side by one position. 

illustrative_diagram

Secondly, we need a new location to add pineapple. So, we take a new index 5 and shift pear to this index. This way, index 4 is free now. We go on shifting all the fruits until we reach index 2. Now, the pineapple can be added to the empty index 2. That’s how the Insertion takes place in Arrays.

illustrative_diagram

Now let’s see the Implementation for the insertion in arrays:

C

#include<stdio.h>
  
void insert(int arr[], int N, int pos, int element)
{
    N=N+1;
    for(int i=N;i>pos;i--){
        arr[i]=arr[i-1];
    }
    arr[pos]=element;
}
int printArray(int arr[], int N){
    printf("Resultant array \n");
    for(int i = 0; i <= N; i++)
        printf("%d ",arr[i]);
}

int main()
{
    int N;
    printf("Enter the size of an array \n");
    scanf("%d",&N);

    int arr[N], pos, element;
    printf("Enter the elements \n");
    for(int i = 0; i < N; i++)
        scanf("%d",&arr[i]);
    printf("Enter the position(0 - Based Indexed) and the element you want to insert \n");
    scanf("%d%d",&pos, &element);
    if(pos < N){
        insert(arr, N, pos, element);
        printArray(arr, N);
    }
    else {
        printf("Please enter the valid position from  0 to %d \n",N);
        scanf("%d",&pos);
        insert(arr, N, pos, element);
        printArray(arr, N);
    }
    
    return 0;
}

Output

Enter the size of an array
4
Enter the elements
56 4 9 87 
Enter the position(0 - Based Indexed) and the element you want to insert
2  60
Resultant Array
56 4 60 9 87

C++

#include<iostream>
using namespace std;
void insert(int arr[], int N, int pos, int element)
{
    N=N+1;
    for(int i=N;i>pos;i--){
        arr[i]=arr[i-1];
    }
    arr[pos]=element;
}
int printArray(int arr[], int N){
    cout<<"Resultant array"<<endl;
    for(int i = 0; i <= N; i++)
        cout<<arr[i]<<" ";
}

int main()
{
    int N;
    cout<<"Enter the size of an array"<<endl;
    cin>>N;

    int arr[N], pos, element;
    cout<<"Enter the elements"<<endl;
    for(int i = 0; i < N; i++)
        cin>>arr[i];
    cout<<"Enter the position(0 - Based Indexed) and the element you want to insert"<<endl;
    cin>>pos>>element;
    if(pos < N){
        insert(arr, N, pos, element);
        printArray(arr, N);
    }
    else{
        cout<<"Enter the valid index from 0 to "<<N<<endl;
        cin>>pos;
        insert(arr, N, pos, element);
        printArray(arr, N);
    }
    return 0;
}

Output

blog banner 1
Enter the size of an array 
3
Enter the elements
56 34 98
Enter the position(0 - Based Indexed) and the element you want to insert
0 35
Resultant array
35 56 34 98

Let’s analyse the time complexities in each aspect.

  • Best Case: O(1), when the user wants to insert the element in the last or the size of an array equals the position.
  • Average Case: O(N), when the user wants to insert the element at any particular position.
  • Worst Case: O(N), when the user wants to insert the element at the first index.

Searching:- Find the element in an Array.

 In Arrays, we have two types of Searching algorithms.

  1. Linear Search- “The linear search is a very elementary algorithm. Sometimes it’s also called sequential search, as it uses a loop to step through an array sequentially. It compares each element with the value being searched and stops when either the value is found, or we reach the end of the array.
  1. Binary Search– Binary search is an efficient algorithm for finding an item from a sorted array. It follows the divide and conquers approach in which the array is divided into two halves, and the item is compared with the middle element of the array. If the match is found then, the location of the middle element is returned. Otherwise, we search this item into either of the halves depending on the match’s result.

In this tutorial, we will be looking at the Sequential Search, i.e., Linear Search.

illustrative_diagram

In the above representation, we aim to search the element with the value “89”; 

First, the control will check with the first element’s value,i.e. 7, which does not equal our target value. Then the control will jump to the other values until it finds the actual value that matches the target value. In this example, the actual value is present at the 3rd index. After encountering the actual value, we simply return the position and terminate from the loop.

Now, Let’s see the Implementation of Linear Search:

C

#include<stdio.h>
  
int search(int arr[], int N, int key)
{
    for(int i=0;i<N;i++){
        if(arr[i]==key){
            return i;
        }
    }
    // If the key to be searched is not found
    return -1;
}

int main()
{
    int N;
    printf("Enter the array size \n");
    scanf("%d",&N);

    int i, arr[N], key;
    printf("Enter the array elements \n");
    for(i = 0; i < N; i++)
        scanf("%d",&arr[i]);
    printf("Enter the element you want to search \n");
    scanf("%d",&key);
    
    printf("The position of element in array: ");
    printf("%d",search(arr,N,key));

    return 0;
}

Output

Enter the array size
4
Enter the array elements
123 87 65 43
Enter the element you want to search
43
The position of element in array: 3

C++

#include<bits/stdc++.h>
using namespace std;
int search(int arr[], int N, int key)
{
    for(int i=0;i<N;i++){
        if(arr[i]==key){
            return i;
        }
    }
    // If the key to be searched is not found
    return -1;
}

int main()
{
    int N;
    cout<<"Enter the array size"<<endl;
    cin>>N;

    int i, arr[N], key;
    cout<<"Enter the array elements"<<endl;
    for(i = 0; i < N; i++)
        cin>>arr[i];
    cout<<"The position of element in array: ";
    cin>>key;

    cout<<search(arr,N,key);

    return 0;
}

Output

Enter the array size
5
Enter the array elements
4 5 6 7 8
Enter the element you want to search
5
The position of element in array: 1

Let’s analyse the time complexities in each aspect.

  • Best Case: O(1), when the element is found at the first index.
  • Average Case: O(N), when the element is located at some other index in an array.
  • Worst Case: O(N), when the element is found at the last index or not found in the list.

Deletion:- Remove a specific element in an Array

To understand the deletion operation, let’s retake the fruit’s example. In Insertion, we shift the elements to their right side, whereas, Deletion works oppositely. 

Suppose we want to delete Mango from the list.

illustrative_diagram

Firstly, we require the position where the user wants to remove the element. In the above example, the index where the mango is present is 2. To remove mango, we need to shift its next immediate position to its position (i.e. its left position).

array[i] = array[i+1]; // where i = 2 and i+1 = 3

To maintain the sequence, we need to shift the rest of the elements to their left side so there will be no vacant space within the array. Lastly, the array size will be decremented by one as the last block will now be empty.

illustrative_diagram

 Let’s see the Implementation for Deletion in arrays:

C

#include <stdio.h>

int main()
{
    int n;
    
    printf("Enter the number of elements in the array\n");
    scanf("%d", &n);
    printf("Enter %d elements\n", n);
    int array[n];
    for ( int c = 0 ; c < n ; c++ )
        scanf("%d", &array[c]);
    
    printf("Enter the location(0 - Based Indexed) where you wish to delete element\n");
    int pos;
    scanf("%d", &pos);
    
    if ( pos >= n )    
       printf("Deletion not possible.\n");
    
    else
    {    
        for ( int c = pos ; c < n - 1 ; c++ ) 
            array[c] = array[c+1];        
        
        printf("Resultant array is\n");
        
        for( int c = 0 ; c < n - 1 ; c++ )        
                printf("%d ", array[c]);        
    }    
    return 0;
}

Output

Enter the number of elements in the array
4
Enter 4 elements
56 4 6 7
Enter the location(0 - Based Indexed) where you wish to delete element
2
Resultant array is
56 4 2

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    
    cout<<"Enter the number of elements in array\n";
    cin>>n;
    cout<<"Enter "<<n<<" elements\n";
    int array[n];
    for ( int  c = 0 ; c < n ; c++ )
        cin>>array[c];
    
    cout<<"Enter the location(0 - Based Indexed) where you wish to delete element\n";
    int pos;
    cin>>pos;
    
    if ( pos >= n )    
        cout<<"Deletion not possible.\n";
    
    else
    {    
        for (int  c = pos ; c < n - 1 ; c++ ) 
            array[c] = array[c+1];        
        
        cout<<"Resultant array is\n";
        
        for( int c = 0 ; c < n - 1 ; c++ )        
             cout<<array[c]<<" ";        
    }    
    return 0;
}

Output

Enter the number of elements in array
6
Enter 6 elements
9 8 7 6 5 4 
Enter the location(0 - Based Indexed) where you wish to delete element
5
Resultant array is
9 8 7 6 5

Let’s analyse the time complexities in each aspect.

  • Best Case: O(1), when the user wants to delete the element present at the last index of an array.
  • Average Case: O(N) when the user wants to remove the element present at any particular position.
  • Worst Case: O(N), when the user wants to remove the element present at the first index of an array.

Now, you should try some Array-based questions to boost your learning.

  1. Algorithm to find best insert position in a sorted array
  2. NINJA’S ARRAY
  3. Reverse the array
  4. First Index of Element
  5. Rotate array

Frequently asked questions

What is an array? Explain the various operations that can be performed on arrays in C++?

An array is a collection of data items, all of the same types, accessed using a common name. Traversal, Insertion, Searching, Deletion, Sorting, and many more are the functions that can be performed on arrays in C++.

Why insertion and deletion are brutal in an array?

In short, array elements are arranged in sequential order. So to make any change in the array, we need to take care of the sequence. Hence, Insertion and Deletion are costly operations on Arrays in C/C++.

Why is binary search better than linear search?

Time Complexity is the main reason why Binary search is more efficient than linear search. Linear Search has O(n) time complexity, whereas Binary Search has O(log n).

How do you delete an element from an array?

Firstly, Search for the desired location where you want to remove the element, afterward shift the immediate next element to its left side. Repeat this process till you encounter the end of the array. Finally, decrement the array size by one.

What does traversing an array means?

Traversing an array means accessing every element of an array for a specific purpose. It could be Inserting, Searching, Deleting, or printing the array elements.

How is data stored in an array?

Elements of data are logically stored sequentially in blocks within the array. An index or subscripts reference each element. An index is usually a number used to address an element in the array.

Key Takeaways

To conclude the discussion, An array is a container that holds a fixed number of values of a single type. The length of an array is initialized when the array is created.

Insertion and Deletion are costly operations on arrays in C/C++ or be it any other programming language. Nevertheless, Searching is relatively more straightforward in arrays. There are many other operations that we can perform on arrays like sorting, manipulating, rotating, reversing, and the list goes on. 

Tadaaaaa, you made it till here. Pat yourself on the back. 

If you found this article advantageous, please share it with your friends.

Don’t stop here Ninja, get yourself enrolled in the free Guided Path

Have a look at these fantastic articles to empower your knowledge.

Understanding Pointers & References in C++, Learn to Sort Algorithms