10: Arrays

What We Will Cover

Continuations

Homework Questions?

Questions from last class?

^ top

10.1: Array Basics

Objectives

At the end of the lesson the student will be able to:

  • Declare and allocate memory for arrays
  • Generate code to initialize arrays
  • Access array elements

^ top

10.1.2: Introduction to Arrays

Array: a single name for a collection of identically-typed data values

  • Arrays are a type of data structure
    • -- a way to organize data
  • An array is used to process a collection of data of the same type
    • Scores
    • Temperatures
  • Why do we need arrays?
  • Imagine keeping track of 5 test scores, or 100, or 1000 in memory
    • How would you name all the variables?
    • How would you process each of the variables?
  • Arrays provide a convenient solution to these problems
  • Entire array referred to by a single identifier
  • Each element uniquely identified by an index number

For Example

  • One-dimensional array is like single row of data in spreadsheet or table

    • score[0] score[1] score[2] score[3] score[4]
    90 95 87 89 98

  • Top row shows the indices for an array named "score"
  • Individual items are referenced by the index (a.k.a. subscript)
  • All the values are of the same type: int
  • Array size is 5

^ top

10.1.2: Declaring and Allocating Arrays

  • Consider an array named score containing 5 values
  • You declare and allocate memory for this array like this:
    • int score[5];
  • This is like declaring 5 variables of type int numbered as follows:
    • score[0], score[1], score[2], score[3], score[4]
  • The value in brackets is called an index
  • Individual values in an array are called items or elements
  • The number of indexed variables in an array is the size of the array
    • The largest index is one less than the size
    • The first index value is zero
  • Array declaration syntax:
    • DataType arrayName[size];
  • Arrays can be of any data type
  • All the variables of an array are always of the same data type
    • Known as the base type of the array
  • Once created, you cannot change the number of elements
  • The best way to specify the size of an array is to use a constant
    • const int NUMBER_OF_STUDENTS = 50;
int score[NUMBER_OF_STUDENTS];
  • This allows you to know the size anywhere in your code
  • If you need to change the size, you change only a single constant and recompile

^ top

10.1.3: Selecting Array Elements

  • Each array element is referenced by name and an index inside of square brackets
  • score[3] is one of the indexed variables of the score array
    • score[0]++;
  • The index can be any integer expression
    • int n = 2;
score[n + 1] = 99;
  • You can use an indexed array variable like any regular variable
    • score[0] = score[1] + 1;
    score[0]++;

^ top

10.1.4: Initializing Array Values

  • You can assign a value to an array element any time after it is declared
    • const int NUMBER_OF_STUDENTS = 5;
int score[NUMBER_OF_STUDENTS];
score[0] = 90;
score[1] = 95;
score[2] = 87;
score[3] = 89;
score[4] = 98;

Static Initialization

  • You can also initialize array elements in the declaration statement
    • Called initialization
    • Use a comma-separated list inside curly-braces
    int score[] = {90, 95, 87, 89, 98};
  • Produces the same array as the previous example
  • The size of the array is determine automatically from the list
  • If you want a longer array with only the first few elements initialized, you can use:
    • int score[NUMBER_OF_STUDENTS] = {90, 95, 87};

Unititialized Elements

  • Note that if you do not assign a value to an array element, its value is not known
  • Just like with regular variables, there are no default values assigned

^ top

10.1.5: Summary

  • Arrays are convenient ways to process a list of data
  • You declare and allocate space for an array with a single statement:
    • int score[5];
  • The best way to specify the size of an array is to use a constant
    • const int NUMBER_OF_STUDENTS = 50;
int score[NUMBER_OF_STUDENTS];
  • This allows you to know the size anywhere in your code
  • If you need to change the size, you change only a single constant
  • Each array element is referenced by name and an index inside of square brackets
  • You can use an indexed array variable like any regular variable
    • score[0] = score[1] + 1;
  • You can initialize array elements individually with an assignment statement
    • score[0] = 90;
  • A more convenient way is to use an initializer list
    • int score[NUMBER_OF_STUDENTS] = {90, 95, 87, 89, 98};

^ top

Exercise 10.1

In this exercise we explore declaring, allocating and assigning values to arrays containing lists of data.

