IN THIS CONCEPT

Summary: Welcome to the Information Age. There has never before been a time in human history that so much information was produced and recorded. So, what’s a person to do with all that information? Search it? Sort it? Find patterns that can help people? In this concept, you will learn how to implement algorithms that allow you to search and sort data, regardless of how many pieces of data there are.

Key Ideas

   The Insertion Sort, Selection Sort, and Merge Sort are sorting routines.

   The Binary Search is an efficient way to search for a target in a sorted list.

Background on Sorting Data

The idea of sorting is quite easy for humans to understand. In contrast, teaching a computer to sort items all by itself can be a challenge. Through the years, hundreds of sorting algorithms have been developed, and they have all been critiqued for their efficiency and memory usage. The AP Computer Science A Exam expects you to be able to read and analyze code that uses three main sorts: the Insertion Sort, the Selection Sort, and the Merge Sort.

The most important thing to remember is different sorting algorithms are good for different things. Some are easy to code, some use the CPU efficiently, some use memory efficiently, some are good at adding an element to a pre-sorted list, some don’t care whether the list is pre-sorted or not, and so on. Of our three algorithms, Merge Sort is the fastest, but it uses the most memory.

The Swap Algorithm

Recall the swapping algorithm that you learned in Concept 6: Algorithms (Basic Version). It is used in some of the sorting algorithms in this concept.

Sorting Algorithms on the AP Computer Science A Exam

You will not have to write the full code for any of the sorting routines described in this concept. You should, however, understand how each works.

Insertion Sort

The Insertion Sort algorithm is similar to the natural way that people sort a list of numbers if they are given the numbers one at a time. For example, if you gave a person a series of number cards one at a time, the person could easily sort the numbers “on the fly” by inserting the card where it belonged as soon as the card was received. Insertion Sort is considered to be a relatively simple sort and works best on very small data sets.

To write the code that can automate this process on a list of numbers requires an algorithm that does a lot of comparing. Let’s do an example of how Insertion Sort sorts a list of numbers from smallest to largest.

This algorithm uses a temporary variable that I will call temp. The first step is to put the number that is in the second position into the temporary variable (temp). Compare temp with the number in the first position. If temp is less than the number in the first position, then move the number that is in the first position to the second position and put temp in the first position. Now, the first pass is completed and the first two numbers are sorted from smallest to largest.

Next, put the number in the third position in temp. Compare temp to the number in the second position in the list. If temp is less than the second number, move the second number into the third position and compare temp to the number in the first position. If temp is less than the number in the first position, move the number in the first position to the second position, and move temp to the first position. Now, the second pass is completed and the first three numbers in the list are sorted. Continue this process until the last number is compared against all of the other numbers and inserted where it belongs.

I’ll Pass

A pass in programming is one iteration of a process. Each of these sorts makes a series of passes before it completes the sort. An efficient algorithm uses the smallest number of passes that it can.

Implementation

The following class contains a method that sorts an array of integers from smallest to greatest using the Insertion Sort algorithm.

Selection Sort

The Selection Sort algorithm forms a sorted list by repeatedly finding and selecting the smallest item in a list and putting it in its proper place.

To sort a list of numbers from smallest to largest using Selection Sort, search the entire list for the smallest item, select it, and swap it with the first item in the list (the two numbers change positions). This completes the first pass. Next, search for the smallest item in the remaining list (not including the first item), select it, and swap it with the item in the second position. This completes the second pass. Then, search for the smallest item in the remaining list (not including the first or second items), select it, and swap it with the item in the third position. Repeat this process until the last item in the list becomes (automatically) the largest item in the list.

Implementation

The following class contains a method that sorts an array of integers from smallest to greatest using the Selection Sort algorithm.

Merge Sort

The Merge Sort is called a “divide and conquer” algorithm and uses recursion. The Merge Sort algorithm repeatedly divides the numbers into two groups until it can’t do it anymore (that’s where the recursion comes in). Next, the algorithm merges the smaller groups together and sorts them as it joins them. This process repeats until all the groups form one sorted group.

Merge Sort is a relatively fast sort and is much more efficient on large data sets than Insertion Sort or Selection Sort. Although it seems like Merge Sort is the best of these three sorts, its downside is that it requires more memory to execute.

Example

Sort a group of numbers using the Merge Sort algorithm.

Goal: Sort these numbers from smallest to largest: 8, 5, 2, 6, 9, 1, 3, 4

Step 1: Split the group of numbers into two groups: 8, 5, 2, 6 and 9, 1, 3, 4

Step 2: Split each of these groups into two groups: 8, 5 and 2, 6 and 9, 1 and 3, 4

