Sunday, August 14, 2016
One dimensional array algorithms
One dimensional array algorithms:
This
algorithm to Traverse an array:
Description: Here
A is a linear array. This algorithm
traverses
Array A
and applies the operation PROCESS
to each element of the array.
1. Repeat For I = 0 to N
2. Apply PROCESS to A[ I ]
[End of For Loop]
3. Exit
|
Explanation: Here A is a linear array stored in memory. The “For loop”
iterates from 0 to N and visits each element of the array. During this visit,
it applies the operation PROCESS to the elements of the array A.
Note: The operation PROCESS in the traversal algorithm may use certain
variables which must be initialized before PROCESS is applied to any of the
elements in the array. Therefore, the algorithm may need to be preceded by such
an initialization step.
This algorithm is for inserting a value
in a sorted array:
Description: Here
A
is a sorted linear array (in ascending order) with N elements.
ITEM
is the value to be inserted.
1.
Input value in ITEM
2.
Set
I = N
[Initialize counter]
3.
Repeat
While (ITEM < A[I]) and (I >= 1)
4. Set A[I+1] = A[I] [Move elements downward]
5.
Set I = I – 1 [Decrease counter by 1]
[End of While Loop]
6.
Set A[I+1] = ITEM
[Insert element]
7.
Set N = N + 1
[Reset N]
8.
Exit
|
Explanation: Here A is a sorted array stored in
memory. This algorithm inserts a data element ITEM into the (I + 1)th position
in an array A. I is initialized from N i.e. from total number of elements. ITEM
is compared with each element until it finds an element which is smaller than
A[I] or it reaches the first element.
During this process, the elements are moved downwards and I is decremented. When it finds an element smaller then ITEM, it inserts it in the next location i.e. I + 1 because I will be one position less where ITEM is to be inserted. And finally, total number of elements is increased by 1.
This
algorithm is for inserting a value at specified location in an unsorted array:
Description: Here A is a sorted linear array with N elements. LOC is the location
where ITEM is to be inserted.
1.
Input value in ITEM
2.
Input location in LOC
3.
Set I = N [Initialize
counter]
4.
Repeat While (I >= LOC)
5.
Set A[I+1] = A[I] [Move elements downward]
6.
Set I = I – 1 [Decrease counter by
1]
[End
of While Loop]
7.
Set A[LOC] = ITEM [Insert element]
8.
Set N = N + 1 [Reset N]
9. Exit
|
Explanation: Here A is an unsorted array stored in memory with N elements. This algorithm inserts a
data element ITEM into the locth position in an
array A. The first four steps create space in A by moving downward the elements of A.
These elements
are moved in reverse order i.e. first A [N], then A [N–1], A [N–2 ] , . . . . . and last A[LOC], otherwise data will be overwritten. We first set I=N and then, using I as a counter, decrease it each time
the loop is executed until I reaches LOC. In the next step, Step 5, it inserts ITEM into the array in the space just
created. And at last, the total number of elements N is increased by 1.
This algorithm is for deleting an item from an array at specified
location:
Description: Here
A is a linear array with N
elements. LOC is
the location from where ITEM is
to be deleted.
1.
Input location in LOC
2.
Set ITEM = A[LOC] [Assign the
element to be deleted to ITEM]
3.
Repeat For I = LOC to N
4.
Set A[I] = A[I+1] [Move
the Ith element upwards]
[End of For Loop]
5.
Set N =
N – 1 [Reset N]
6.
Exit
|
Explanation: First, the element to be deleted is
assigned to ITEM from location A[LOC].Then I is set to LOC from where ITEM is to be deleted and it iterated to total number of elements i.e. N. During this loop, the elements are
moved upwards. And lastly, total number of elements is decreased by 1.
This algorithm
merge two sorted arrays by using 3rd array:
Description: Here A
is a sorted array with M elements and B is a sorted
array with N elements. C is an empty array with P locations where P
>= M + N.
1. Set I = J = K = 1
[ Initialize counters ]
2. Repeat While (I <= M) and (J <= N)
3. If ( A[ I ] < B [ J ]
) Then
4. Set
C[ K ] = A[ I ] [ Assign
elements of array A to array C ]
5. Set I = I + 1
6. Else
7. Set C[ K ] = B[ J ] [ Assign
elements of array B to array C ]
8. Set J = J + 1
[End of If]
9. Set K = K + 1
[End
of While Loop]
10. If (I > M) Then [ Array A is empty ]
11. Repeat
While ( J <= N)
12. Set C [ K
] = B [ J ] [Assign the remaining elements of array B to array C ]
13. Set J = J+1 and K = K+1
[End of While Loop]
[End of If]
14. If ( J > N ) Then
[ Array B is
empty ]
15. Repeat
While (I <= M)
16. Set C[K] = A[I]
[Assign
the remaining elements of array A to array C ]
17. Set I = I+1 and K = K+1
[End of While Loop]
[End of If]
18. Exit
|
Explanation:
The above algorithm merges the elements of sorted array A and sorted array B into a sorted array C. First of all, we must keep track of
the locations of the smallest element of A and the smallest element of B which have not yet been placed in C. I and J denote these locations respectively, and K denotes the location in C to be filled. Therefore, initially,
we set I = J = K = 1.
In step 3, we compare A [ I ] and B [ J ] and assign the smallest element to C [ K ]. Then we either increment I by setting I = I + 1 or increment J by setting J = J + 1, according to whether the new
element in C has come from A or B. And also we increment K by setting K = K + 1. If I > M, then it means array A has become empty and the remaining
elements of B are assigned to C, or if J > N, then it means array B has become empty and the remaining elements of A are assigned to C.
This algorithm
merge two unsorted array by using 3rd array:
Description:
Here A is an array with M
elements and B is an array with N elements. C is
an empty array with P
locations
where P
>= M + N.
1. Repeat For I = 1 to M
2. Set C[ I
] = A[ I ] [Assign the elements of array A to array C]
[End of For Loop]
3. Set K = 1 [Initialize
counter]
4. Repeat For J = M+1 to M+N
5. Set C [ J
] = B[ K ] [Assign the elements of array B to array C]
6. Set K = K + 1 [Increase the counter by 1]
[End of For Loop]
7. Exit
|
Explanation: In step 1 & 2, all the elements of array A are assigned to array C. Then K is initialized from 1 which will keep
track of the elements of array B. In step 4 for loop, J is initialized from next empty location in C i.e. M+1 and it will iterate to total number
of elements of array A & B i.e. M+N. In step 5, all the elements of array B are assigned to array C and in next step, K is incremented by 1.
Subscribe to:
Post Comments
(
Atom
)
good way to sort an array ...pleas do more way to define sorting of arrays
ReplyDelete