10-29-2018 Chapter 6 Notes PDF

Preview

Summary

Dr. Juyeon Jo - These are the notes that correspond with the chapter in Computer Science 135....

Description

Common tasks performed on arrays -

Searching and sorting

Search -

Given a series of values and a target value, find out if the target is present and where it is located o 2 possible outcomes – success or failure o If list of items to be searched is in an array, we can use sequential search  Start at beginning of the array and compare the target to each value until a match is found (success) or there are no more values in the array (failure)

Sample Searches -

List n = 10 0 1 0

-

1 2 3 1 2

3 4 5 1 7

5 6 8 2 3

7 1 4

8 9 6 1 9

If target = 12, value returned by search is 2 If target = 23, value returned by search is 6 If target = 13, value returned by search is -1

Sorting -

-

The importance of sorting is evident Applications: o Sorting a column in Excel o Organizing your iTunes playlists by artist name o Ranking a high school graduating class o Finding a median score to report on an exam o Countless others… Sorting – given a series of values, rearrange the values into a logical order o 2 sorting orders o Ascending – smallest to largest (for strings this is alphabetical order) o Descending – largest to smallest

Is it interesting? -

Give me 100 names written on 100 index cards and I can sort them, no problem One way to remind yourself that it’s tricky is by increasing the problem size

Computers are stupid -

A computer can’t “jump” to the M section, unless you explicitly create an M section or something For most common sorts, the computer has to compare two numbers (or strings) at a time Based on that comparison, it has to take another step in the algorithm Remember, we can swap things around in an array

Bubble sort is a classic sorting algorithm -

It is very simple to understand It is very simple to code It is not very fast The idea is simply to go through your array, swapping out of order elements until nothing is out of order

Single pass example -

Run through the whole array, swapping any entries that are out of order

Sorting -

Bubblesort sorting strategy o Decide on desired sorting order (ascending or descending) o Perform the following: 1. Move through the list comparing adjacent values 2. If adjacent values are out of desired order, interchange them 3. When a complete pass through the list has been made, the smallest (largest) value will have “bubbled” to its proper location 4. Repeat steps 1 and 3 ignoring the already sorted values (requires length-1 passes through the list)

Sample sort

-

void bubblesort(int list[], int count) { int temp; for (int i=0; I < count-1; i++) for (int j=0; j < count – (i + 1); j++) { temp = list[j]; list[j] = list[j + 1]; list [j + 1] = temp; } } count = 5 j < count – (I + 1)

Bubblesort -

Conversion to an ascending sort o change relational operator in the if statement to > (greater than) to find the largest value of the list on each iteration Two Dimensional Arrays

Parallel Arrays -

Two (or more) arrays are called parallel if their corresponding components hold related information Example: o int studentId[50]; o char courseGrade[50];

2345 A 6 8672 B 3 2235 C 6 9273 B 3 1189 D 2 Two and Multidimensional Arrays -

-

Two-dimensional array – collection of a fixed number of components (of the same type) arranged in two dimensions o Sometimes called matrices or tables Declaration syntax: datatype arrayName[intExp1][intExp2];

Two-Dimensional Array Initialization During Declaration -

Two-dimensional arrays can be initialized when they are declared Elements of each row are enclosed within braces and separated by commas All rows are enclosed within braces For number arrays, if all components of a row aren’t specified, unspecified ones are set to 0

Processing Two-Dimensional Arrays -

Ways to process a two-dimensional array: o Process the entire array o Process a particular row of the array, called row processing o Process a particular column of the array, called column processing

-

Each row and each column of a two-dimensional array is a one-dimensional array

Initialization -

-

To initialize row number 4 (i.e., fifth row) to 0: row = 4; for (col = 0; col < NUMBER_OF_COLUMS; col++) matrix[row][col] = 0; To initialize the entire matrix to 0; for (row = 0; row < NUMBER_OF_ROWS; row++) for (col = 0; col < NUMBER_OF_COLUMS; col++) matrix[row][col] = 0;

Print -

To output the components of matrix: for (row = 0; row < NUMBER_OF_ROWS; row++) { for (col = 0; col < NUMBER_OF_COLUMS; col++) cout...