O'Reilly logo

Big Java, 4th Edition by Cay Horstmann

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 14. Sorting and Searching

CHAPTER GOALS

  • To study several sorting and searching algorithms

  • To appreciate that algorithms for the same task can differ widely in performance

  • To understand the big-Oh notation

  • To learn how to estimate and compare the performance of algorithms

  • To learn how to measure the running time of a program

Sorting and searching are among the most common tasks in data processing. Of course, the Java library contains methods for carrying out these operations. Nevertheless, studying algorithms for sorting and searching is fruitful because you will learn how to analyze the performance of algorithms and how to choose the best algorithm for a particular task. Sorting and searching are an excellent entry point into the study of algorithm analysis because the tasks themselves are simple to understand. As you will see in this chapter, the most straightforward algorithms do not perform very well, and we can achieve dramatic improvements with more sophisticated algorithms.

Selection Sort

In this section, we show you the first of several sorting algorithms. A sorting algorithm rearranges the elements of a collection so that they are stored in sorted order. To keep the examples simple, we will discuss how to sort an array of integers before going on to sorting strings or more complex data. Consider the following array a:

Selection Sort

An obvious first step is to find the smallest element. In ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required