Memory, Search and Sorting

A computer's memory

Let's try swapping the values of variables

Let's try swapping the values of variables inside a method

Memory addresses

Passing primitive variables

When we pass primitive types as arguments to a method, we are passing copies of the arguments. So the value of the original variables cannot be changed inside a method

Passing array variables

Arrays are a reference type

Passing array variables (reference types )

When we pass reference types as arguments to a method, we are passing the memory address of the arguments. So the values of the original variables CAN be changed inside a method

Passing by value

When we pass primitive types as arguments to a method, we are passing copies of the arguments. So the value of the original variables cannot be changed inside a method

Primitive types:

int, long (Integer numbers)
float, double (Decimal/Floating point numbers))
char (Single characters)
boolean (Boolean )
String

Passing by reference

When we pass reference types as arguments to a method, we are passing the memory address of the arguments. So the values of the original variables CAN be changed inside a method

Reference types:

Arrays (int[], String[] )
Scanner
Random
Anything you initialize with the new keyword

Search

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Linear Search

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Linear Search

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Linear Search

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Linear Search

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Linear Search

There are numbers behind the doors.
You are asked to find if the number 11 is behind any of the doors

We needed 5 steps to find the number

The worst case

What if the number is not in the array?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

What if the number is not in the array?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

What if the number is not in the array?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

What if the number is not in the array?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

We had to go through ALL the elments of the array

Linear Search

 
Given an array of N items, and a target to search
For every position i in the array {
    if the item as position i is our target{
       Finish! We found our target!
    }
}

The array is sorted! Let's use that information

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors

Let's start by checking the middle of the array

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

11 is greater than 7. If it is in the array, it must be to the right of 7.

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

11 is smaller than 13. If it is in the array, it must be to the left of 13.

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

We found 11!.

The worst case

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

Let's start by checking the middle of the array

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

25 is greater than 7. If it is in the array, it must be to the right of 7.

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

25 is greater than 13. If it is in the array, it must be to the right of 13.

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

25 is greater than 17. If it is in the array, it must be to the right of 17.

What if we know the array is sorted?

There are numbers behind the doors. You are asked to find if the number 25 is behind any of the doors

25 is greater than 19. We cannot continue subdividing the array, so 25 was not found.

What if we know the array is sorted?

For 8 doors, we had to d 4 comparisons in the worst case

What if we know the array is sorted?

For 8 doors, we had to d 4 comparisons in the worst case

This procedure is know as binary search

Binary Search

 
Given an array A of N items, and a target to search
Let start = 0, end = N-1
while target not found{
    Set mid = (start + end)/2
    if A[mid] is our target{
       Finish! We found our target!
    }
    else{
        if A[mid] < target{
            set start = mid + 1
        }
        else if A[mid] > target{
            set end = mid - 1
        }
    }
}

In the worst case, how many comparisons do we make?

Given an array of N items, and a target that is not in the array

For Linear Search:

We have to do N comparisons

For an array of 8 elements: 8 comparisons
For an array of 128 elements: 128 comparisons
For an array of N elements: N comparisons

In the worst case, how many comparisons do we make?

Given an array of N items, and a target that is not in the array

For Binary Search:

We have to do as many comparisons as we can split the array in 2.
We have to do as many comparisons as we can split the array in 2, plus 1.
- For an array of 8 elements: we split 8 into 4, 4 into 2, 2 into 1, and the compare the last element. 4 comparisons
- For an array of 128 elements: 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1, plus the final comparison. 8 comparisons
- For an array of N elements: N → N/2 → N/4 → ... → 2 → 1, plus the final comparison. log(N) + 1 comparisons.

How much faster is binary than linear search?

We say that an algorithm is faster than another if it performs less operations

In this case, the operations we measure are the number of comparisons

Sorting

To take elements out of order and put them in some order (e.g. ascending order)

Sorting

To take items that are out of order and put them in some order (e.g. ascending order)

Names in a phone book
Grades in a class
Scores in a competition

The items need to be comparable

Sorting

To take items that are out of order and put them in some order (e.g. ascending order)

Sorting

To take items that are out of order and put them in some order (e.g. ascending order)

Bubble sort!

 
Start with an unsorted array A with N items

while the array is unsorted{

    For every position between 1 and N {

        if A[i] and A[i-1] are not in the correct order{

           Swap A[i] and A[i-1]

        }

    }

}

How fast is bubble sort?

Insertion sort!

 
Start with an unsorted array A with N items

For every pos between 1 and N {
    
    Let j = pos_a 
    Let ITEM = A[pos]
    
    While j > 0 and  ITEM is greater than A[j -1] {

        Set A[j] = A[j-1]
        Decrease j by 1

    }

    Set A[j] = ITEM
}

How fast is insertion sort?

Why is insertion sort faster?

Resources

I'll put something here after class

Resources

I'll put something here after class