Guided: Searching and Sorting in a Java Book Catalog App

You have been given a mostly complete Book Catalog Application in Java. In this lab, you will be responsible for finishing up the rest of the application by implementing algorithms such as quick sort, merge sort, and binary search. These algorithms are a must-know for any developer as they provide efficient ways for ordering or retrieving data in progressively larger data sets.

There are two main classes to take note of. First is in Book.java, which contains an implementation for the Book objects that are stored in the catalog. It has already been completed for you and is fairly straightforward. Take note of its compareTo method which compares books by title for alphabetical ordering.

Second is the Catalog.java file which contains the Catalog class. This implementation is mostly complete with the exception of a few functions you will need to complete to finish the implementation.

The app can be launched at any time by clicking the Run button at the bottom right of the Terminal.

The first of the two sorting algorithms you will need to implement is a merge sort. The idea behind a merge sort involves continuously splitting a list in half until it can no longer be divided (meaning either the list is empty or the split sublist only contains one element). Then, you sort each sublist before merging the sublists together until eventually you have reformed the original list in sorted form.

To do this, you will also need a secondary merge() function for your merge sort to combine the sublists. The merge sort function itself then becomes a recursive call to each of its halves before calling the merge() function.

Details

1. Create three index variables: i for left, j for right, and k for output. Initialize them to 0.
2. Start a while loop that continues as long as both i is less than left.size() and j is less than right.size().
3. Inside the loop, compare the elements at indices i and j in left and right, respectively.
4. If the element at left[i] is less than or equal to the element at right[j] ( See Hint #1):
   • Assign the element at left[i] to output[k] (See Hint #2).
   • Increment both i and k.
5. Otherwise, if the element at left[i] is greater than the element at right[j]:
   • Assign the element at right[j] to output[k].
   • Increment both j and k.
6. After the while loop, add any remaining elements from left to output using another while loop.
7. After the while loop, add any remaining elements from right to output using another while loop.

Hint #1

Use the Book classes compareTo to compare books. A value of 0 or less should be placed in the output array first.

Hint #2

Hint: The set(index, value) method of the List class can be used for placing elements in the output list. The get(index) method can be used to retrieve values from a specified index.

Now that `merge()` has been completed, you will need to use it to implement the `mergeSort()` function. The implementation here is fairly straight forward using recursion.

Details

1. Check if the size of arr is less than 2. If so, return since the list is already sorted or empty.
2. Calculate the middle index of arr. You can do this by dividing the size of the list by 2 and rounding down if necessary. Let's call this index mi.
3. Create two new lists, list1 and list2.
4. Put all elements from index 0 to mi (exclusive) in list1.
5. Put all elements from mito the end of arr in list2.
6. Call mergeSort recursively on list1.
7. Call mergeSort recursively on list2.
8. Call the merge function with arr, list1, and list2 to merge the two sorted lists back into arr.

The second sorting algorithm you will be implementing here will be a quick sort. Like merge sort, quick sort is also a divide and conquer algorithm that involves dividing the input data into smaller sublists, sorting them individually and then combining them. The quick sort process involves picking a "pivot" element, usually the first or last element of the list, and splitting the list such that all smaller elements come before the pivot, all greater elements come after, and the pivot itself is placed in its correct final position.

To do this, you will once again need an auxiliary function called partition(), which has already been defined for you. Another function called swap() for swapping elements has already been provided for you for use in partition().

Details

1. Select the pivot element from the end of arr (book at index high).
2. Create a variable, such as ci, and set it to low - 1.
3. Start a loop from low to high - 1.
4. Inside the loop, if arr[x] is less than the pivot, increment ci and swap arr[ci] with arr[x].
5. After the loop, swap arr[ci + 1] with arr[high].
6. Return ci + 1 as the updated index of the pivot

Now that the `partition()` method is complete, you can now use it to implement the `quickSort()` method. Like `mergeSort()`, this can be done fairly easily using recursive calls.

Details

1. Check if low is less than high. If not, return since the current partition has zero or one element.
2. Call the partition function and store its return value in a variable, such as pivotIndex.
3. Recursively call quickSort with arr, low, and pivotIndex - 1 as parameters.
4. Recursively call quickSort with arr, pivotIndex + 1, and high as parameters.

The final step will be for you to implement a search algorithm known as binary search. For larger data sets, binary search offers much better performance compared to a linear search when retrieving data. However, it can only be performed on sorted data sets (which makes the previous two algorithms come in handy!).

Like the previous algorithms, binary search is also a divide and conquer algorithm. It involves selecting an element from the middle of the array and comparing it to the element to be retrieved. If the target element is less, then binary search is performed again from start to the mid element. If the target element was more, then binary search is performed from the midpoint to the end. This continues until a match is found or is not found in the list.

Details

1. Set a start as the first index of the list.
2. Set an end as the last index of the list.
3. While start is less than or equal to end, do steps 6-9.
4. Calculate mid as the average of start and end.
5. If the value at index mid is equal to the target value, return mid.
6. If the value at index mid is greater than the target value, set end to mid - 1.
7. If the value at index mid is less than the target value, set start to mid + 1.
8. Return -1 outside of the while loop

Great job on completing the lab. Now you should be familiar with search and sort algorithms such as merge sort, quick sort, and binary search. These algorithms, along with other search and sort algorithms, are very important for maintaining performance in terms of resources and time when working with progressively larger data sets.

The use cases for search and sort algorithms are also fairly specific to the scenario, as some algorithms perform significantly better than others under certain circumstances while others could perform significantly worse than they typically would. It's your job as the developer to assess the situation when determining the best approach!