Lecture on Arrays

Content
s
• Array Data Structure
• Types of Array
• Traversing an Array
• Insertion in Array
• Deletion in Array
• Sorting – Bubble Sort
• Searching – Linear Search and Binary Search 2
 Arrays

• An array is a fixed number of data items that are stored contiguously and
that are accessible by an index
• An Array is a linear collection of Homogeneous data items.
• An array is a collection of elements of similar data type.
• Contiguous memory allocation takes place.
• An array is a DS in which we can access every element directly using
position
variable .
• It is rather an organizational concept.
• Array elements can be accessed individually

3
 Types of array

ONE DIMENSIONAL ARRAY:

• One-dimensional array (or linear array) is a set of ‘n’ finite numbers
of homogenous data elements such as
1. The elements of the array are referenced respectively by an index
set
consisting of ‘n’ consecutive numbers.
2.The elements of the array are stored respectively in successive memory
locations.
• ‘n’ number of elements is called the length or size of an array. The elements
of an array ‘A’ may be denoted in C as
A[0], A[1], A[2], ...... A[n–1].
• The number ‘n’ in A[n] is called a subscript or an index and A[n] is
called a subscripted variable. : 4
 ONE DIMENSIONAL ARRAY

• The length or the number of data elements of the array

can be obtained from the index set by the formula
Length = UB – LB + 1
• If ‘n’ is 10, then the array elements A[0], A[1]......A[9] are
stored in sequential memory locations as follows

5
ONE DIMENSIONAL ARRAY

6
Syntax for single dimensional Array

Now this age array will have four elements, starting from age[0] …..
To age [3], total 4 elements. So, the index of first element is zero and
last element is one less than array’s size i.e. 3 = 4-1.
 Arrays inside the memory

 Array’s elements inside the memory are placed

sequentially.
 The figure shows typical elements placed inside the array
named age[ ] Now all elements are of integer dat type.
 Accessing array elements

• As Array Elements are sequential in nature, they individually could be

easily accessed with the use of loop.
• For loop is better to use, as array size is fixed and almost known in all
cases.
• So, we can access each element of an array using a for loop, starting its
counter variable from 0, to the last element (1 less than array’s size).
To access elements inside age array of size 4, we will use following
loop.
– for (int i=0;i<4; i++) or for (int i=0; i<=3; i++)
 Multi Dimensional Array

• If we are reading or writing two-dimensional array,

two loops are required.
• Similarly the array of ‘n’ dimensions would require ‘n’
loops. The structure of the two dimensional array is
illustrated in the following figure :
int A[10][10];

1
Multi Dimensional Array

1
 Creation of Integer Array

7 a[0]  int
a[10]={7,1,32,58,0,5,8,16,9,2
14 i=0  Integer
3}; array
a[1] “a”.
32  It is of dimension 10 (from
58 i=1 0 to 9).
 Take positing
0 a[2] variable i.
5 i=2
8 a[3]

16 i=3

9 a[4]
i=4
23
a[5]
 Basic Operations of an Array

Traversing Linear Array:

• Let A be a collection of data elements stored in the memory of the computer.
Suppose we want to print the content of each element of A or suppose we
want to count the number of elements of A, this can be accomplished by
traversing A, that is, by accessing and processing each element of a exactly
ones.
• The following algorithm traverses a linear array LA. The simplicity of the
algorithm comes from the fact that LA is a linear structure. Other linear
structures, such as linked list, can also be easily traversed. On the other hand,
traversal of nonlinear structures, such as trees and graph, is considerably
more complicated.
13
 Algorithm: (Traversing a Linear Array)

• Here LA is a linear array with lower bound LB and upper bound UB. This
algorithm traverses LA applying an operation PROCESS to each element of LA.
1. [Initialize counter] Set k: =LB.
2. Repeat steps 3 and 4 while k <=UB.
3. [Visit Element] Apply PROCESS to LA [k].
4.[Increase Counter] Set k: =k
+ 1. [End of step 2 loop]
5. Exit

14
 Algorithm II: (Traversing a Linear Array)

• We also state an alternative form of the algorithm which uses a repeat-for loop
instead of the repeat-while loop.
• Here LA is a linear array with lower bound LB and upper bound UB. This
algorithm traverses LA applying an operation PROCESS to each element of LA.
1.Repeat for k = LB to UB:
Apply PROCESS to LA [k].
[End of loop]
2. Exit.

