Sorting and Recursion

New survey!

Visualizing sorting algorithms

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]

        }

    }

}

Insertion sort!

 
Start with an unsorted array A with N items

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

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

    }

    Set A[j] = ITEM
}

Let's implement this

Insertion sort!

• We want to declare a method that receives a reference array as an input argument.
• After the method finishes doing its thing, the array should be sorted. When does a method finish?
• We might also want to implement the SwapTwoValues method from three classes ago. public static void SwapTwoValues(int[] num_array){ int t = num_array[0]; num_array[0] = num_array[1]; num_array[1] = t; } public static void main(String args[]){ int numbers = new int[2]; numbers[0] = 10; numbers[1] = -10; SwapTwoValues(numbers); }

Insertion sort!

• We want to declare a method that receives a reference array as an input argument.
• After the method finishes doing its thing, the array should be sorted. When does a method finish?
• We might also want to implement the SwapTwoValues method from three classes ago, with a small change public static void SwapTwoValues(int[] num_array, int i, int j){ int t = num_array[i]; num_array[i] = num_array[j]; num_array[j] = t; } public static void main(String args[]){ int numbers = new int[2]; numbers[0] = 10; numbers[1] = -10; SwapTwoValues(numbers, 0, 1); }

How fast is insertion sort?

Why is insertion sort faster on average?

Complexity

Complexity

An estimate number of times a particular operation is repeated by your algorithm:

• Search: How many comparisons are needed to find a number in an array of size N
• Sorting: How many swaps/comparisons are needed to sort an array with N items.

An algorithm is A faster than algorithm B if

As N grows to infinity, A requires less operations to give an answer.

Complexity

An algorithm is A faster than algorithm B if

As N grows to infinity, A requires less operations to give an answer.

• Linear Search: In the worst case, N comparisons are needed to find a target number
• Binary Search: In the worst case, log₂(N)+1 comparisons are needed to find a target number

The worst case: The target number is not in the array

Complexity

An algorithm is A faster than algorithm B if

As N grows to infinity, A requires less operations to give an answer.

• BubbleSort: On the order of N² comparisons are needed
• InsertionSort: On the order of N² comparisons are needed

The worst case for BubbleSort and InsertionSort: The array is sorted in reverse

Big O notation

An estimate of the number of times a particular operation is repeated by your algorithm, in the worst case ( An upper bound )

Not an exact number or expression. We only look at how fast it grows when N becomes very large.

• Linear Search: On the order of N comparisons are needed to find a target number
• Binary Search: On the order of log₂(N)+1 comparisons are needed to find a target number
• BubbleSort: On the order of N² comparisons are needed
• InsertionSort: On the order of N² comparisons are needed

Big O notation

An estimate of the number of times a particular operation is repeated by your algorithm, in the worst case ( An upper bound )

Not an exact number or expression. We only look at how fast it grows when N becomes very large.

• Linear Search: O ( N ) comparisons
• Binary Search: O ( log₂(N) ) comparisons
• BubbleSort: O ( N² ) comparisons
• InsertionSort: O ( N² ) comparisons

Can we do better?

Can we do some trick like in binary search?

We can do better

Divide your problem into easier (smaller) subproblems

Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together

We can do EVEN better

Divide your problem into easier (smaller) subproblems

Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together

Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together

Idea 3: instead of sorting a list of size N/4 , sort two lists of size N/8 and merge them together

...

Idea K: instead of sorting a list of size 2 , sort two lists of size 1 and merge them together

We can go all the way down

Divide your problem into easier (smaller) subproblems

Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together

Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together

Idea 3: instead of sorting a list of size N/4 , sort two lists of size N/8 and merge them together

...

Idea i : instead of sorting a list of size N/(2^(i-1)) , sort two lists of size N/(2^i) and merge them together

...

Idea K: instead of sorting a list of size 2 , sort two lists of size 1 and merge them together

Complexity of the previous algorithm

An algorithm is A faster than algorithm B if

As N grows to infinity, A requires less operations to give an answer.

• BubbleSort: On the order of N² comparisons are needed
• InsertionSort: On the order of N² comparisons are needed
• InsertionSort: On the order of N*log₂(N) comparisons are needed

The worst case for BubbleSort and InsertionSort: The array is sorted in reverse

The worst case for MergeSort: The number of comparisons is independent from the state of the array

How do we merge two sorted lists?

 Merge ( A , B) {
    Let N be the number of items in A
    Let M be the number of items in B
    
    Create an empty array R with size N+M
    Let i = 0, and j = 0
    While i + j < N + M -1 {
       if  i  == N{
           // Reached the end of array A
           R[i+j] = B[j]
           j = j + 1
        }
        else if  j  == M{
           // Reached the end of array B
           R[i+j] = A[j]
           i = i + 1
        }
       else if A[i] ≤ B[j] {
           R[i+j] = A[i]
            i = i + 1
        }
        else if A[i] ≥ B[j] {
           R[i+j] = B[j]
           j = j + 1
        }
    }
    return R;
}

