Lesson 2 - Arrays Data Structures & Algorithms

Instructor: Engr. Bernardith Batoy-Cruz (Ms. Badeth)

Email: [email protected]
FB Messenger: MsBerna Kruz (My profile pic has Siena’s SAFE frame)

LESSON 2:
INTRODUCTION

List – one of the simplest and most common types of data. An ordered set consisting of a variable
number of elements to which additions and deletions may be made, if applicable.

Linear list – a list which displays the relationship of physical adjacency. A finite sequence of simple data
items or records.

Some examples of linear lists are:

Days of the Week (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday)
Values in a Deck of Cards (2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace)
Floors of a Building (Basement, Lobby, Mezzanine, First, Second, Third)

ARRAY
➢ May be defined as an ordered collection of data items of the same type referred to collectively
by a single name.
➢ Individual data items in an array are called elements.
➢ Array elements are ordered according to subscripts (an integer from 1 to n); for this reason
they are sometimes called subscripted variables.

Dimensionality of an Array
➢ The number of subscripts of an array determines its dimensionality.
➢ One – dimensional, two – dimensional and multi – dimensional arrays.

ONE – DIMENSIONAL ARRAYS

➢ An array with only one subscript, for example, Array[i], is called a one-dimensional
array.

Array[subscript1] where 1<= subcript1 <= 10

Retrieving the ith Element of a One-Dimensional Array

The following pseudo code illustrates the process of reading the elements of an array from left
to right. The algorithm Read_Arr accepts the following parameters as input:

1. Arr1 The name of the array whose elements are to be read

2. N The number of elements in the array

Prepared by Engr. Badeth Batoy-Cruz Page 1 of 6

Lesson 2 - Arrays Data Structures & Algorithms

Read_Arr (Arr1, N)
{
Set Ctr to 0 Algorithm for reading the elements of a
While (Ctr < N) One-Dimensional Array
{
Print Arr1[Ctr]
Increment Ctr
}
}

Storing a New Value into an Element of a One-Dimensional Array

Store_Arr (Arr1, N)
{
Set Ctr to position of the element Algorithm for storing new elements in
Set Arr1[Ctr] to New Value One-Dimensional Array

Deleting an Element from a One-Dimensional Array

Delete_Arr (Arr1, N)
{
Set Ctr to position of the element Algorithm for deleting an element in
Set Arr1[Ctr] to Null One-Dimensional Array

Sorting the Elements of a One-Dimensional Array in Ascending Order

Using an array called Arr1 with a size of N, the following pseudo code illustrates the procedure
for sorting an array in ascending order. The algorithm makes use of three other variables:
1. Ctr1 A subscript to an element of the array
2. Ctr2 A subscript to another element of the array
3. Temp A variable used to temporarily hold the value of an element
Sort_Arr (Arr1,N)
{
Set Ctr1 to 0
While(Ctr1 < N-1)
{
Set Ctr2 to Ctr1 + 1
While(Ctr2 <N)
{
If ( Arr1[Ctr1] > Arr1[Ctr2] ) then
{
Set Temp to Arr1[Ctr1]
Set Arr1[Ctr1] to Arr1[Ctr2]
Set Arr1[Ctr2] to Temp
}
Increment Ctr2
}
Increment Ctr1
}
}

Prepared by Engr. Badeth Batoy-Cruz Page 2 of 6

Lesson 2 - Arrays Data Structures & Algorithms

Copying a One-Dimensional Array

Copy_Arr (Arr1, N)
{
Set Ctr to 0
While (Ctr < N)
{
Set Arr2[Ctr] to Arr1[Ctr]
Increment Ctr
}
}

TWO-DIMENSIONAL ARRAYS
➢ An array with two subscripts.
➢ The first subscript is called the row and the second subscript is referred to as the column.

The following is a list of the basic operations that can be performed on two-dimensional
arrays:
1. Retrieving the element in the array
2. Reading all the elements in the array row-wise (or column-wise)
3. Storing a new value
4. Deleting the element
5. Copying an array

Reading a Two-Dimensional Array in row-wise

Read_TwoDim (Arr1, I, J)
{
Set ctr1 to 0
While (ctr1 < I)
{
Set ctr2 to 0
While (ctr2 < J)
{
Print (Arr1[ctr1][ctr2])
Increment ctr2
}
Increment ctr1
}
}

Prepared by Engr. Badeth Batoy-Cruz Page 3 of 6

 Lesson 2 - Arrays Data Structures & Algorithms

Copying a Two-Dimensional Array

Copy_2Dim (Arr1, I, J) Copy_2Dim (Arr1, I, J)

{ {
Set ctr1 to 0 Set ctr2 to 0
While (ctr1 < I) While (ctr2 < J)
{ {
Set ctr2 to 0 Set ctr1 to 0
While (ctr2 < J) While (ctr1 < I)
{ {
Set Arr2[ctr1][ctr2] to Arr1[ctr1][ctr2] Set Arr2[ctr1][ctr2] to Arr1[ctr1][ctr2]
Increment ctr2 Increment ctr1
} }
Increment ctr1 Increment ctr2
} }
} }

Algorithm for Copying a Two-Dimensional Array by Row Algorithm for Copying a Two-Dimensional Array by Column

MATRICES

➢ A matrix is a mathematical object which arises in many physical problems.

➢ A general matrix consists of m rows and n columns.

Magic Square

➢ An n x n matrix of the integers 1 to n2 such that the sum of every row, column and diagonal
is the same.
➢ For example, the figure below shows the magic square for a 3 x 3 matrix where the common
sum is 15.

Sum of Diagonals: 1) 6 + 5 + 4 = 15
2) 8 + 5 + 2 = 15
Column Column Column SUM
1 2 3
Magic Square for N=3
Row 1 6 1 8 15
Row 2 7 5 3 15
Row 3 2 9 4 15
SUM 15 15 15