Step 3: Repeat until you can’t anymore: 8 and 5 and 2 and 6 and 9 and 1 and 3 and 4

Step 4: Combine two groups, sorting as you group them: 5, 8 and 2, 6 and 1, 9 and 3, 4

Step 5: Combine two groups, sorting as you group them: 2, 5, 6, 8 and 1, 3, 4, 9

Step 6: Repeat the previous step until you have one sorted group: 1, 2, 3, 4, 5, 6, 8, 9

Implementation

The following class contains three interdependent methods that sort a list of integers from smallest to greatest using the Merge Sort algorithm. The method setUpMerge is a recursive method.

Binary Search

So far, the only algorithm we know to search for a target in a list is the Sequential Search. It starts at one end of a list and works toward the other end, comparing each element to the target. Although it works, it’s not very efficient. The Binary Search algorithm is the most efficient way to search for a target item provided the list is already sorted . It repeatedly eliminates half of the search list with each pass by guessing in the middle of the existing list and determining if the guess was too high or too low. The secret of the Binary Search algorithm is that the data must be sorted prior to doing the search.

Sorted Data

The Binary Search only works on sorted data. Performing a Binary Search on unsorted data produces invalid results.

Example

The “Guess My Number” game consists of someone saying something like, “I’m thinking of a number between 1 and 100. Try to guess it. I will tell you if your guess is too high or too low.”

Solution 1: Terrible way to win the “Guess My Number” game

Solution 2: Fastest way to win the “Guess My Number” game (the Binary Search algorithm)

Visual description of the “Guess My Number” game using the Binary Search algorithm:

Implementation

The following class contains a method that searches an array of integers for a target value using the Binary Search algorithm. Notice that the main method makes a method call to sort the array prior to calling the binarySearch method.

 Rapid Review

Insertion Sort

• Insertion Sort uses an algorithm that repeatedly compares the next number in the list to the previously sorted numbers in the list and inserts it where it belongs.

Selection Sort

• Selection Sort uses an algorithm that repeatedly selects the smallest number in a list and swaps it with the current element in the list.

Merge Sort

• Merge Sort uses an algorithm that repeatedly divides the data into two groups until it can divide no longer. The algorithm joins the smaller groups together and sorts them as it joins them. This process repeats until all the groups are joined to form one sorted group.
• Merge Sort uses a divide and conquer algorithm and recursion.
• Merge Sort is more efficient than Selection Sort and Insertion Sort.
• Merge Sort requires more internal memory (RAM) than Selection Sort and Insertion Sort.

Binary Search

• A Binary Search algorithm is the most efficient way to search for a target value in a sorted list.
• A Binary Search algorithm requires that the list be sorted prior to searching.
• A Binary Search algorithm eliminates half of the search list with each pass.

 Review Questions

Basic Level

Questions 1–4 refer to the following information.

Array arr has been defined and initialized as follows

1 .    Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Insertion Sort algorithm?

(A)   1   5   3   8   6   4   2   7

(B)   1   3   8   5   6   4   2   7

(C)   5   3   7   1   6   4   2   8

(D)   3   5   8   1   6   4   2   7

(E)   1   2   3   4   5   6   7   8

2 .    Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Insertion Sort algorithm?

(A)   1   3   5   6   8   4   2   7

(B)   1   2   3   4   6   5   8   7

(C)   1   2   3   4   5   6   7   8

(D)   3   5   8   1   6   4   2   7

(E)   1   2   3   4   5   6   8   7

3 .    Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Selection Sort algorithm?

(A)   1   2   3   5   6   4   8   7

(B)   1   3   8   5   6   4   2   7

(C)   1   3   5   8   6   4   2   7

(D)   1   5   3   8   6   4   2   7

(E)   5   3   1   6   4   2   7   8

4 .    Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Selection Sort algorithm?

(A)   3   1   4   2   5   6   7   8

(B)   3   1   4   2   5   8   6   7

(C)   1   2   3   4   5   6   7   8

(D)   1   2   3   4   5   8   6   7

(E)   1   2   3   4   6   5   8   7

5 .    Array arr2 has been defined and initialized as follows.

If the array is being searched for the number 4, which sequence of numbers is still in the area to be searched after two passes through the while loop of the Binary Search algorithm?

(A)   1   2   3   4   5

(B)   2   3   4

(C)   4   5   6

(D)   4   5

(E)   The number has been found in the second pass. Nothing is left to be searched.

Advanced Level

6 .    Consider the following method.

The algorithm implemented by the method can best be described as:

(A)   Insertion Sort

(B)   Selection Sort

(C)   Binary Search

(D)   Merge Sort

(E)   Sequential Sort

