25.3. The InetAddress Class

[Page 745]

Chapter 23. Algorithm Efficiency and Sorting

Mayan God Shel, Mexico. Photographer: Philip Coblentz. Courtesy Brand X Pictures.

Objectives

• To estimate algorithm efficiency using the Big O notation ( §23.2).

• To understand growth rates and why constants and smaller terms can be ignored in the estimation ( §23.2).

• To know the examples of algorithms with constant time, logarithmic time, linear time, log-linear time, quadratic time, and exponential time ( §23.2).

• To analyze linear search, binary search, selection sort, and insertion sort ( §23.2).

• To design, implement, and analyze bubble sort ( §23.3).

• To design, implement, and analyze merge sort ( §23.4).

• To design, implement, and analyze quick sort ( §23.5).

• To design, implement, and analyze heap sort ( §23.6).

• To sort large data in a file ( §23.7).

---

[Page 746]

23.1. Introduction

Sorting is a classic subject in computer science. There are three reasons for studying sorting algorithms. First, sorting algorithms illustrate many creative approaches to problem solving and these approaches can be applied to solve other problems. Second, sorting algorithms are good for practicing fundamental programming techniques using selection statements, loops , methods , and arrays. Third, sorting algorithms are excellent examples to demonstrate algorithm performance.

The data to be sorted might be integers, doubles, characters , or objects. §6.8, "Sorting Arrays," presented selection sort and insertion sort for numeric values. The selection sort algorithm was extended to sort an array of objects in §10.5.7, "Example: Sorting an Array of Objects." The Java API contains several overloaded sort methods for sorting primitive type values and objects in the java.util.Arrays and java.util.Collections class. For simplicity, this section assumes:

1. data to be sorted are integers,

2. data are sorted in ascending order, and

3. data are stored in an array.

The programs can be easily modified to sort other types of data, to sort in descending order, or to sort data in an ArrayList or a LinkedList .

There are many algorithms on sorting. In order to analyze and compare the complexities of these algorithms, this chapter first introduces the Big O notation for estimating algorithm efficiency. The whole chapter is optional. No chapter in the book is dependent on this chapter.