Grade 12 – Computer Science
Advanced Algorithms – A Guide to Programming in Java Ch 13
- 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
- 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
- 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
- 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
- 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 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
- 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