15
JAVA Implementation of Traversing Algorithm

Output:

The array elements are:

arr[0]= 53
arr[1]= 99
arr[2]= -11
arr[3]= 5
arr[4]= 102

16
 Algorithm for Insertion

(Inserting into Linear Array) INSERT (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is an integer such that K<=N. The algorithm
inserts an element ITEM into the Kth position in LA.
1. [Initialize counter] Set J: = N.
2. Repeat Steps 3 and 4 while j >= k;
3. [Move jth element downward.] Set LA [J + 1]: =LA [J].
4. [Decrease counter] Set J: = J-1
[End of step 2 loop]
5. [Insert element] Set LA [K]:=ITEM.
6. [Reset N] Set N:=N+1
7. EXIT.

1
 Algorithm for Deletion
• The following algorithm deletes the Kth element from a linear array LA
and assigns it to a variable ITEM.
(Deletion from a Linear Array) DELETE (LA, N, K, ITEM)
• Here LA is a Linear Array with N elements and K is the integer such that K<=N. This algorithm delete
the Kth element from LA.
1. Set ITEM: = LA [k].
2. Repeat for J = K to N – 1.
[Move J + 1st element upward] Set LA [J]: = LA [J +1]. [End of loop]
3. [Reset the number N of elements in LA] Set N: = N-1
4. EXIT

18
JAVA Implementation of Insertion Algorithm

1
JAVA Implementation of Deletion Algorithm

20
2
 Sorting- Bubble Sort

• There are many sorting algorithms. This section describes the

sorting algorithm, called bubble sort, to sort a list.
• Suppose list[0]......list[n-1]is a list of n elements, indexed 0 to n-1. We
want to rearrange, that is, sort, the elements of list in increasing order.
The bubble sort algorithm works as follows:
• In a series of n-1 iterations, the successive elements list [index] and
list[index+1] of List are compared. If list [index] is greater than list
[index+1], then the elements list[index] and list[index+1] are swapped,
that is, interchanged.

2
 Sorting- Bubble Sort

• It follows that the smaller elements move toward the top (beginning), and the
larger elements move toward the bottom (end) of the list.
• In the first iteration, we consider list[0]...list[n-1]; in the second iteration, we
consider list[0]...list[n - 2]; in the third iteration, we consider list[0]...list[n-3], and
so on. For example, consider list[0]............list[4], as shown in Figure

2
24
25
26
27
 Sorting- Bubble Sort
• Suppose the list of numbers A [1], A [2], A [3], …, A[n] is in
memory. The bubble sort algorithm works as

• Step 1: Compare A [1] and A[2] and arrange them in the desired order, so that
A [1] < A [2]. Then compare A [2] and A [3] and arrange them so that A [2] <
A [3]. Then Compare A [3] and A [4] and arrange them so that A [3] < A [3].
Continue until we compare A [n-1] with A [n] and arrange them so that A [n-
1] < A [n].
• Observe that step 1 involves n-1 comparisons. When step 1 is completed,
A[n] will contain the largest element.

28
 Sorting- Bubble Sort

Step 2: Repeat Step 1 with one less comparison; that is, now we stop after we
compare and possibly rearrange A [n-2] and A [n-1]. When Step 2 is completed,
the second largest element will occupy A [n-1].
Step 3: Repeat step 1 with two fewer comparisons; that is, we stop after we
compare and possibly rearrange A [n-3] and A [n-2].
……………………………………………………………………………………
……………………………………………………………………………………
Step n-1: Compare A [1] with A [2] and arrange them so that A [1] < A [2].
• After n-1 steps, the list will be sorted in the increasing order.

29
 Algorithm: (BUBBLE SORT)
Algorithm: (BUBBLE SORT) BUBBLE (DATA, N)
Here DATA is an array with N elements. This algorithm sorts the elements in DATA.
1. Repeat step 2 and 3 for K=1 to N-1
2. Set PTR :=1 [Initializes pass pointer PTR]
3. Repeat while PTR <= N-K [Executes pass]
a. If DATA [PTR]> DATA [PTR+1], then: Interchange
DATA [PTR] and DATA [PTR+1].
[End of if structure].
b.Set PTR: = PTR+1. [End of
inner loop].
[End of Step 1 outer loop].
4. EXIT.
30
JAVA Implementation of Bubble Sort
Algorithm

31
 Searching

• The goal of the search is to find all records with keys matching a
given search key.
• Applications of searching are widespread, and involve a variety of
different operations.
• Two common terms often used to describe data structures for searching
are dictionaries and tables.
• In searching have programs that are in widespread and frequent use to
study a variety of methods that store records in arrays that are either
searched with key comparisons or indexed by key value.

33
 Searching (Continue)

• Search algorithms as belonging to packages implementing a variety

of generic operations that can be separated from particular
implementations, so that alternate implementations can be substituted
easily. The operations of interest include:
• Initialize the data structure.
• Search for a record (or records) having a given key.
• Insert a new record.
• Delete a specified record.
• Join two dictionaries to make a large one.
• Sort the dictionary; output all the records in sorted order.
34
Searching

35
Linear Search

36
 Algorithm- Linear Search
(Linear Search) LINEAR (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements, and ITEM is a given item of information. This
algorithm finds the location LOC of ITEM in DATA, or sets LOC: = 0 if the search is unsuccessful.
1. [Insert ITEM at the end of DATA.]Set DATA [ N+1 ]: = ITEM.
2. [Initialize counter.] Set LOC: = 1.
3. [Search for ITEM.]
Repeat while LOC ≤ N and DATA[LOC] ≠ ITEM:
Set LOC: = LOC+1.
[End of loop.]
4. [Successful?] If LOC = N+1, then: Set LOC: = 0.
5. Exit

37
JAVA Implementation of Linear Search
Algorithm

38
9/9/201
5
 Binary Search

• Suppose DATA is an array which is sorted in increasing numerical order or equivalently

alphabetically then there is an extremely efficient searching algorithm called binary
search which can be used to find the location of a given item of information in data
array.
• The basic idea is that you divide the array being searched into sub-arrays, and compare
the middle element to the value for which you are searching.
• The binary search algorithm applied to our DATA works as follows. During each stage of
our algorithm, our search ITEM is reduced to a segment of element of DATA:
DATA[BEG], DATA[BEG+1], DATA[BEG+2] ,--------------DATA[END]

40
 Binary Search
• Note that the variables BEG and END denote respectively the beginning and end location
of the segments under consideration. The algorithm compares ITEM with middle element
DATA[MID] of the segment, where MID is obtained by:
MID = INT ( ( BEG + END) / 2 )
a) We use INT (A) for the integer value of A. If DATA [MID] = ITEM then the search is
successful and we set LOC = MID. Otherwise new segment of DATA obtained as
follows:
b) If ITEM < DATA [MID], then ITEM can appear only in the left half of the segment.
DATA[BEG], DATA[BEG+1] ,--------------DATA [MID -1]
• So we reset END: = MID –1 and begin searching again.

