C++ Programming:

Problem Solving and

Programming
Chapter 10
Arrays
Array
• Is a collection of a fixed number of elements of
the same data type.
• One-dimensional array - an array in which the
elements are arranged in a list form.
• Each element is accessed by using index /
subscript. It always starts from zero.

2
Array - Example

▪ Example: An array named score which can

store 8 different values at the same time.

score
95 …. …. …. 70 …. …. ….
0 1 2 3 4 5 6 7

subscript / index
3
Array - Example
▪ Example: To store the values 95 and 70
into first and fifth locations respectively:

- score [0] = 95; 1st location

- score [4] = 70; 5th location

score
95 …. …. …. 70 …. …. ….
0 1 2 3 4 5 6 7

4
Array - Introduction

▪ Arrays allow us to store related data items using

the same identifier.

(If NO ARRAY used, we would need to think of 8

identifiers to store the 8 values.)

▪ Also, less instruction is required to manipulate

the values.

5
8 identifiers without Array Using Array
int score1;
int score2;
int score3;
int score4; int score[7];
int score5;
int score6;
int score7; score[0] = 23;
score[1] = 56;
score1 = 23; score[2] = 76;
score2 = 56; score[3] = 86;
score3 = 76; score[4] = 88;
score4 = 86; score[5] = 93;
score5 = 88; score[6] = 45;
score6 = 93;
score7 = 45; 6
Array – One dimensional
▪ Example: ARR_1D is a 1-D array with 5
elements
ARR_1D
2 4 9 5 8
0 1 2 3 4

E.g. ARR_1D [2] = 9

ARR_1D [0] = 2
ARR_1D [4] = 8
7
Array – Declaration / Definition
▪ Array declaration:

<data type> <array name> [<array size>]

▪ E.g. int score [8];

▪ Defines an array which can store 8 integers
? ? ? ? ? ? ? ?
0 1 2 3 4 5 6 7
8
Array components-Assignment
• Consider the array
int score[8];
• Its elements are:
score[0], score[1], ………, score[7]
• Using assignment statements
score[3] = 88; // assign 88 to 4th element
i = 2; score[i] = 45; // assign 45 to 3rd
element
score[7] = score[7] + 5; // add 5 to the last
element of score array

9
Array components-Assignment
• Cannot assign one array to another array
Example:
int x[5] = {1,2,3,4,5}, y[5];
y = x; Invalid
• However:
for (int i=0; i<5; i++)
y[i] = x[i];  Valid

10
Array – Initialization
▪ Array initialization:
Initialization with definition:
compile-time initializing

▪ Braces { } are used to enclose the elements,

which must be separated by commas (,).

▪ E.g. int score [8] = { 95,08,85,67,70,60,78,90 };

float costs [4] = { 12.00, 5.00, 2.50, 7.25 };

11
Array Initialization - Example
▪ E.g. (i) int score[8] = { 95, 80, 85, 67, 70, 60, 88, 90 };

score
95 80 85 67 70 60 88 90
0 1 2 3 4 5 6 7

▪ E.g. (ii) float costs[4] = { 1.20, 5.50, 2.50,7.25 };

costs
1.20 5.50 2.50 7.25
0 1 2 3

12
Array Declaration & Initialization
▪ The squares brackets [ ] can be left empty
if all elements are present in the brackets.

Empty

E.g. int ARR [ ] = {2,3,1};

(same)
int ARR [3] = {2,3,1};
13
Array Declaration & Initialization

Partial initialization: the rest of

the elements will be filled with 0

int ARR[3] = { 2 };
int ARR[3] = { 2,0,0 }; same
int ARR[ ] = { 2,0,0 };

14
8 identifiers Array Array
without Array (Basic Initialization) (compile-time initializing)

int score1;
int score2;
int score3; int score[7];
int score4;
int score5;
int score6; score[0] = 23; int score[7] =
int score7; score[1] = 56; {23,56,76,86,88,93,45};
score[2] = 76;
score1 = 23; score[3] = 86;
score2 = 56; score[4] = 88;
score3 = 76; score[5] = 93;
score4 = 86; score[6] = 45;
score5 = 88;
score6 = 93;
score7 = 45; 15
Array – Index out of bound
▪ C++ does not check for the boundary of an
array. The programmer must check that all
indexes referenced are valid (i.e. within the
range of the array).
� common mistake:
int ARR[10];
Boundary/range of an array.
Begin from 0 - 9
ARR[10]= 45; /* Error: index out of bound! */

16
Operation on Array

▪ Initialize directly using a program statement:

int testscores[10];
testscores[5] = 60;
▪ Compile-time initialization using a program
statement:
int testscores[10] = {60, 20, 11, 55, 45, 89, 75 ,85, 23, 45};

▪ Processing of the whole array requires the

use of for loop
17
Operation on Array
int testscores[8]; Run-time
for (i= 0 ; i<8; i++){ 67
cin >> score; 50
95
testscores [ i ] = score; …..
}

testscores
67 50 95
0 1 2 3 4 5 6 7
18
Operation on Array
▪ Using values keyed in from keyboard:
for (i=0; i<8; i++){
or
cin >> score;
for (i=0; i<8; i++)
testscores [i] = score; cin >> testscore[i];
}

▪ Each operation requires ability to step through

the elements of the array
▪ It is accomplished by a loop
19
Operation on Array - Example
⦿ Assume that we have the following declarations:
double sales[10];
int index;
double largest, sum=0, average;

⦿ Initializing every elements of the array sales to 0.0

for(index = 0; index < 10; index++)
sales[index] = 0.0;

20
Operation on Array - Example
⦿ Reading data into the array sales
for(index = 0; index < 10; index++)
cin >> sales[index];

⦿ Printing the values from the array sales

for(index = 0; index < 10; index++)
cout << sales[index];

21
Operation on Array - Example
⦿ Find the sum and average from the array sales
int sum = 0;
for(index = 0; index < 10; index++)
sum += sales[index];
average = sum / 10.0;

⦿ Find the largest value from the array sales

largest = sales[0];
for(index = 1; index < 10; index++)
if (largest < sales[index])
largest = sales[index];
22
Manipulation of Array elements
▪ To double the value of all elements in testscore:
Beforeint testscore[ 8 ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 ,8 };
for ( i=0; i< 8; i++) After
testscore[i] *= 2;
Before:
testscore
1 2 3 4 5 6 7 8
After:
testscore
2 4 6 8 10 12 14 16
23
Manipulation of Array elements
▪ To print the contents of an array ARR:

int ARR[4] = {5, 7, 9, 11};

for ( i=0; i<4; i++)
cout<< “ARR[” << i << “] =”<<ARR[i] << endl;

Output: ARR[0] = 5
ARR[1] = 7
ARR[2] = 9
ARR[3] = 11
24
Manipulation of Array elements
▪ From one array, ARR, produce another array,
SQUARE:

int ARR[8] = { 2, 1, 9, 6, 5, 4, 7, 3 };
int SQUARE[8];
:
for ( i= 0; i< 8; i++)
SQUARE[i] = ARR[i] * ARR[i];

SQUARE
4 1 81 36 25 16 49 9
25
Manipulation of Indexes
⦿ The index can be written in many ways.

⦿ Example:
int x[5]={1, 2, 3, 8, 7};
int i = 2;

x[i+1] refers to the 4th element, x[3]

x[2*i] refers to the 5th element, x[4]
x[0] has a value of 1
26
Manipulation of Indexes
int num1[5] = {1, 2, 3, 4, 5}, num2[5], i;

for (i = 0; i < 5; i++)

num2[i] = num1[4-i];

num1 1 2 3 4 5
[0] [1] [2] [3] [4]

num2 5 4 3 2 1
[0] [1] [2] [3] [4]
27
Array - Exercise

a) Define a single-dimensional integer array called

SumArray of size 5

b) Initialize the array with the value 6, 8, 12, 15 and 18

c) Read a integer number from user and store it into
second element in the SumArray array. Then display all
the integer numbers in the SumArray.
Calculate and display the sum and average of the
integer numbers in the SumArray.

d) Write a program segment that displays all those integer

numbers that are divisible by 3 in the SumArray.
28
Array – Two dimensional
▪ E.g ARR_2D is a 2-D array with 3 x 4 elements
0 .. .. .. ..
1 .. .. .. 7
2 .. .. .. ..
0 1 2 3

e.g ARR_2D[1][3]=7;
▪ The element is accessed by using:
array_name[row number][column number]
29
Array – Two dimensional
▪ Contents are listed row by row, or each row
contents are enclosed separately in braces.
0 2 4 6 8
ARR_2D 1 1 3 5 7
2 1 4 9 16
0 1 2 3

e.g int ARR_2D[3][4]={ { 2,4,6,8 },

{ 1,3,5,7 },
{ 1,4,9,16 } };
30
Array – Two dimensional
▪ Only differences between single and two-
dimensional arrays : declaration and referencing.
This is due to the second index/dimension

