Transcript Array Algorithms

Array Algorithms
CS0007: Introduction to Computer Programming
Review
 Arrays are…
 complex variables that can hold multiple values of the same data type.
 The size declarator indicates…
 the number of elements the array can hold.
 Individual values inside of an array are called…
 elements.
 An element’s index (or subscript) is…
 a uniquely identifying number that is used to pinpoint its position in
the array.
 The enhanced for loop is…
 a special loop that iterates through the elements in a collection (in this
case array) and allows access to each element.
Comparing Arrays
 Sometimes you want to know if two arrays contain all of the same elements.
 What would be the output?
int[] firstArray = {1, 2, 3, 4, 5};
int[] secondArray = {1, 2, 3, 4, 5};
if(firstArray == secondArray)
System.out.print("The arrays are the same!");
else
System.out.print("The arrays are NOT the
same!");
 Answer: “The arrays are NOT the same”
 Why?

Because the == operator compares the references in the array variables and they point to two different objects
 How do we fix it?
We iterate through each the arrays and compare them element by element
 Example: ArrayComparison.java

Sum, Average, and Minimum and
Maximum
 Four common algorithms used with arrays:
 Sum of all the elements in the array (ArraySum.java)
 Average of all the elements in the array (ArrayAverage.java)
 Minimum element in the array (ArrayMin.java)
 Max element in the array (ArrayMax.java)
Partially Filled Arrays
 Sometimes you need to stores a series of items in an array,
but you don’t know the number of items there are.
 Solutions?
 One solution is to create and array with the size being equal to the
maximum number of possible items.
 Problem?
o If you do not fill the entire array, the array will only be partially
filled.
o If you go to process the items in the array, you need to only process
valid items.
• Solution?
• You must keep track of the number of items you have currently in
the array, as well.

Example: PartialArray.java
The Sequential Search Algorithm
 Arrays are known as a data structures.
 A Data Structure is a particular way of storing and organizing data in
a computer so that it can be used efficiently.
 There are many, many data structures and many are provided by the
Java API.
 The array is one of the more simple ones.
 Although arrays are very useful, they may not be the most efficient
structure depending on the situation you want to use them.
 For instance, if you need to find an element with a specific value in an array,
what can you do?
 Simplest answer: look at every element in the array starting from the
begining and see if it is the one we are looking for.
o This is called the Sequential Search Algorithm (SequentialSearch.java).
The Sequential Search Algorithm
 If we are talking about speed in terms of number of comparisons,
what is the worst case scenario for the Sequential Search
Algorithm?
 The element we are looking for is the last element of the array.
 If there are n elements, that means we have to check n elements in the worst
case.
 If there are n elements in the array what is the average case?
 n+1/2 comparisons.
 There are data structures that can theoretically perform better in
the worst case
 There are search algorithms that can perform better in the average
case
 We will revisit this in a bit.
The Selection Sort Algorithm
 Another thing we often want do to with data, besides search it, is
to sort it.
 Names, grades, scores, etc.
 Probably the most simple sorting algorithm is the Selection Sort
Algorithm.
 The Selection Sort Algorithm works as follows:
1. Search the array for the smallest element
2. Swap the first element with the smallest element
3. The first element is holding the correct value, so no longer consider it in
the sort
4. Repeat previous steps for rest of array until the array is completely sorted.
 Example: SelectionSort.java
 There are many, many more sorting algorithms, most of which are
more efficient than Selection Sort.
Binary Search
 Sequential Search does not scale well to arrays with a large number of elements.
 As stated before, there are many, many searching algorithms. One of which is
the Binary Search Algorithm.
 The general idea of Binary Search assumes that the array is sorted in ascending
order, and it uses this knowledge to incrementally eliminate half of the elements
from the array.
 The algorithm is as follows:
1.




Compare the target value to the element in the middle of the sorted array
If they are the same, the search ends
If the target value is larger than the element, then you know every element to the left of
the middle is also not the element.
o Eliminate all values to the left of the middle and repeat step 1 with the elements left
in the array.
If the target value is smaller that the element, then you know every element to the right
of the middle is also not the element.
o Eliminate all values to the right of the middle and repeat step 1 with the elements
left in the array.
If there is no more elements to eliminate in the array, the target value is not in the array.