Specifications

  1. Save the following code file as myarrays.cpp.
  2. Declare and allocate an array for a list of 100 integer grades.
  3. Declare and allocate an array of char vowels, assigning a value to each array element.
  4. Declare and allocate an array of double-precision values holding the temperatures 25, 30 and 40 in order.
  5. Declare and allocate a list of strings holding the names: Able, Baker and Charlie in order.
  6. Make sure your code compiles after every array that you declare and allocate.

    7. Note that you may get warnings about unused variables when you compile. Your code does compile with warnings and warnings are acceptable for this exercise.

  7. Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;

int main() {
    // A list of 100 integer grades

    // A list of chars holding vowels

    // A list of doubles holding temperatures

    // A list of strings holding names

    return 0;
}

^ top

10.2: Arrays and Loops

Objectives

At the end of the lesson the student will be able to:

  • Use loops to process array elements
  • Calculate statistics on lists of data stored in arrays

^ top

10.2.1: Processing Array Values in a Loop

  • Array processing is easily done in a loop
  • A for loop is commonly used to process array elements
  • For example, we can use a loop to display the contents of an array
    • int scores[] = {90, 95, 87, 89, 98};
for (int i = 0; i < 5; i++) {
    cout << scores[i] << endl;
}
  • Note the use of the constant length in the array loop

Initializing an Array

  • Similarly, we can initialize array elements to a known value:
    • const int NUMBER_OF_STUDENTS = 5;
int scores[NUMBER_OF_STUDENTS];
for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
    scores[i] = 100;
    cout << i << ": " << scores[i] << endl;
}

^ top

10.2.2: Initializing From the Keyboard

  • We can also use a loop to initialize values from the keyboard
    • const int NUMBER_OF_STUDENTS = 5;
int score[NUMBER_OF_STUDENTS];
cout << "Enter the score for each of the "
     << NUMBER_OF_STUDENTS << " students:\n";
for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
    cin >> score[i];
}
  • Note that the loop counter and array index counts from 0 to size - 1

Partially Filled Arrays

  • Note that until the above example finishes, only part of the array is filled
  • This is known as a partially-filled array
  • There is no automatic way to know how many values have been set in an array
  • Instead, the programmer must keep track of which values are entered
  • As shown above, this tracking is done using the index of the array

^ top

10.2.3: Calculating Statistics on an Array of Values

  • Since we can use a loop to access every item in an array, we can sum the array values
  • For example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}
  • What code would we add to show the average of the array values?
  • What would we change to find the maximum array value?
  • How would we find the minimum array value?
  • What is the easiest way to initialize minimum and maximum values?

^ top

10.2.4: Copying an Array

  • Sometimes you need to copy the values in one array to another array
  • This is easy to accomplish with a loop

Example of Copying an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    double prices1[] = {0.99, 1.99, 2.99, 3.99, 4.99};
    double prices2[5];

    for (int i = 0; i < NUMBER_ITEMS; i++) {
        prices2[i] = prices1[i];
    }


    for (int i = 0; i < 5; i++) {
        cout << i << ": " << prices1[i] << " = "
             << prices2[i] << endl;
    }
}

^ top

10.2.5: Array Index Out of Range

  • A common error is access an element outside the range of the array
  • For example, index values for int values[5] are the values 0 through 4
  • What if we tried to access array element 5?
  • Using an out of range index value does not produce an error message!
  • We can see this in the following example
  • Executing these statements usually does not seem to cause a problem
  • However, undetected problems like these may cause many different problems after the code is shipped
  • C++ code is infamous for these types of bugs

Example of Writing Values Beyond the Range of an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<iostream>
using namespace std;

const int SIZE = 3;

int main(void) {
    int values[SIZE];

    cout << "I will store 5 numbers in a 3-element array!\n";
    for (int i = 0; i < 5; i++) {
        values[i] = i + 1;
    }

    cout << "If you see this, the computer did not crash!\n";
    for (int i = 0; i < 5; i++) {
        cout << values[i] << endl;
    }
}

^ top

10.2.6: Summary

  • You can use loops to access every array element
  • For example, to assign values to an array and to display array values:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include<iostream>
using namespace std;

const int NUMBER_OF_STUDENTS = 5;

