Search, insert and delete in an unsorted array

0

Search, insert and delete in an unsorted array

In this post search, insert and delete operation in an unsorted array is discussed.

Search Operation

In an unsorted array, the search operation can be performed by linear traversal from the first element to the last element.

// C program to implement linear search in
// unsorted array
#include<stdio.h>
/* Function to implement search operation */
int findElement(int arr[], int n,int key)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == key)
            return i;
    return -1;
}
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 34, 10, 6, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    //Using a last element as search element
    int key =40;
    int position = findElement(arr,n,key);
    if (position==-1)
        printf("Element not found");
    else
        printf("Element Found at Position: %d", position+1 );
    return 0;
}

Output:

Element Found at Position: 5

Insert Operation

In an unsorted array, the insert operation is faster as compared to sorted array because we don’t have to care about the position at which the element is to be placed.

// 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 capcity
    if (n >= capacity)
       return n;
    arr[n] = key;
    return (n+1);
}
/* Driver program to test above function */
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]);
    // Inserting key
    n = insertSorted(arr, n, key, capacity);
    printf("\nAfter Insertion: ");
    for (i=0; i<n; i++)
        printf("%d  ",arr[i]);
    return 0;
}

Output:

Before Insertion: 12 16 20 40 50 70 
After Insertion: 12 16 20 40 50 70 26 

Delete Operation

In delete operation, the element to be deleted is searched using the linear search and then delete operation is performed followed by shifting the elements.

// C program to implement delete operation in a
// unsorted array
#include<stdio.h>
// To search a key to be deleted
int findElement(int arr[], int n, int key);
/* Function to delete an element */
int deleteElement(int arr[], int n, int key)
{
    // Find position of element to be deleted
    int pos = findElement(arr, n, key);
    if (pos==-1)
    {
        printf("Element not found");
        return n;
    }
    // Deleting element
    int i;
    for (i=pos; i<n-1; i++)
        arr[i] = arr[i+1];
    return n-1;
}
/* Function to implement search operation */
int findElement(int arr[], int n, int key)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == key)
            return i;
    return -1;
}
// Driver code
int main()
{
    int i;
    int arr[] = {10, 50, 30, 40, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 30;
    printf("Array before deletion\n");
    for (i=0; i<n; i++)
      printf("%d  ", arr[i]);
    n = deleteElement(arr, n, key);
    printf("\n\nArray after deletion\n");
    for (i=0; i<n; i++)
      printf("%d  ", arr[i]);
    return 0;
}

Output:

Array before deletion
10 50 30 40 20 

Array after deletion
10 50 40 20 

Time complexities:
Search: O(n)
Insert: O(1)
Delete: O(n)

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar