SPLIT THIS UP:
part 1: searching - sequential serach, binary search with a while loop, low, mid, might, and bin search with recursion
part 2: sorting - change insert to use one arraylist instead of two. START lesson by putting them in pairs, give them 5 or 6 playing cards, have them put in alpha order, then ask them to write down their steps. Show selection sort with ARRAYS (swapping as thats how it will be on ap test) and two different arraylists.
a bit more time for part 2, add some easy points first, like a simple find the min, then a simple insert one number in correct spot? this is a great idea to help them set the table. maybe make them bogo??
------------------------
You can see a video version of this lesson here: https://www.youtube.com/watch?v=8UdhE5eNv18 and https://www.youtube.com/watch?v=QX_XAOPwKwc
For some cool visuals, check out https://www.youtube.com/watch?v=kPRA0W1kECg (sound on) or www.sorting-algorithms.com
In this lab, you will be creating one large program called SearchSort.java. These labs are due Thursday, February 19th at 11:59 pm. ALL METHODS WILL BE PUBLIC AND STATIC. The point of this lab is to implement some of the searching and sorting algorithms we learned about in class (the algorithms in this lab are the ones you are expected to know for the AP test). I recognize that you may be able to find some of this code online, but please do not even look at it – write your own so you can understand how the code actually works. Obviously, do not use any built-in java functions for these methods either. I will be looking over your code.
TEST ALL OF YOUR METHODS AS YOU WRITE THEM, probably in a main method. This is one of the tougher labs of the year and must be tested thoroughly.
Please make sure that you are careful with arrays vs. ArrayList throughout. I want you to get practice with both. Also, when sorting numbers, remember to sort from smallest to largest.
***0. DELETE ALL OLD LABS FROM YOUR TURN IN FOLDER! There should be nothing in there besides this lab.***
Please write the following STATIC methods in your SearchSort class:
1. seqSearch( ) – this method inputs an ArrayList of Strings and a String, and returns a boolean - true if that String matches one of the Strings in the list, false if it does not, using sequential search. For example, if you have the ArrayList words storing ["jennifer", "happy", "cool", "funny"], then SearchSort.seqSearch(words, "cool") would return true but seqSearch(words, "lame") would return false. [you should test this and all of your other methods in main]
2. selSort( ) – this method should input an ArrayList of type <Double> [recall that you can add a Double to an ArrayList<Double> by just typing list.add(2.4) and that Double objects can be compared with < and > just like doubles] and return an ArrayList of type <Double> that has been sorted using Selection sort. This method should utilize the selection sort algorithm as seen in class, repeatedly selecting the lowest element, then taking it out. One way to do this is to select a second list to hold things in. Loop through the entire first list, searching for the smallest element. Once you have it, remove it from the first list and add it on to the second. [hint: remember to reset your minimum every time through the loop]
Be careful with how you use .remove() and .add(), and make sure you are using a nested loop.
3. insertSort( ) – this method should input an ArrayList of type <Integer> and return an ArrayList of type <Integer> that has been sorted using insertion sort. Like with selection sort, you probably want to write a nested for loop, and you should take advantage of the overloaded .add method for ArrayList. You will need a second ArrayList and you should add items in the correct location in that list as you go along, then return the new list.
Here is an outline that might be helpful:
-set up the second list, add an element too it
-your outer loop should go through the original list and look at each number, list.get(i)
-then, your inner loop will go through the sorted list. Check to see whether list.get(i) goes before each element in the sorted list. If it does, put it in that spot. Otherwise, continue going through the loop without doing anything (the addOrder method from the arraylist labs might be useful).
-make sure you have a special case for when list.get(i) goes at the end of your sorted list.
[hint: make sure you are always inserting it somewhere in the second list! sometimes it may go at the end...]
4. takePart(int[] nums, int index1, int index2) – this method inputs an array of ints and 2 ints representing indices of the array, and returns an array of ints representing that chunk of the array between those two indices, NOT including the last term (just like in substring). For instance, if you call takePart( {7,8,9,11,-15},2,4 ), it returns the chunk of the array between 2 and 4 not including 4, so just, {9,11}. You may assume the first bound will be <= the second bound.
HINT: Test this method thoroughly before proceeding, including the case where the second bound is the length of the array. If you have errors in the next method, they may actually be related to this not working properly.
[YOUR SOLUTION SHOULD NOT USE ARRAYLISTS]
5. totalOrder(int[] nums1, int[] nums2) – this method inputs two arrays of ints (as a precondition, assume both are already sorted from smallest to largest) and returns an array consisting of the two put together from least to greatest. For example, totalOrder( {2,5}, {0,2,12,13} ) should return {0,2,2,5,12,13} and totalOrder( { }, {0,2,12,13} ) should return {0,2,12,13}. You should create a new array to be filled up and returned, and you should probably also create separate variables to keep track of your current location in each of the two input arrays as well as the array you will return. Again, ASSUME BOTH INPUT ARRAYS HAVE ALREADY BEEN SORTED. Inside a loop, you should consider the cases where one array may be empty and the case where you can compare the first elements of each array.
->this is actually the hardest part of merge sorting. Test this first before you move on. Test it in several cases - including the case where one of the two lists is empty and the cases where the lists have different lengths.
->this method should NOT call or implement any of your other sorting methods, it will automatically sort by only comparing the first element of each sorted array.
-> Start by setting up an array of the requisite length and slowly fill that in.
[YOUR SOLUTION SHOULD NOT USE ARRAYLISTS]
6. merSort( ) – this method inputs an array of ints and returns the sorted array using merge sort. Use recursion and the takePart and totalOrder methods that you just wrote – those are the hard parts, this method should really just be a base case (if you have 0 or 1 elements in your list) and a recursive return statement which also calls takePart and totalOrder. Basically, you split the input array in half, sort each half using merSort (recursive call) and then TotalOrder those two halves. When you split it in half, just go from 0 to length/2 and (length/2) to length , java will handle the rounding for you.
7. binSearch( ) – this method inputs an array of ints (assume it is already sorted), and an int, and returns a boolean representing whether the int has been found in the array using a binary search. So binSearch({-11,0,5,6,7,12,125},1) returns false, but binSearch({-11,0,5,6,7,12,125},0) returns true. Since binary search only works on sorted arrays, assume the input will already be sorted.
Remember to check a point in the middle, see if it is greater, less or equal to your target, and then only look at half of what is left – using takePart should be helpful. I am requiring you to use RECURSION to solve this program.
NOTE: I expect that you will complete all the labs, but if for some reason you do not, please write the method to still return something so that it works with my program. For instance, suppose you just didn’t get merSort, rather than leaving it blank, just do this (which will make your program compile but is obviously wrong):
public static int[] merSort(int[] nums)
{
return nums;
}
When you are done, submit SearchSort.java
Want two points of extra credit?? Program a public class Bogosort. Inside this class, write a bogosort() method to randomly sort an array of ints, and a main method to call and test bogosort(). Make sure it prints out how many attempts it took before it got it correct. Do not test this on a list of more than 6 or 7 items as it will take a VERY long time to run.