Algorithms in Java

The subject of this chapter is the sorting algorithm that is probably used more widely than any other, quicksort. The basic algorithm was invented in...

Quicksort is a divide-and-conquer method for sorting. It works by partitioning an array into two parts, then sorting the parts independently. As we shall see,...

Despite its many assets, the basic quicksort program has the definite liability that it is extremely inefficient on some simple files that can arise in...

As in we can use an explicit pushdown stack for quicksort, thinking of the stack as containing work to be done in the form...

A definite improvement to quicksort arises from the observation that a recursive program is guaranteed to call itself for many small subfiles, so it should...

Another improvement to quicksort is to use a partitioning element that is more likely to divide the file near the middle. There are several possibilities...

Files with large numbers of duplicate sort keys arise frequently in applications. For example, we might wish to sort a large personnel file by year...

As discussed in Section 6.2, we can write an ITEM interface implementation to use the quicksort implementations in this chapter to sort records with string...

An important application related to sorting but for which a full sort is not required is the operation of finding the median of a set...