Merging two sorted lists

The merge sort algorithm

 MergeSort ( A) {
    Let N be the number of items in A

    if N < 2{
        // An array with 0 or 1 elements is already sorted
        return A
    }
    
    Copy the left half of A in leftHalf

    Copy the right half of A in rightHalf


    leftHalf = MergeSort ( leftHalf) 
    rightHalf = MergeSort ( righttHalf) 

    result = Merge( leftHalf, rightHalf)

    return result
}

The merge sort algorithm

 MergeSort ( A) {
    Let N be the number of items in A

    if N < 2{
        // An array with 0 or 1 elements is already sorted
        return A
    }
    
    Copy the left half of A in leftHalf

    Copy the right half of A in rightHalf
    
    // What is this ??????
    leftHalf = MergeSort ( leftHalf) 
    rightHalf = MergeSort ( righttHalf) 

    result = Merge( leftHalf, rightHalf)

    return result
}

Recursion

Recursion

Remember, methods can be viewed as boxes that process data

Recursion

We can call other methods inside any method we define

In this case, someMethod stops until anotherMethod returns

Recursion

We can call other methods inside any method we define

In this case, magicMethod stops until System.out.println returns

Recursion

There is no reason why we can't call a method inside its definition

In this case, magicMethod calls System.out.println

Then, magicMethod stops until the second call to magicMethod returns

Recursion

This is called recursion.

In this case, magicMethod stops until System.out.println

Then, magicMethod stops until the second call to magicMethod returns

When will the second call to magicMethod return ?

When does recursion stop?

Writing down the steps executed by the previous code

When will the second call to magicMethod return ? The answer is never

The base case in recursion

We need to add something to our code to make it return at some point!

For example, make it stop calling itself when n == 0

This is called a base case

The base case in recursion

We need to add something to our code to make it return at some point!

For example, make it stop calling itself when n == 0

This is called a base case

The base case in recursion

We need to add something to our code to make it return at some point!

For example, make it stop calling itself when n == 0

This is called a base case

The inner call to magicMethod, happens when n > 0. This is called the recursive case

Recursion examples

The sum of all numbers from 1 to N

We use this function to count the number of comparisons in BubbleSort and InsertionSort

• The base case: When N == 1
• The recursive case: When N > 1

Recursion examples

The sum of all numbers from 1 to N

We use this function to count the number of comparisons in BubbleSort and InsertionSort

• The base case: When N == 1
  • The sum equals to 1
• The recursive case: When N > 1
  • The sum equals to N + the sum of all numbers from 1 to N -1

Recursion examples

The factorial function: N!= 1 * 2 * 3 * 4 * 5 * ... * N!

We can use this function to count the number of different orderings of an array of size N (i.e., permutations)

• The base case: When N == 1
• The recursive case: When N > 1

Recursion examples

The factorial function: N!

We can use this function to count the number of different orderings of an array of size N (i.e., permutations)

• The base case: When N == 1
  • factorial(1) = 1
• The recursive case: When N > 1
  • factorial(N) = N * factorial(N -1)

Recursion examples

The N-th Fibonnaci number: 1, 1, 2 ,3 ,5, 8 , 13, ...

A number sequence ubiquitous in science and mathematics

The N-th Fibonnaci number is the sum of the two previous Fibonnaci numbers

• The base cases:
• When N == 0
• When N == 1
• The recursive case: When N > 2

Recursion examples

The N-th Fibonnaci number: 1, 1, 2 ,3 ,5, 8 , 13, ...

A number sequence ubiquitous in science and mathematics

The N-th Fibonnaci number is the sum of the two previous Fibonnaci numbers

• The base cases:
• When N == 0
  • fibonnaci(0) = 1
• When N == 1
  • fibonnaci(1) = 1
• The recursive case: When N > 2
  • fibonnaci(N) = fibonnaci(N-1) + fibonnaci(N-2)

To try by yourself

More recursive algorithms

Hint: These recursive methods are very similar to the Fibonnaci sequence

1. Implement a recursive method that returns numbers according to the Lucas sequence
2. Implement a recursive version of Assignment 2 Question 3e: T(n) = T(n-1) + T(n-2) + T(n-3)

Recursive algorithms always have an iterative version (i.e. using loops instead of recursion)

3. Write an iterative version of the algorithm for computing the sum of numbers from 1 to N
4. Write an iterative version for the factorial function
5. Write an iterative version for the Fibonnaci numbers, the Lucas sequence, and the T(n) sequence

NEXT CLASS MIDTERM REVIEW

Resources

• A short video on the merge sort algorithm for Harvard's CS50:
  https://www.youtube.com/watch?v=EeQ8pwjQxTM
• A short video on recursion from Computerphile:
  https://www.youtube.com/watch?v=Mv9NEXX1VHc
• Suggested reading on recursion:
  How to think like a Computer Scientist, Chapters 4.8 and 6.8