Warning: Outdated Content
This lab is from a previous version of CS 125. Click here to access the latest version.
Sorting and Searching
Sorting and searching are fundamental computer science tasks. They get to the heart of two things that computers are very good at: organizing and retrieving data. They are also building blocks on which other algorithms are built.
Today’s lab introduces you to basic searching and sorting algorithms. The written portion starts to develop your intuition about how sorting and searching algorithms work, and how their performance might vary. The programming component provides an opportunity to implement a few sorting algorithms, and get a visceral sense of algorithm runtime.
1. Written Exercises (45 Minutes)
As usual, we begin with a written lab component. Please complete these exercises carefully. Your course staff will review and discuss your answers along with the rest of your section.
Complete this part of the lab in pairs using Google Docs. Create a copy of our document template, and then edit it to record you and your partner’s answers. Note that you must open this document using your @illinois.edu Google Apps account. We will not grant access to non-Illinois users.
Have a course staff member check your answers as you go. When you are done, move on to the programming component.
2. Sorting Implementations (45 Minutes)
Computers have gotten extremely fast, and as a result it can be easy to not care about algorithm runtime when working on small problems. But once data gets a bit bigger—and the world is full of big data—the difference between algorithms starts to matter. A lot.
The second part of the lab provides you with an opportunity to get up close and personal with the implementation and performance of several classic sorting algorithms.
2.1. Forking and Cloning the Lab10 IntelliJ Project
We’ve set up an Lab 10 GitHub repository containing an IntelliJ Project that’s correctly configured for Lab 10. Getting access to it is similar to how you imported MP0. But you have to fork our repository first. If it’s not obvious how to do that, try following these instructions.
Note that you should continue to use IntelliJ for this lab, not Android Studio. We’ll get to that next time.
2.2. Your Goal
We provide skeletons of three classic sorting algorithms for you to implement: bubble sort, selection sort, and merge sort 1. Implement one, two, or all three of these algorithms.
Then use the provided plotting tool to explore their performance. Remember from the written component that algorithm performance can be affected by both the size and the structure of the inputs. We’ve given you inputs both of different size and structure, so this should be an ideal starting point for an exploration of their impact on the algorithms you have completed.
Work with other groups nearby to complete a characterization of all three sorting algorithms. You should be able to answers questions about how their performance varies with input size, but also about how well they perform on different sized inputs. You are free to split up the problem so that each group implements one sorting algorithm and then you all compare results.
Keep in mind that you may need to adjust the size of the input arrays for some of the slower algorithms, since they are slow! Hopefully you’ll be impressed by the difference in speed on large inputs between the various sorting algorithms. Feel free to test the default built-in Java sort as well—see how much it out-performs your implementations.
3. Help with Android Setup
Use any remaining time in your lab section 2 to get help setting up your Android development environment, or returning to any of the parts of the previous lab that you may have missed.