One-Dimensional Two-Dimensional
Declaration int Arr[5]; int Arr[2][3];
Referencing int Arr[5] ={1, 2, 3, int Arr[2][3]
/ 4, 5} ; = {{2, 2, 2}, {3, 3, 3}};
Initialization

31
Two dimensional array – Processing
Algorithm
0 2 4 6 8
ARR_2D 1 1 3 5 7
2 1 4 9 16
0 1 2 3
Single Row processing:
E.g. Sum up total of 2nd row of ARR_2D array
row = 1;
for ( col = 0; col < 4; col++ )
sum += ARR_2D [ row ][ col ];
32
Two dimensional array – Processing
Algorithm
0 2 4 6 8
ARR_2D 1 1 3 5 7
2 1 4 9 16
0 1 2 3
Single Column processing:
E.g. Sum up total of 4th column of ARR_2D array
col = 3;
for ( row = 0; row < 3; row++ )
sum += ARR_2D [ row ][ col ];
33
Two dimensional array – Processing
Algorithm
0 2 4 6 8
ARR_2D 1 1 3 5 7
2 1 4 9 16
0 1 2 3
Row by Column processing:
E.g. Find the grand total of ARR_2D
for ( row = 0; row < 3; row++ )
for ( col = 0; col < 4; col++ )
GrandTotal += ARR_2D [ row ][ col ];
34
Two dimensional array – Processing
Algorithm
0 2 4 6 8
ARR_2D 1 1 3 5 7
2 1 4 9 16
0 1 2 3
Colum by Row processing:
E.g. Find the grand total of ARR_2D
for ( col = 0; col < 4; col++ )
for ( row = 0; row < 3; row++ )
GrandTotal += ARR_2D [ row ][ col ];
35
Passing Array to Function
(Individual element)
⦿ Using pass-by-value – similar to passing
values from actual parameters to formal
parameters.

⦿ Example:
void initialize (int x)
{
....;
}

⦿ Function call:
initialize (list[5]);
36
Passing Array to Function
(Individual element) - Example
#include <iostream>
#define SIZE 15
using namespace std;
int findLargest(int, int);

