# ICS4U Grade 12 – Computer Science – Advanced Algorithms Test

Grade 12 – Computer Science

Advanced Algorithms – A Guide to Programming in Java Ch 13

Selection Sort

• Sorts by finding the lowest number and swapping it with first
• Next, it will look at the list from the 2nd number onwards and look for the lowest number from there
• It will find the smallest number from 2 till the end, and swap it with the 2nd number
• Nested for-loops are capable of doing this method, without the use of recursions

Sorting Objects

• Using the equals() or compareTo() implemented in objects, you may compare objects
• Objects may also implement the Comparable Interface to use to compare
• Interfaces cannot be used to instantiate a class but interfaces can be used as a data type.
• Interface data type can refer to any class it implements
• This polymorphic behavior can allow a generic sort of any list of objects which have the Comparable Interface

Insertion Sort

• Starts sorting with the first 2 items in a list, shifts them to the correct place
• The third item will be compared and shifted up to where it fits
• Each element is compared with all the elements before it to see where it should fit

Recursion

• Recursive Call: are methods that can call itself.
• A recursive method calls itself but with different parameters each time
• Recursion can be used to solve problems requiring smaller versions of the same problem, then combining the results
• For example, if we wanted to use recursion to find the value of a number raised to a power, we could have a recursion call that reduces the number into x * xn-1 each time until it reaches 1 and adding all the results.
• 23 is 2* 22 + 2* 21 + 1 which is 8
• Each 2* 23 is a new call in the recursive method

Mergesort

• Selection short is inefficient for large arrays
• Merge sort takes a “divide-and-conquer” approach in sorting numbers.
• It cuts the array in half, and cuts the halfs in half and so on to to sort smaller sections
• Mergesort will then recombine all of the elements together into one large sorted array
• Mergesort has a recursive method that keeps calling itself to sort the halves
• A temporary array is needed to store the items moved from two sorted arrays into the items array

Binary Search

• Binary search uses a sorted list to quickly look for the location of a value
• It too also takes the divide and conquer approach
• It cuts the array in half and determines, by comparing the target value with the middle, beginning, and end value to see which half the value is located in
• It then takes the half and does the same thing to cut that in half
• Eventually, it will find the number on one of the halves
• This saves time because it only looks at half of the values at a time, not needing to go through the entire array

Depth-First Searching

• Solves problems, not sort lists
• A problem is solvable with DFS If it can be modeled by a tree diagram
• It looks deeper and deeper into the problem, in smaller chunks, until it finds the solution (uses recursive methods)
• Each time a recursive method is called, it does the same actions differently with slight modifications to get deeper into the problem.
• Can be used for solving mazes, creating schedules, or possible plays in a game