University of Engineering and Technology, Taxila
Experiment 3
Arrays : Implementation of insert and delete operations
CLO-2: Use modern tools to solve problems of varying complexities in data
structures.
CLO-3: Construct the projects of varying complexities using different data
structures
CLO-4: Demonstrate a unique solution of problem under discussion
University of Engineering and Technology, Taxila 1
Array Operations
INSERT Operation in Arrays:
Sorted Array:
AIM: Write a program to Insert an Item into Linear Array:
Description: Inserting refers to the addition of a new element in an array, say ‘A’. Inserting an
element at the end of the array can be easily done. On the other hand, if an element is to be
inserted at the beginning or in the middle of array ‘A’, then the elements (from insertions point
inclusively) must be moved downward to new locations, to accommodate the new element.
Assume, values inside the ‘A’ are in sorted order and it is needed to insert the new item at such
location in ‘A’ so that the sorted order of ‘A’ should not be disturbed. See the algorithm:
The following set of algorithms inserts a data element ITEM at Kth position in a linear
array. Here A is a Linear Array with SIZE locations, N is the number of total values stored in
A and K is a positive integer (location where to insert) such that K<= N.
This algorithm inserts an element ITEM into the Kth position in A.
Algorithm:
1. if N = SIZE then write: “Overflow, Array is Full. “ and End
2. Get ITEM from user to be inserted in array
[ Find location in sorted array ]
3. Call Find_Location_To_Insert (A, N, K, ITEM)
[ Above algorithm finds the location K where to insert ]
4. Call INSERT (A, N, K, ITEM)
5. End
Engr. Rabia Arshad
University of Engineering and Technology, Taxila 2
Algorithm:
Find_Location_To_Insert(A, N, K, ITEM)
1. LB = 0 and UB = N – 1
2. Repeat Step-3 for K = LB to UB.
3. If A[K] > ITEM then return K. [ Insertion at front or in middle ]
[End of Step 2 loop.]
4. return K. [ Insertion at the end of array ]
5. End.
Algorithm:
INSERT (A, N, K, ITEM)
1. Set J = N - 1. [Initialize counter.]
2. Repeat Step-3 and 4 while J≥K.
3. Set A[J+1] = A[J]. [Move Jth element downward.]
4. Set J = J-1. [Decrease counter.]
[End of Step 2 loop.]
5. Set A[K] = ITEM. [Insert element.]
6. Set N = N+1. [Reset N.]
7. End.
Unsorted Array:
In an unsorted array, the insert operation is faster as compared to sorted array because we do
not have to care about the position at which the element is to be placed.
Engr. Rabia Arshad
University of Engineering and Technology, Taxila 3
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. Element might be present at
start, end or middle of array.
AIM: Write a program to Delete an Item from Linear Array:
Description: Deletion refers to the operation of removing one of the element from the array
‘A’. Deleting an item at the end of the array presents no difficulties. But, deleting an item
from beginning or somewhere in the middle of array would require that each subsequent
element be moved one location upward in order to fill up the array.
The following algorithm deletes the Kth element from a linear array A with N values stored
in it. Here A is a Linear Array with SIZE locations, N is the number of total values stored
in A and K is a positive integer such that K<=N. This algorithm deletes the Kth element
from A.
Algorithm:
1. If N = 0 then write: “Underflow. Array is Empty. “ and End
2. Get ITEM from user to be deleted from array
[ Find location in sorted array ]
3. Call Find_Location_To_Delete(A, N, K, ITEM)
4. If found Call DELETE (A, N, K, ITEM) [ if K = -1 then not found ]
Else write: “Not Found in array”
5. End
Engr. Rabia Arshad
University of Engineering and Technology, Taxila 4
Algorithm:
Find_Location_To_Delete(A, N, K, ITEM)
1. Repeat Step 2 for I = LB to UB.
2. If A[I] = ITEM then K = I and return K. [ Deletion from front or from middle]
[End of Step 2 loop.]
3. K = -1 and return K. [ITEM Not found in array ]
4. End.
Algorithm:
DELETE (A, N, K, ITEM)
1. Set ITEM = A[K].
2. Repeat for J=K to N-1:
Set A[J] = A[J+1] [Move J + 1 element upward.].
[End of loop.]
3. Set N = N-1. [Reset the number “N” of element in A.]
4. End.
Task 1: Write a program, which perform insertion as well as deletion on array elements
(User’s choice) by using above-mentioned algorithms.
Exercise#02: (Upload your exercise work before next DSA lab on LMS portal, exercise-uploading
time will expire at 12:00am, Copied code will be marked 0).
Viva of Exercise will be in coming lab:
Q#01: In-Place merge two Sorted arrays:
Given two sorted arrays A[] and B[] of size m and n, merge elements of A[]
with elements of array b[] by maintaining the sorted order i.e. fill A[] with
smallest elements and fill b[] with remaining elements.
A[]={1,4,6,9,11}
B[]={0,2,5,7}
Output:
A[]={0,1,2,4,5}
B[]={6,7,9,11}
Engr. Rabia Arshad