int main(void) {
    int score[NUMBER_OF_STUDENTS];

    cout << "Enter the score for each of the "
         << NUMBER_OF_STUDENTS << " students:\n";
    for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
        cout << "Student #" << i << ": ";
        cin >> score[i];
    }

    cout <<"You entered:" ;
    for (int i = 0; i < NUMBER_OF_STUDENTS; i++) {
        cout << score[i] << endl;
    }
}
  • Another use for loops is to sum the values of an array
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}
  • You can also use loops to compute an average, find a minimum or a maximum
  • Loops also allow you to copy all the values from one array and save them in another array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    double prices1[] = {0.99, 1.99, 2.99, 3.99, 4.99};
    double prices2[5];

    for (int i = 0; i < NUMBER_ITEMS; i++) {
        prices2[i] = prices1[i];
    }


    for (int i = 0; i < 5; i++) {
        cout << i << ": " << prices1[i] << " = "
             << prices2[i] << endl;
    }
}
  • The programmer must be very careful to keep the array index within bounds
  • Accessing an array element outside the bounds of an array can cause many problems
    • However, there is no warning by the compiler
  • This is a large source of bugs in C++

^ top

Exercise 10.2

In this exercise we explore using a loop to access every array element.

Specifications

  1. Save the following code file as arrayminimum.cpp.
  2. Add code to find and display the minimum value of the data in the array.
  3. Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 5;

int main(void) {
    int data[] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < NUMBER_ITEMS; i++) {
        sum = sum + data[i];
        cout << data[i] << ", ";
    }
    cout << "\nsum = " << sum << endl;
}

^ top

10.3: Arrays and Functions

Objectives

At the end of the lesson the student will be able to:

  • Pass arrays elements as arguments
  • Pass entire arrays as arguments
  • Use arrays in functions
  • Change array elements in functions

^ top

10.3.1: Array Elements as Arguments

  • Indexed variables can be arguments to functions
  • For example, if a program contains these declarations:
    • int i, n, a[10];
void myFunction(int n);
  • You can use indexed variables a[0] through a[9] as arguments
    • myFunction(a[0]);
myFunction(a[3]);
myFunction(a[i]);

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 3;

/**
 * Displays a double to the screen
 */
void showPrice(double value);

int main() {
    double data[] = {12.3, 23.45, 3.456};
    for (int  i = 0; i < NUMBER_ITEMS; i++) {
        showPrice(data[i]);
    }
}

void showPrice(double value) {
    cout.setf(ios::fixed);     // fixed, not scientific
    cout.setf(ios::showpoint); // show decimal point
    cout.precision(2);         // show 2 decimal places
    cout << '$' << value << endl;
}

^ top

10.3.2: Arrays as Function Parameters

  • Can use an entire array as an argument to a function
  • When calling the array, use just the array name and no brackets
    • showArray(scores, NUMBER_OF_STUDENTS);
  • To pass an array, the function must have an array parameter
  • You declare an array parameter using empty brackets in the parameter list
    • void showArray(int values[], int size);
  • Following example shows an array used in a function:
    • void showArray(int values[], int size) {
    for (int i = 0; i < size; i++) {
        cout << values[i] << " ";
    }
}
  • Note the use of the size variable
  • You do not know the size of the array that will be passed
  • Size of the array passed can be different for each call
  • So need to pass a size variable to the function
  • You could easily overload the showArray function for different array types

^ top

10.3.3: Changing Array Elements in Functions

  • Array parameters behave much like call-by-reference parameters
    • The function has access to and can change the original array
  • The values of the indexed variables can be changed by the function
  • You can even collect input in a function for an array

For Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include<iostream>
using namespace std;

const int NUMBER_ITEMS = 3;

// Fills an array with int values from the keyboard
void fillUp(int a[], int size);

// Displays an array to the screen
void showArray(int a[], int size);

int main() {
    int data[NUMBER_ITEMS];
    fillUp(data, NUMBER_ITEMS);
    showArray(data, NUMBER_ITEMS);
}

void fillUp(int data[], int length) {
    cout << "Enter " << length << " numbers:\n";
    for (int i = 0; i < length; i++) {
        cin >> data[i];
    }
}

void showArray(int values[], int size) {
    cout << "You entered " << size << " numbers:\n";
    for (int i = 0; i < size; i++) {
        cout << values[i] << endl;
    }
}

Using the const Modifier

  • Normally, a function can change the values of array elements
  • You can prevent the modification using the const modifier
    • void showArray(const int values[], int size);
  • The compiler will issue error messages if you accidentally change an array element
  • For example, if you used const and made a mistake in showArray:
    • void showArray(const int values[], int size) {
    for (int i = 0; i < size; i++) {
        values[i]++;  // error
        cout << values[i] << endl;
    }
}
  • Using const, the compiler gives us a message like:
