Chapter XVIII
Algorithms and Informal Analysis
Chapter XVIII Topics
18.1 Introduction
18.2 Pre-OOP Algorithms
18.3 The List Class to Study Algorithm
18.4Sorting Algorithms
18.4.1The Bubble Sort
18.4.2The Smart Bubble Sort
18.4.3The Selection Sort
18.4.4The Insertion Sort
18.4.5The Merge Sort
18.5Searching Algorithms
18.5.1The Linear Search
18.5.2 The Binary Search
18.6Testing Algorithm Efficiency with TimeTest
18.7Informal Algorithmic Analysis
18.8 Summary
18.1 Introduction
We need to take a Java break with this chapter. There will be no significant new Java language features introduced. Do keep remembering that you are learning introductory computer science concepts and the language Java is used to teach these concepts. At most high schools, BASIC, Pascal, C and C++ were used in computer science before switching to Java. In college you will see a bigger variety in introductory computer science classes. Java is certainly popular, but so are Scheme, Visual BASIC, C++, Python and other languages, and the choice of the college-level, introductory computer science, programming language changes quite frequently.
This chapter, however, focuses on an area that does not have many changes: the algorithms used in computer programming. The algorithms that are presented in this chapter are essentially unchanged from earlier chapters in BASIC, Pascal and C++ text books. Sure the language syntax is different, but the essence of the algorithm is unchanged. Do you remember what an algorithm is?
Algorithm DefinitionAn algorithm is a step-by-step sequence to solve a problem.
Niklaus Wirth’s Programming Language Definition
Niklaus Wirth, the creator of the programming language Pascal, made an equation about data structures and algorithms.
Data Structures + Algorithms = Programs
You have done quite a variety of program assignments at this stage and each program required the creation of an algorithm. There were times when you repeated the same types of algorithms for different assignments. The aim of this chapter is to look at a group of practical algorithms that are commonly used in computer science. In particular we want to look at computer program algorithms that are used to process array information. However,an algorithm is a step-by-step sequence to solve a problem. In that sense you then have already seen and used many , many algorithms.
This chapter also emphasizes the recurring theme of computer science, not to reinvent the wheel. If practical algorithms have been created for certain situations, use them, store them, and reuse them as some later date. Time is too precious to start from scratch with every program when useful tools have already been created. By the end of this chapter I hope that your programming toolbox will be considerably expanded.
18.2 Pre-OOP Algorithms
Long before there were classes and methods we had program code, subroutines and data structures. The subroutines and data structure were thrown in somewhere with the program code. Subroutines received different names over time and became procedures, functions and methods.
Many subroutines contained common algorithms. Regardless of the program design that was used, programmers always recognized that any practical code can be re-used. The OOP organization of classes and methods did not yet exist, but subroutines did create their own containers and could be called from anywhere by using program code sequence numbers or subroutine names. Parameters followed soon after and made subroutines more practical.
Imagine a payroll program. One part of the payroll program is the printing of a check. A Check subroutine uses parameters for name, address, amount and any other required information and now one procedure has the ability to print checks for every employee. Printing a check may not seem as much of an algorithm,everything is done in sequence and such a subroutine is highly practical.
In this chapter the main focus will be on sorting and searching algorithms with array data structures. Much of computer science involves data processing. The processing of data means to store data and retrieve data. Storing and retrieval requires finding the data which means efficient searching algorithms are needed. Data that is sorted can be searched more efficiently and for that reasons sorting and searching are very common companions in computer science.
The Pre-OOP programming days made heavy use of algorithms, which normally involved passing a data structure, like an array, to a subroutine parameter. Program PreOOP01.java, in figure 18.1, starts very simple with the declaration of a list array and the display of the list elements. This is all done inside the main method without the use of any subroutines.
Figure 18.1
// PreOOP01.java// This program creates an array and displays it.
// It is all in the main method, but the program is small.
public class PreOOP01
{
public static void main(String[] args)
{
int[] list = {11,99,22,88,33,77,44,66,55};
for (int k = 0; k < list.length; k++)
System.out.print(list[k] + " ");
System.out.println();
}
}
It can certainly be argued that the PreOOP01programis too small to be concerned without any type of organization or program design. There is a display loop for the list array, but that loop structure is used only once. In other words, let us not get overly excited over the poor design of this program.
Program PreOOP02.java, in figure 18.2, is more involved. The same List array is declared, and once again the array is displayed. The program continues and sorts the array elements in ascending order. After the sorting process, the list elements are displayed again to show that they are sorted. At this stage the algorithmic logic of the sort routine is not an issue. You see that it works and there will be considerable detail later in the chapter explaining how this actually works.
The display loop is short, but the exact same loop structure is used twice. That can certainly be improved with a subroutine. The program is still fairly short, but it is already starting to look messy. Using subroutines not only saves code writing for multiple use, the subroutine name also provides clarity with self-documenting names, like sort and display. The program would be easier to comprehend with some strategic comments, but right now the focus is on subroutines.
Figure 18.2
// PreOOP02.java// This is a bad way to show a sorting algorithm
// with all the code in the main method.
public class PreOOP02
{
public static void main(String[] args)
{
int[] list = {11,99,22,88,33,77,44,66,55};
for (int k = 0; k < list.length; k++)
System.out.print(list[k] + " ");
System.out.println();
for (int p = 1; p < list.length; p++)
{
for (int q = 0; q < list.length-p; q++)
{
if (list[q] > list[q+1])
{
int temp = list[q];
list[q] = list[q+1];
list[q+1] = temp;
}
}
}
for (int k = 0; k < list.length; k++)
System.out.print(list[k] + " ");
System.out.println();
}
}
Program PreOOP03.java, in figure 18.3, is the classic Pre-OOP program. It uses the concept of one task, one module as you see that there is a method for show and for sort. We have more readability. We have re-use of the same algorithm and the program will be easier to debug and enhance in the future.
Figure 18.3
// PreOOP03.java// Modules or methods now organize the program.
// This is PreOOP separation of data and methods.
public class PreOOP03
{
public static void main(String[] args)
{
int[] list = {11,99,22,88,33,77,44,66,55};
show(list);
sort(list);
show(list);
}
public static void show(int[] x)
{
for (int k = 0; k < x.length; k++)
System.out.print(x[k] + " ");
System.out.println();
}
public static void sort(int[] x)
{
for (int p = 1; p < x.length; p++)
{
for (int q = 0; q < x.length-p; q++)
{
if (x[q] > x[q+1])
{
int temp = x[q];
x[q] = x[q+1];
x[q+1] = temp;
}
}
}
}
}
Computer Science multiple-choice tests can rapidly occupy lots of space with the display of lengthy programs. The simple reality is that proper Object Oriented Programming requires that a method is placed inside a class, along with the data structures that the method accesses. That can make for some rather thick tests.
Figure 18.4 shows a typical multiple-choice question. The objective is to see if a student can recognize the algorithmic logic of a sort method. In proper OOP we do not pass the array data structure as a parameter to the sort method. The array data structure should be in a class, as should the sort method. Since we have a proper object constructed of the class, the sort method is called with the object and accesses it very own array data structure without the need of parameters.
That is all lovely, but you may well see a question, such as the one below on the AP Computer Science Examination. It is also possible that you may encounter some old code that has this appearance. And who knows, somebody may not like OOP and stubbornly sticks to the old style of programming. It may not really be that far-fetched. Perhaps somebody needs a quick, short program to sort some data. The truth is that the Pre-OOP approach is faster. Yes, it is less reliable, but given the short length of the program, who will get excited?
Figure 18.4
17. Consider the following sort method.public static void sort(int[] x)
{
for (int p = 1; p < x.length; p++)
{
for (int q = 0; q < x.length-p; q++)
{
if (x[q] < x[q+1])
{
int temp = x[q];
x[q] = x[q+1];
x[q+1] = temp;
}
}
}
}
Assume array x contains {11,99,22,88,33,77,44,66,55}
Which of the following represent the array after calling sort ?
(A) {11,99,22,88,33,77,44,66,55}
(B) {11,22,33,44,55,66,77,88,99}
(C) {99,88,77,66,55,44,33,22,11}
(D) {55,66,44,77,33,88,22,99,11}
(E) {11,11,11,11,11,11,11,11,11}
18.3 The List Class to Study Algorithms
Well we now have arrived at our official Algorithm chapter. In this chapter you will learn some of the common algorithms used in computer science. These algorithms are independent of any particular programming language. The syntax implementation in sample programs may be specific to Java, but the algorithmic considerations carry across all program languages.
In earlier chapters you saw that occasionally material is presented in the form of a Case Study. The Train Case Studyused for class interaction and polymorphism is one example and so are the three AP Labs, Magpie-Chatbot, Picture and Elevens, introduced in 2014. Case studies vary in size, but their common objective is to teach computer science concepts with a sequence of program examples.
This chapter will use a List class and introduces its use in a modest-sized case study. The point is to show that Java static arrays can be a member of an object. You have seen that earlier with several Deck classes. Arrays were used to store Card objects and the Deckclasscombined an array of cards with the methods to manipulate the cards.The creation of a List class allows storage of array elements along with the actions or methods that process the array. This OOP approach creates a neatly encapsulated package for list processing.
The List class will grow with each new algorithm. Program List01.java, shown in figure 18.5, it the first stage of List Case Study. The main method of the program tests the List class. The List class has four methods right now. There are two constructors, an assign method and a display method. The creation of this List class will allow us to study algorithms in a proper OOP environment.
The first constructor has one parameter to indicate the number of array elements. The second constructor has two parameters. The first parameter is for the array size, the second parameter indicates the initial value for each array element.
The assign method assigns new values to each array element, using random values in the [1000..9999] range. The display method shows the value for each element of a List object, called array1 and array2 in this program.
This program and a few later programs will include the entire List class with the program. As the case study advances and grows with each additional method, only the main method and the latest addition of the List class will be shown by itself. Some methods, which are not used in future program examples, will be deleted from the List class. This approach will create greater program clarity as we focus on the newest method.
Figure 18.5
// List01.java// The first stage of the List case study.
public class List01
{
public static void main(String[] args)
{
List list1 = new List(10);
list1.display();
List list2 = new List(10,999);
list2.display();
list2.assign();
list2.display();
}
}
class List
{
private int intArray[];
private int size;
public List(int s)
{
System.out.println("\nConstructing new List object with default values");
size = s;
intArray = new int[size];
}
public List(int s, int n)
{
System.out.println("\nConstructing new List object with specified values");
size = s;
intArray = new int[size];
for (int k = 0; k < size; k++)
intArray[k] = n;
}
public void assign()
{
System.out.println("\nAssigning random values to List object");
for (int k = 0; k < size; k++)
intArray[k] = (int) (Math.random() * 1000);
}
public void display()
{
System.out.println("\nDisplaying array elements");
for (int k = 0; k < size; k++)
System.out.print(intArray[k] + " ");
System.out.println();
}
}
Figure 18.5 Continued
List Case Study #2, Adding a Third Constructor
The assign method provides a set of random values for a List object. These values are always in the [1000..9999] range. Our next step is to create a third constructor that can control the kind of random values that will be assigned to a new List object.
Three parameters are necessary for this new constructor. The first parameter specifies the size of the new List object. The second parameter indicates the smallest possible random integer value. The third parameter passes the value of the largest value of the random integer range. Program List02.java, in figure 18.6, demonstrates the use of this new constructor. Four objects are instantiated with four different random integer ranges. The range of the integers is displayed by the constructor method.
Figure 18.6
// List02.java// This stage adds a third constructor, which instantiates an array object with
// a specified set of random numbers. Old methods, like the first two constructors,
// which are not tested are removed for better program brevity and clarity.
public class List02
{
public static void main(String[] args)
{
List list1 = new List(15,10,20);
list1.display();
List list2 = new List(15,100,999);
list2.display();
}
}
class List
{
private int intArray[];
private int size;
public List(int s, int min, int max)
{
size = s;
System.out.println("\nConstructing List with values in [" + min + ".." + max + "] range");
intArray = new int[size];
int range = max - min + 1;
for (int k = 0; k < size; k++)
intArray[k] = (int) (Math.random() * range + min);
}
public void display()
{
System.out.println("\nDisplaying array elements");
for (int k = 0; k < size; k++)
System.out.print(intArray[k] + " ");
System.out.println();
}
}
List Case Study #3, Adding a pause Method
Before we go too much further with some new algorithms, it is time to make the List class more user-friendly in the input/output department. Output of any sizeable list will fly by on the monitor without allowing proper viewing of the intermediate values. Input right now does not exist. The size of the List objects and the range of the values are hard coded in the programs. This is not a satisfactory arrangement. The first issue of too much output is handled by programList03.java, in figure 18.7. This program adds a pause method to the class.The programmer can select where to call this method to control program output. In our example, pause is called after the display of each list. The result is that the elements of each separate list can be viewed before displaying the next list. Please remember that only the main method is shown completely and the partial List class is shown with the currently introduced pause method.
Figure 18.7
// List03.java// This program adds the <pause> method, which freezes output display until
// the <Enter> key is pressed. This new method allows output viewing on the
// monitor when the display becomes too large.
import java.util.*;
public class List03
{
public static void main(String[] args)
{
List list1 = new List(60,100,200);
list1.display();
list1.pause();
List list2 = new List(100,100,999);
list2.display();
list2.pause();
}
}
class List
{
public void pause()
{
Scanner input = new Scanner(System.in);
System.out.print("\nPress <Enter> to continue ===> ");
String dummy = input.nextLine();
}
}
Figure 18.7 Continued
List Case Study #4, Keyboard Input
The program user now can take control of the program execution process. The three List constructor parameters will be prompted and entered at the keyboard. The input process will be handled by the main method and the input values will then be used to construct the requested List objects. Program List04.java, in figure 18.8, executes the program and then prompts for user input.
Figure 18.8
public class List04{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
System.out.print("\nEnter list size ===> ");
int listSize = input.nextInt();
System.out.print("Enter minimum value ===> ");
int listMin = input.nextInt();
System.out.print("Enter maximum value ===> ");
int listMax = input.nextInt();
List list = new List(listSize,listMin,listMax);
list.display();
}
}
Figure 18.8 Continued