Logout

4.2 Connecting computational thinking and program design (22 hours)


4.2.1

Describe the characteristics of standard algorithms on linear arrays.

 

Teaching Note:

These are: sequential search, binary search, bubble sort, selection sort.

JSR Notes:

So, for these, I'll give a brief, "canned" answer, but also link below to the Java Revolution notes for each for more details.

Note: for these algorithms, "key" is the data being searched for.

330     notes  Sorting
335 animation 340 notes Searching


Sequential Search


Start at the beginning, and go through each element, one at a time,
looking for the key.
If it is found, return the element at which it resides.
If reaching the end of the array, it has not been found, return an indication that it is not in the array, such as by returning a -1.

 

Binary Search

First, make sure the array is sorted.
Successively pick the middle element, and ask if it is the key.
If it is the key, return the element.
If it is not, ask whether the key is greater than or less than the present "mid".
And then, if the key is less than the present "mid", keep the "low" element the same, but make the "high" one less than the "mid",
whereas, if the key is greater than the present "mid", keep the "high" element the same, but make the "low" one greater than the mid.
If the "low" ever gets higher than the "high", that means the key was not found, so return an indication that it is not in the array, such as by returning a -1.

 

Bubble Sort

With successive passes through the array,
compare neighboring array element pairs, and
if the one on the left is greater than the one on the right,
swap them.
To make this more efficient, do one less comparison each pass, since one more gets bubbled up to the end each pass.
And check to see if no swaps are made in a single pass; if so, that means the array is already sorted.

 

Selection Sort

Assume that the 0th element is the smallest in the array,
and progress through the array, checking to see if any of the elements are smaller,
and if/when one is encountered which is smaller, flag it as being the current "smallest" of that pass.
Then at the end of each pass, if the "smallest" is not the one first assumed to be, swap them.
Since the next smallest will get put in its proper place each pass, start each pass one element beyond the last starting point.