fillup.cpp: In function `void showArray(const int*, int)':
fillup.cpp:27: increment of read-only location
  • If a function with a constant array parameter calls another function using the const array parameter as an argument...
    • The called function must use a const array parameter as well
    • Otherwise, the compiler will issue an error

^ top

10.3.4: Returning an Array

  • Recall that functions can return a value of type int, double, char, or even a class type like string
  • However, functions cannot return arrays
  • Later, we learn how to return a pointer to an array
  • Returning a pointer accomplishes much of the same thing

^ top

10.3.5: Summary

  • Indexed variables can be arguments to functions
  • You can also pass an entire array as an argument to a function
  • To pass an array, the function must have an array parameter
    • void showArray(int a[], int size);
  • Important to pass the size of the array as well
  • Array parameters behave much like call-by-reference parameters
  • The function has access to and can change the original array
  • You can prevent the modification using the const modifier
    • void showArray(const int a[], int size);
  • Functions cannot return arrays

^ top

Exercise 10.3

In this exercise we explore passing an array to a function.

Specifications

  1. Save the following code file as onemore.cpp.
  2. Write a definition for the function addOne() that has a parameter for an int[] and adds one to each element of the array.
  3. Submit your source-code file as the answer to this exercise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;

const int SIZE = 5;

void addOne(int data[], int size);

void showArray(int values[], int size);

int main() {
    int data[SIZE] = { 1, 2, 3, 4, 5 };

    showArray(data, SIZE);
    addOne(data, SIZE);
    showArray(data, SIZE);

    return 0;
}

void showArray(int values[], int size) {
    cout << "You entered " << size << " numbers:\n";
    for (int i = 0; i < size; i++) {
        cout << values[i] << endl;
    }
}

// Write function definition here

^ top

10.4: Array Programming Techniques

Objectives

At the end of the lesson the student will be able to:

  • Use partially-filled arrays to solve the fixed-array-size problem
  • Test array equality
  • Search an array
  • Sort an array
  • Understand when to use binary search

^ top

10.4.1: Partially-Filled Arrays

  • You often do not know how large to make an array
  • This is often the case when you use arrays interactively
  • You do not know how large to make the array until the user tells you
  • A common solution to this size problem is to:
    1. Declare the array size to be the largest that could ever be needed
    2. Use code that can deal with partially-filled arrays
  • Consider the following example that takes a list of scores and computes how far any score differs from the average

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/**
 * Shows the difference between each of a list of
 * scores and their average.
 */
#include <iostream>
using namespace std;

const int MAX_NUMBER_SCORES = 10;

/**
 * Partially fills an array and returns the number
 * of elements used.
 */
void fillArray(int a[], int size, int& numberUsed);

/**
 * Returns the average of numbers a[0] through
 * a[numberUsed - 1]
 */
double computeAverage(const int a[], int numberUsed);

/**
 * Displays how much each of the first numberUsed
 * elements differ from their average
 */
void showDifference(const int a[], int numberUsed);

int main(void) {
    int score[MAX_NUMBER_SCORES], numberUsed;

    cout << "This program reads scores and shows how\n"
         << "much each differs from the average.\n";

    fillArray(score, MAX_NUMBER_SCORES, numberUsed);
    showDifference(score, numberUsed);

    return 0;
}

void fillArray(int a[], int size, int& numberUsed) {
    cout << "Enter up to " << size
         << " nonnegative whole numbers.\n"
         << "Enter a negative number when finished.\n\n";

    int next = 0, index = 0;
    while ((next >= 0) && (index < size)) {
        cout << "Enter score #" << (index + 1) << " : ";
        cin >> next;
        if (next > 0) {
            a[index] = next;
            index++;
        }
    }

    numberUsed = index; // return numberUsed
}

void showDifference(const int a[], int numberUsed) {
    double average = computeAverage(a, numberUsed);
    cout << "Average of the " << numberUsed
         << " scores = " << average << endl
         << "The scores are:\n";
    for (int index = 0; index < numberUsed; index++) {
        cout << a[index] << " differs from average by "
             << (a[index] - average) << endl;
    }
}

double computeAverage(const int a[], int numberUsed) {
    double total = 0;
    for (int index = 0; index < numberUsed; index++) {
        total = total + a[index];
    }
    if (numberUsed > 0) {
        return (total / numberUsed);
    } else {
        cout << "ERROR: number of elements is 0.\n"
             << "computeAverage returns 0.\n";
        return 0;
    }
}

Notes About Array-Size Parameters

  • Function fillUp needs to know the array size
  • Other functions only need to know how many elements to use
  • Note that when function fill_array is called, MAX_NUMBER_SCORES is an argument
  • Why not use MAX_NUMBER_SCORES directly without passing it as an argument?
    • Using MAX_NUMBER_SCORES as an argument makes it clear that fillArray requires the array's declared size
    • This makes fillArray easier to use in other programs

^ top

10.4.2: Testing Array Equality

  • Sometimes you have two arrays and you want to compare whether or not they are the same
    • int a[] = {1, 2, 3};
int b[] = {1, 2, 3};
  • You may be tempted to use == to test for equality
    • if (a == b) {
    // do something
}
  • However, this may have unexpected results

For Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>
using namespace std;

int main() {
    int a[] = {1, 2, 3};
    int b[] = {1, 2, 3};
    if (a == b) {
        cout << "a == b\n";
    } else {
        cout << "a != b\n";
    }

    return 0;
}
  • Remember that arrays store values in sequential memory locations
  • Thus, different arrays store values in different memory locations
  • Tests using == checks if the base memory addresses are the same
    • if (a == b)
  • Tests if both arrays have the same memory address

Testing Array Elements for Equality

  • To test array elements for equality, you need to check each element
  • Define an equals function that returns true if and only if all the array elements are equal
  • Arrays must also be the same size
  • Updating our previous code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
using namespace std;

const int NUM_ELEMENTS = 3;

bool equals(int a[], int b[], int length);

int main() {
    int a[] = {1, 2, 3};
    int b[] = {1, 2, 3};
    if (a == b) {
        cout << "a == b\n";
    } else {
        cout << "a != b\n";
    }
    if (equals(a, b, NUM_ELEMENTS) == true) {
        cout << "a equals b\n";
    } else {
        cout << "a not equal to b\n";
    }

    return 0;
}

bool equals(int a[], int b[], int length) {
    for (int i = 0; i < length; i++) {
        if (a[i] != b[i]) {
            return false;
        }
    }
    return true;
}

^ top

10.4.3: Arrays of Objects

  • Any type can be made into an array, including class types
    • Product prods[10];
  • In the following, array elements are objects
  • You can call methods of the objects stored in each array element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include "product.cpp"
using namespace std;

const int NUM_PRODS = 3;

int main(void) {
    // Create 3 Product objects
    Product milk("Milk", 3.95);
    Product bread("Bread", 1.09);
    Product cheese("Cheese", 4.59);

    // Assign objects to an array
    Product store[] = { milk, bread, cheese };

    // Display Products using a loop
    for (int num = 0; num < NUM_PRODS; num++) {
        Product prod = store[num];
        cout << prod.getName() << " @ ";
        cout << store[num].getPrice();
        cout  << endl;
    }
    return 0;
}

Notes on the Code

  • Code that accesses each individual array element
    • Product prod = store[num];
  • Code that calls a function on each array element
    • cout << store[num].getPrice();

^ top

10.4.4: Sequentially Searching an Array

  • Sometimes you want to find out if a particular value exists in an array
  • This is known as searching an array
  • An easy and straightforward algorithm is sequential search
  • In sequential search you:
    • Start at the beginning of the array
    • Compare each value in the array until:
      • If the value is found, then return found
      • If you reach the end of the array, return not found
  • The following example demonstrates sequential search

Example of Sequential Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include<iostream>
using namespace std;

int search(const int array[], int size, int valueToFind);

void showArray(const int values[], int size);

int main(void) {
    const int SIZE = 7;
    int data[] = {-12, -4, 7, 10, 14, 21, 29};
    int valueToFind = 1;

    cout << "For the array:\n";
    showArray(data, SIZE);

    cout << "Enter the value to find (0 to exit): ";
    cin >> valueToFind;
    while (valueToFind != 0) {
        int index = search(data, SIZE, valueToFind);

        if (index > 0) {
            cout << "and found " << data[index] << endl;
        } else {
            cout << "but did not find " << valueToFind
                 << endl;
        }

        cout << "Enter the value to find (0 to exit): ";
        cin >> valueToFind;
    }
}

int search(const int array[], int size, int valueToFind) {
    int index = -1;
    int i = 0;
    for (i = 0; (index == -1) && (i < size); i++) {
        if (valueToFind == array[i]) {
            index = i;
        }
    }
    cout << "Completed search after looking at "
         << i << " array elements\n";
    return index;
}

void showArray(const int values[], int size) {
    for (int i = 0; i < size; i++) {
        cout << values[i] << " ";
    }
    cout << endl;
}
  • On average, would it be any faster to start searching at the end of an array?
  • If an array is sorted, then we can program faster methods -- binary search

^ top

10.4.5: Sorting an Array

  • Sorting is a common task for computers, for example:
    • Sort numbers in ascending order
    • Sort numbers in descending order
    • Sort strings in alphabetic order
  • Many different algorithms for sorting, including:
    • Bubble sort - move item up until in right place
    • Insertion sort - add elements to list one at a time
    • Selection sort - pick 1st, then 2nd, etc.
    • Quick sort - divide and conquer

Selection Sort

  • Selection sort is one of the easiest -- but not the most efficient
  • General algorithm:
    1. Find the smallest element
    2. Swap with the first element
    3. Find the smallest element in the rest of the list
    4. Swap with the first element of the rest of the list
    5. Repeat until the list is sorted

    Pass a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    Original 10 7 29 14 -4 -12 21
    First -12 7 29 14 -4 10 21
    Second -12 -4 29 14 7 10 21
    Third -12 -4 7 14 29 10 21
    Fourth -12 -4 7 10 29 14 21
    Fifth -12 -4 7 10 14 29 21
    Sixth -12 -4 7 10 14 21 29

  • How many passes were needed for a seven element array?

Selection Sort Code

  • Following is selection sort code
  • Have added some statements to show action for each pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>
using namespace std;

const int NUMBER_ITEMS = 7;

/**
 * Sorts the array so that
 * a[0] <= a[1] <= ... <= a[numberUsed - 1]
 */
void sort(int data[], int numberUsed);

/**
 *Interchanges the values of variable1 and variable2.
 */
void swapValues(int& variable1, int& variable2);

/**
 * Returns the index i such that data[i] is the
 * smallest value between data[start] and data[end].
 */
int findMin(const int data[], int start, int end);

/**
 * Displays an array to the screen
 */
void showArray(int a[], int length);

int main() {
    int a[] = {10, 7, 29, 14, -4, -12, 21};

    cout << "Original: ";
    showArray(a, NUMBER_ITEMS);
    sort(a, NUMBER_ITEMS);
    cout << "\nSorted array:   ";
    showArray(a, NUMBER_ITEMS);
    cout << endl;

    return 0;
}

void sort(int data[], int numberUsed) {
    int indexOfMin;
    //Place the correct value in a[index]:
    for (int index = 0; index < numberUsed - 1; index++) {
        indexOfMin =  findMin(data, index, numberUsed);
        swapValues(data[index], data[indexOfMin]);
        cout << "Pass#" << index << ": ";  // tracing
        showArray(data, numberUsed);       // tracing
    }
}

void swapValues(int& variable1, int& variable2) {
    cout << "\nSwapping " << variable1
         << " with " << variable2 << endl; // tracing
    int temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}


int findMin(const int data[], int start, int end) {
    int indexOfMin = start;
    for (int i = start + 1; i <= end; i++) {
        if (data[i] < data[indexOfMin]) {
            indexOfMin = i;
        }
    }
    return indexOfMin;
}

void showArray(int values[], int length) {
    for (int i = 0; i < length; i++) {
        cout << values[i] << "  ";
    }
}
  • Note that every element in the array must have a value
  • Can the array have duplicate items?
  • Also note that the larger task was broken into smaller tasks using functions
    • Helps to organize program and improve clarity

What About Bubble Sort?

  • Another sorting algorithm that is easy to understand and use
  • General algorithm:
    1. Make length passes through the array
    2. For each pass, compare each array element with the next element
    3. If the current element is larger than the next one, swap them
  • Not an efficient sorting algorithm
  • Sometimes simple algorithms perform poorly
  • Simple algorithms are still useful: easy to program and understand
  • If better performance is needed, replace with a better algorithm
  • More information: Sorting Algorithms

^ top

10.4.6: Binary Search

  • Once an array is sorted, can use binary search to find an item
  • Binary search is much faster than sequential search

Binary Search Algorithm

  • A key value is searched for among the values stored in the array.
  • Two index variables lowIdx and highIdx are used to limit the scope of the search.
  • The search proceeds until the element searched for is found or the scope between lowIdx and highIdx is exhausted.
    • The index middleIdx is computed as (lowIdx + highIdx) / 2.
    • If key = data[middleIdx] the search is successful.
    • If key < data[middleIdx], highIdx is lowered to middleIdx.
    • If key > data[middleIdx], lowIdx is raised to middleIdx.
    • If the scope between lowIdx and highIdx is exhausted, the search is unsuccessful.
  • Visual demonstration: BinarySearch

Binary Search Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
using namespace std;

const int NUMBER_ITEMS = 7;

/**
 * Find the index of key in array a
 * return -1 if key is not found
 */
int binarySearch(int a[], int length, int key);

/**
 * Displays an array to the screen
 */
void showArray(int a[], int length);

int main(void) {
    int a[] = {-12, -4, 7, 10, 14, 21, 29};

    int key = 14;
    cout << "Searching array: ";
    showArray(a, NUMBER_ITEMS);
    int index = binarySearch(a, NUMBER_ITEMS, key);
    cout << "Index of " << key << " = "
         << index << endl;
}

int binarySearch(int a[], int length, int key) {
    int step = 0; // tracing
    int lowIdx = 0;
    int highIdx = length - 1;
    int middleIdx;
    while (lowIdx <= highIdx) {
        step++;
        middleIdx = (lowIdx + highIdx) / 2;
        cout << "Step#" << step
             << " lowIdx=" << lowIdx
             << " highIdx=" << highIdx
             << " middleIdx=" << middleIdx
             << endl; // tracing
        if (a[middleIdx] == key) {
            return middleIdx;        // just right
        } else if (a[middleIdx] < key) {
            lowIdx = middleIdx + 1;  // too small
        } else {
            highIdx = middleIdx - 1; // too big
        }
    }
    return -1; // not found
}

void showArray(int values[], int length) {
    for (int i = 0; i < length; i++) {
        cout << values[i] << "  ";
    }
    cout << endl;
}

How Much Faster is Binary Search?

  • Given the sorted array:

    • a[0] a[1] a[2] a[3] a[4] a[5] a[6]
    -12 -4 7 10 14 21 29

  • How many steps to find the value of 14 using sequential search?
  • How many steps to find the value of 14 using binary search?
  • On average for an array of n elements:
    • Sequential search takes n / 2 steps
    • Binary search takes 2 * log2(n) + 2 steps maximum
  • Translating to some array sizes:

    • Array Size floor(log2(n)) + 1
    1 1
    10 4
    100 7
    1000 10
    10,000 14

  • Binary search quickly becomes worth the effort of its implementation
  • Binary search is one algorithm a programming professional should know!

^ top

10.4.7: Summary

  • You can easily enter values into an array for later processing
  • A "partially filled array" is one in which values are stored in an initial segment of the array
  • You use partially-filled arrays when you do not know how large to make to make the array
  • To compare two arrays, you cannot use == on the whole array
  • Instead, you must loop through both arrays and compare each element
  • You can create arrays of objects by specifying a class type
    • Product store[10];
  • When an array contains an object, you can call a function of the object using an array element
    • cout << store[num].getPrice();
  • You can search arrays sequentially to find a value
  • Sorting algorithms can sort array elements into ascending or descending order
  • If an array is sorted, you can use binary search to speed the search process

Check Yourself

  1. If you want to use only part of an array, do you track indexes or values?
  2. How can you solve the problem of not knowing how large to make an array?
  3. If you compare two arrays containing the same values, why does == return false?
  4. If you have an array constructed as follows, how do you call the show() function of the first array element?
    5. Product milk("Milk", 3.95);
Product bread("Bread", 1.09);
Product cheese("Cheese", 4.59);
Product store[] = { milk, bread, cheese };
  5. Why is binary search faster than sequential search?
  6. What condition must an array be in before you can use binary search?

^ top

Exercise 10.4

In this exercise we write a short program that stores char values in an array and then processes the values

Specifications

  1. Save the following code as reverse.cpp
  2. Add the code to read in 10 characters from the user and display the characters in reverse order.
  3. Submit your program along with your other exercises for this lesson.
1
2
3
4
5
6
7
8

#include <iostream>
using namespace std;

int main() {
    // Enter code here

    return 0;
}

One possible answer.

^ top

Wrap Up

^ top

Home | WebCT | Announcements | Day Schedule | Eve Schedule
Course info | Help | FAQ's | HowTo's | Links

Last Updated: November 13 2005 @11:29:58