H. Coxeter has given a simple rule for generating a magic square

When n is odd:
“Start with 1 in the middle of the top row; then go up and left assigning numbers in increasing order to
empty squares; if you fall off the square imagine the same square as tilting the plane and continue; if a
square is occupied, move down instead and continue.”

Prepared by Engr. Badeth Batoy-Cruz Page 4 of 6

Lesson 2 - Arrays Data Structures & Algorithms

Sparse Matrix

➢ A matrix that has many zeros (0) entries.

➢ Let us assume that we have a 6 x 6 matrix called Arr1 which contains the following
elements:

Column 1 Column 2 Column 3 Column Column Column

4 5 6
Row 1 18 0 13 0 0 0
Row 2 0 4 0 0 8 0
Row 3 0 0 9 0 0 0
Row 4 6 0 0 16 0 7
Row 5 0 32 0 10 0 0
Row 6 0 0 12 0 25 0
Sparse Matrix

Transpose Matrix

➢ A “copy” of a particular matrix wherein the elements in the [ i, j ] position are transferred
to the [ j, i ] position.

➢ To illustrate this concept, let us consider the matrix below which represents a matrix
called Arr1.
Column 1 Column 2 Column 3 Column Column
4 5
Row 1 1 2 3 4 5
Row 2 6 7 8 9 10
Row 3 11 12 13 14 15
Row 4 16 17 18 19 20

4 x 5 Matrix Called Arr1

➢ The following, Arr2, is the transpose of Arr1.

Column 1 Column 2 Column 3 Column

4
Row 1 1 6 11 16
Row 2 2 7 12 17
Row 3 3 8 13 18
Row 4 4 9 14 19
Row 5 5 10 15 20
Transpose Matrix of Arr1

Prepared by Engr. Badeth Batoy-Cruz Page 5 of 6

Lesson 2 - Arrays Data Structures & Algorithms

The pseudocode Transpose computes for the transpose of a matrix. It accepts as input
the following information:
1. Arr1 The source array
2. m The number of rows in the matrix
3. n The number of columns in the matrix

Transpose ( Arr1, I, J )
{
Define Arr2 with size [ J x I ]
Set ctr1 to 0
While ( ctr1 < I )
{
Set ctr2 to 0
While ( ctr2 < J )
{
Set Arr2[ctr2][ctr1] to Arr1[ctr1][ctr2]
Increment ctr2
}
Increment ctr1
}
}

ACTIVITY 1: Pseudocode Writing (20 pts. each)

1. Modify the algorithm of reading the elements of a one-dimensional array, this time make the
algorithm storing new N elements. (20 pts.)

2. Modify the algorithm of reading the elements of a one-dimensional array, this time make the
algorithm deleting N elements. (20 pts.)

3. Modify the algorithm of sorting the elements of a one-dimensional array in ascending order,
this time the algorithm should arrange the elements in descending order. (20 pts.)

4. Modify the algorithm of reading a two-dimensional array in row-wise, this time make the
algorithm reading the elements in column-wise method. (20 pts.)

ACTIVITY 2: Magic Square (20 pts.)

5. Using the simple rule for generating a magic square suggested by H. Coxeter, show the magic
square of 5x5 and 7x7 matrix. (20 pts.)

Prepared by Engr. Badeth Batoy-Cruz Page 6 of 6