Cit 120 Ch. 8

Front 1

What is a search algorithm? What are two methods of searching arrays?

Back 1

a method of locating a specific item in a larger collection of data

linear search, binary search

Front 2

What is another name for a linear search? How does it work?

Back 2

AKA sequential search

Uses a loop to sequentially step through an array, starting w/ first element. Stops when it encounters the correct item or reaches end of array

Front 3

What is a way of setting up a linear search so that you know whether it found the item or unsuccessfully reached the end?

Back 3

Finds it: return value

Does not: returns a flag or some other pre-set value like -1 that isn't part of the set

Also: position variable to flag element number, bool variable to indicate whether it's found

Front 4

What are the advantages and disadvantages of a linear search?

Back 4

+: simple, data doesn't have to be stored in a certain order

-: inefficient

Front 5

How does a binary search work? What does it require?

Back 5

Requires that values in the algorithm be sorted in order

Starts with element in middle. It is either greater or less than desired value. Keeps testing middle element to narrow it down

Front 6

How do you generally set up a binary search?

Back 6

Three index variables: first=0, middle, last=size-1

First and last mark boundaries of array currently being searched. Calculate and go to middle. If not found, middle becomes a new bound

If value is found at middle

Else if value is found in upper half

Else (value is then found in lower half)

Front 7

How do you calculate the maximum number of comparisons a binary search will make on an array of any size?

Back 7

Find the smallest power of 2 that is greater than or equal to the number of elements

e.g. a max of 16 comparisons will be made on an array of 50,000 elements (2^16=65,536)

Front 8

What does a sorting algorithm do? What are two simple sorting algorithms?

Back 8

Arranges data in some order

bubble sort, selection sort

Front 9

What does a bubble sort do? How does it work?

Back 9

Arranges data in ascending or descending order

Compares array elements next to each other and determines if they need to be swapped. Continues until no swaps are made

Front 10

Pseudocode for bubble sort

Back 10

do{

swap flag = false

for{ count is set to subscript 0 to last-1

If array[count] is greater than array[count+1]

swap contents of array elements

}

}while (swap flag=true) //while(swap)

Front 11

Which is more efficient and why: bubble sort vs. selection sort

Back 11

Selection sort is more efficient. Bubble moves one element at a time. Selection immediately moves items to their final position in the array

Front 12

How would a selection sort work for putting items in ascending order?

Back 12

Find smallest element. Put in position zero. Begin scan at next element. Find next smallest. Put in next position. Etc.

Front 13

Pseudocode for selection sort

Back 13

For startScan is set to each subscript in array from 0 to last-1{

Set index variable = to startScan

Set minIndex variable = to startScan

Set minValue variable = to array[startScan]

for index is set to each subscript from (startScan+1) to last{

if array[index]

set minValue = to array[index]

set minIndex to index } }

set array[minIndex] = to array[startScan]

set array[startScan] = to minValue }

Front 14

Another explanation of selection sort in English

Back 14

two nested for loops. inner loop sequences through array starting at [startScan+1], searching for element with smallest value. When found, subscript is stored in minIndex and value is stored in minValue. Outer loop then makes this the new start point

Front 15

Is it ever good programming practice to sort parallel arrays in such a way that they are no longer synchronized?

Back 15

no

Front 16

Can these sorting and searching algorithms be used for vectors as well?

Back 16

Yes

Simply replace the array syntax with the vector syntax where necessary