int main(){
int list[SIZE] = { 5, 2, 7, 8, 36, 4, 2, 68, 22, 34,
11 };
Pass an individual int largest, i;
element of the array
for (largest = list[0], i = 1; i<SIZE; i++)
largest = findLargest(list[i], largest);
Normal variable cout << "The largest number is " << largest
declared as formal << endl;
return 0;
parameter to }
receive value from
the array element int findLargest(int x, int largest){
if (x > largest)
return x;
else
return largest; 37
Passing Array to Function
(Whole array)
⦿ Using pass-by-reference – Do not use the symbol &
when declaring an array as a formal parameter.

⦿ The size of the array is usually omitted

◼ If the size is specified when it is declared as a

formal parameter, the size is ignored by the

compiler.
No & symbol and the size is
⦿ Example: not specified

void initialize (int list[], int size)

{
....;
} 38
Passing Array to Function
(Whole array) - Example
#include <iostream>
#define SIZE 15
using namespace std;
int findLargest(int []);

int main() {
pass only the int list[SIZE] = { 5, 2, 7, 8, 36, 4, 2, 68,
22, 34, 11 };
name of the array int largest;
largest = findLargest(list);
cout << "The largest number is " <<
largest ;
formal parameter of the return 0;
function definition must }
be an array type
int findLargest (int x[]) {
int largest, i;
size of the array does for (largest = x[0], i = 1; i < SIZE; i++)
not need to be specified if (x[i] > largest)
largest = x[i];
return largest; 39
Passing Array to Function
(Whole array) - Example
#include <iostream> void multiply2(int x[], int size)
#define SIZE 5 { int i;
using namespace std;
cout << "Printed from multiply2\
void multiply2(int x[], int size);
n";
int main()
{ for (i = 0; i < size; i++)
int i, base[SIZE] = { 3, 7, 1, 5, 8 }; { x[i] *= 2;

cout << "Before function call : \n"; cout << x[i] << " ";
for (i = 0; i < 5; i++) }
cout << base[i] << " "; cout << endl << endl;
cout << endl << endl;
}
multiply2(base, SIZE);

cout << "After function call : " <<

endl;
for (i = 0; i < 5; i++)
cout << base[i] << " ";
cout << endl << endl;
return 0;
} 40
Passing Array to Function
(Whole array) - Example
⦿ Output:
Before function call:
37158

Printed from multiply2 :

6 14 2 10 16

After function call:

6 14 2 10 16

The original values changed after function call.

WHY? Array name is actually a pointer 41
Function returns an Array

⦿ A function may not return an array in the

same way that it returns a value of type int
or double.
⦿ Instead of writing a function that returns an
entire array, we can return a pointer to an
array by specifying the array's name with *.
⦿ E.g.

int * getRandom( )

42
Function returns an Array - Example

int * getRandom( ) int main()

{ pointer {
int *R; pointer
static int rdm[10]; R = getRandom();
srand( time(0)); for(int i=0; i<10; i++)
for(int i = 0; i < 10; i++) cout << R[i];
{ return 0;
rdm[i] = rand(); }
}

return rdm; return the pointer to the array

}
43
Introduction to Search Algorithms

• Search: locate an item in a list of information

(array)
• Two algorithms (methods) are considered here:
− Linear search
− Binary search

44
Linear Search Example

• Array numlist contains

17 23 5 11 2 29 3

• Searching for the the value 11, linear search

examines 17, 23, 5, and 11
• Searching for the the value 7, linear
search examines 17, 23, 5, 11, 2, 29,
and 3

45
Linear Search Tradeoffs

• Benefits
− Easy algorithm to understand
− Array can be in any order
• Disadvantage
− Inefficient (slow): for array of N elements,
examines N/2 elements on average for value
that is found in the array, N elements for value
that is not in the array

46
Binary Search Algorithm
1. Divide a sorted array into three sections:
− middle element
− elements on one side of the middle element
− elements on the other side of the middle element
2. If the middle element is the correct value, done.
Otherwise, go to step 1, using only the half of
the array that may contain the correct value.
3. Continue steps 1 and 2 until either the value is
found or there are no more elements to
examine.

47
Binary Search Example

• Array numlist2 contains

2 3 5 11 17 23 29
• Searching for the the value 11, binary search
examines 11 and stops
• Searching for the the value 7, binary
search examines 11, 3, 5, and stops

48
Binary Search Tradeoffs

• Advantage
− Much more efficient than linear search

Disadvantage
− Requires that array elements be sorted

49
Introduction to Sorting Algorithms

• Sort: arrange values into an order

− Alphabetical
− Ascending numeric
− Descending numeric
• Two algorithms considered here
− Bubble sort
− Selection sort

50
Bubble Sort Algorithm

1. Compare 1st two elements and exchange them if

they are out of order.
2. Move down one element and compare 2 nd and 3rd
elements. Exchange if necessary. Continue until
end of array.
3. Pass through array again, repeating process and
exchanging as necessary.
4. Repeat until a pass is made with no exchanges.

51
Bubble Sort Example

Array numlist3 contains

17 23 5 11

Compare values 17 and Compare values 23 and

23. In correct order, so 11. Not in correct order,
no exchange. so exchange them.

Compare values 23 and

5. Not in correct order,
so exchange them.

52
Bubble Sort Example (continued)
After first pass, array numlist3 contains
In order from
previous pass
17 5 11 23

Compare values 17 and Compare values 17 and

5. Not in correct order, 23. In correct order, so
so exchange them. no exchange.

Compare values 17 and

11. Not in correct order,
so exchange them.

53
Bubble Sort Example (See pr9-04.cpp)
After second pass, array numlist3 contains
In order from
previous passes
5 11 17 23

Compare values 5 and Compare values 17 and

11. In correct order, so 23. In correct order, so
no exchange.
no exchange.
Compare values 11 and No exchanges, so
17. In correct order, so array is in order
no exchange.

54
Bubble Sort Tradeoffs

• Benefit
− Easy to understand and implement
• Disadvantage
− Inefficiency makes it slow for large arrays

55
Selection Sort Algorithm

1. Locate smallest element in array and

exchange it with element in position 0.
2. Locate next smallest element in array and
exchange it with element in position 1.
3. Continue until all elements are in order.

56
Selection Sort Example

Array numlist contains

11 2 29 3
Smallest element is 2. Exchange 2 with
element in 1st array position (i.e. element 0).

Now in order
2 11 29 3

57
Selection Sort – Example (See pr9-05.cpp)

Next smallest element is 3. Exchange

3 with element in 2nd array position.
Now in order
2 3 29 11
Next smallest element is 11. Exchange
11 with element in 3rd array position.

Now in order
2 3 11 29

58
Selection Sort Tradeoffs

• Benefit
− More efficient than Bubble Sort, due to fewer
exchanges
• Disadvantage
− Considered harder to understand as compared
to Bubble Sort

59