Chapter 13 Sorting & Searching - CCSU

13-1

Java Au Naturel by William C. Jones

13-1

13 Sorting and Searching

Overview

This chapter discusses several standard algorithms for sorting, i.e., putting a number of values in order. It also discusses the binary search algorithm for finding a particular value quickly in an array of sorted values. The algorithms described here can be useful in various situations. They should also help you become more comfortable with logic involving arrays. These methods would go in a utilities class of methods for Comparable objects, such as the CompOp class of Listing 7.2. For this chapter you need a solid understanding of arrays (Chapter Seven).

? Sections 13.1-13.2 discuss two basic elementary algorithms for sorting, the SelectionSort and the InsertionSort.

? Section 13.3 presents the binary search algorithm and big-oh analysis, which provides a way of comparing the speed of two algorithms.

? Sections 13.4-13.5 introduce two recursive algorithms for sorting, the QuickSort and the MergeSort, which execute much faster than the elementary algorithms when you have more than a few hundred values to sort.

? Sections 13.6 goes further with big-oh analysis. ? Section 13.7 presents several additional sorting algorithms -- the bucket sort, the

radix sort, and the shell sort.

13.1 The SelectionSort Algorithm For Comparable Objects

When you have hundreds of Comparable values stored in an array, you will often find it useful to keep them in sorted order from lowest to highest, which is ascending order. To be precise, ascending order means that there is no case in which one element is larger than the one after it -- if y is listed after x, then pareTo(y) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download