7 .    Consider the following code segment that implements the Insertion Sort algorithm.

Which of the following can be used to replace /* condition */ so that insertionSort will work as intended?

(A)   arr[i] > key

(B)   arr[j] > key

(C)   arr[i + 1] > key

(D)   arr[j + 1] > key

(E)   arr[i - 1] > key

 Answers and Explanations

Bullets mark each step in the process of arriving at the correct solution.

1 .    The answer is D.

• Our array starts as:
• The 5 is bigger than everything to its left (which is nothing), so let it be. Our algorithm starts with the 3.
• Take out the 3 and store it in a variable: tempKey = 3. Now we have a gap.
• Is 3 < 5? Yes, so move the 5 to the right.
• There’s nothing more to check, so pop the 3 into the open space the 5 left behind.
• That’s the order after the first pass through the loop (question 1).

2 .    The answer is A.

• We start where we left off at the end of question 1.
• Now for the second pass. The 3 and 5 are in order; tempKey = 8, leaving a gap.
• Since 5 < 8, we put the 8 back into its original spot.
• Now for the third pass: 3, 5, 8 are sorted; tempKey = 1, leaving a gap.
• 1 < 8, move 8 into the space 1 left behind. 1 < 5, move 5 over. 1 < 3, move 3 over, and put 1 in the first spot.
• Now for the fourth pass: 1, 3, 5, 8 are sorted; tempKey = 6, leaving a gap.
• 6 < 8, move the 8 into the space 6 left behind. 5 < 6, so we’ve found the spot for 6 and we pop it in.
• Giving us the answer to question 2.
• Note: One thing to look for in the answers when trying to recognize Insertion Sort—the end of the array doesn’t change until it is ready to be sorted. So the 4 2 7 in our example are in the same order that they were in at the beginning.

3 .    The answer is B.

• Our array starts as:
• We scan the array to find the smallest element: 1.
• Now swap the 1 and the 5.
• That’s the order after the first pass through the loop (question 3).

4 .    The answer is E.

• We start where we left off at the end of question 3.
• Now for the second pass. Leave the 1 alone and scan for the smallest remaining item: 2.
• The 3 is in the spot the 2 needs to go into, so swap the 3 and the 2.
• The third pass swaps the 8 and the 3.
• The fourth pass swaps the 5 and the 4.
• This gives us the answer to question 4.

5 .    The answer is D.

• The Binary Search algorithm looks at the element in the middle of the array, sees if it is the right answer, and then decides if the target item is higher or lower than that element. At that point it knows which half of the array the target item is in. Then it looks at the middle element of that half, and so on.
• Here’s our array:
• First pass: The middle element is 6. We are looking for 4. 4 < 6, so eliminate the right half of the array (and the 6). Now we are considering:
• Second pass: The middle element is 3. 4 > 3, so we eliminate the left half of the section we are considering (and the 3). Now we are considering:
• You can see that we will find the 4 on our next round, but the answer to the question is 4 5.
• Good to know: In this example, there alwayswas a middle element when we needed one. If there is an even number of elements, the middle will be halfway in between two elements. The algorithm will just decide whether to round up or down in those cases (usually down, as integer division makes that easy).

6 .    The answer is C.

• Binary Search works like this:
• We look at the midpoint of a list, compare it to the element to be found (let’s call it the key) and decide if our key is >, <, or = that midpoint element.
• If our key = midpoint element, we have found our key in the list.
• If our key > midpoint element, we want to reset the list so that we will search just the top half of the current list.
• If our key < midpoint element, we want to reset the list so that we will search just the bottom half of the current list.
• Look at the given code. We can see those comparisons, and we can see the high and low ends of the list being changed to match the answers to those comparisons. This code implements Binary Search.

7 .    The answer is B.

• There are many small alterations possible when writing any algorithm. Do you go from 1 to length or from 0 to length -1, for example. This algorithm makes those kinds of alterations to the version given in the text. But in all cases, the general approach is:
• The outer loop goes through the array. Everything to the left of the outer loop index (i in this case) is sorted.
• Take the next element and put it into a temporary variable (key in this case).
• Look at the element to the left of the element you are working on. If it is larger than the element to be sorted, move it over. Keep doing that until you find an element that is smaller than the element to be sorted (this is the condition we need).
• Now you’ve found where our element needs to go. Exit inner loop and pop the element into place.
• So the condition we are looking for reflectskeep doing that until we find an element that is smaller than the element to be sorted , or, phrasing it like a while loop (“as long as” instead of “until”), keep going as long as the element we are looking at is larger than our key . In code, we want to keep going as long as arr[j] > key, so that’s our condition.