41
 Binary Search

a) If ITEM > DATA [MID], then ITEM can appear only in the right half of the segment.
DATA [MID+1], DATA[MID+2] ,--------------DATA [END]
• So we reset BEG: = MID + 1 and begin searching again.
• Initially we begin with the entire DATA; i.e.., we begin with BEG =1 and END =n, or
more generally, with BEG = LB and END = UB.
• If ITEM is not in DATA, then eventually we obtain END <
BEG
• This condition signals that search is unsuccessful, and in such a case we assign LOC: =
NULL. Here NULL is a value that lies outside the set of indices of DATA: (In most cases,
we can choose NULL=0)

42
5
 Binary Search Algorithm

Algorithm: (Binary Search) BINARY (DATA, LB, UB, ITEM, LOC)

Here DATA is stored array with lower bound LU and upper bound UB, and ITEM is given item of
information. The variables BEG, END and MID denote, respectively, the beginning end and middle
location of the segment of an element of DATA. This algorithm finds the location LOC of ITEM in
DATA or set LOC= NULL.
1. [Initialize segment variable]
Set BEG: = LB, END: = UB and MID: = INT ((BEG+END)/2).
2. Repeat Step 3 and 4 while BEG<= END and DATA [MID]!= ITEM.
3. If ITEM < DATA[MID],
then Set END: = MID-1

44
 Binary Search Algorithm
ELSE:
Set BEG: = MID+1.
[End of if structure]
4.Set MID: =INT((BIG+END)/2) [End
of Step 2 loop]
5. If DATA[MID]= ITEM then
Set LOC: = MID
ELSE:
Set LOC: =
NULL.
[End of if
structure]
45
6. Exit
JAVA Implementation of Binary Search
Algorithm

46
9/9/201
6