Week of April 3, 2016
Topics for this week: Sorting and Searching
||Continue your study of chapter 12 in the course packet.
||Review the slides Sorting and Searching
lab #24, due by 11:59pm on Tuesday.
||Review the sample program
example 10, which illustrates some sorting and searching techniques.
||Complete project #10
and submit it to Canvas before 11:59pm on Sunday. Late programs will lose 20% of the possible points
for each day that they are late. If you turn this program in prior to 11:59pm on Saturday, you will
receive a 5 point bonus, if it meets all of the specifications and gives the correct answers.
It is expected that you will meet the objectives outlined here by the end of the week.
You might want to test yourself to see how well you fare. You can be guaranteed that you
will be tested on these concepts on your next exam. By the end of this unit, you should
be able to:
- Explain what it means to search for something in an array.
- Describe the difference between a linear search and a binary search.
- Describe the conditions that must exist for a binary search to work correctly.
- Correctly write a simple linear search.
- Explain what it means to sort the elements of an array.
- Correctly write a simple bubble sort.
- Describe the performance issues with a bubble sort, and show how to correct them.
All reading should be done before you come to class. Your ability to understand
the material discussed in class will be greatly enhanced when you come to class
- Slides on "Searching and Sorting" - demonstrate several algormithms for sorting values in an array
and finding values in an array.
Be sure that you understand the following important ideas presented in this unit.
- Arrays are convenient when you want a collection of data of the same type.
- Two common operations done on an array are searching for an element in the array and sorting the array.
- There are two common searching algorithms: linear search and binary search.
- Typically, a binary search is much faster than a linear search, but requires the array to be sorted first.
- The simplest sorting algorithm to write is a bubble sort.
- However, bubble sorts are not very efficient.
This week you should complete lab 24. This lab will help you to understand sorting and searching.
This week you should complete project #10. This project will
test your ability to use arrays and write the code for a sorting alogorithm.