Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Linear Selection Sorts

The sorts we shall consider in this chapter are all closely related, and the logic involved is reasonably straightforward. They are: the Linear Selection, the Linear Selection with Counting, and the Linear Selection with Exchange.

Keith McLuckie, Angus Barber

2. Basic Exchange Sorts

In the previous chapter the sorts considered may be regarded as low-level sorts. The classification of sorts into high and low level is a guide as to their speed and memory requirement, and not a definitive grouping.

Keith McLuckie, Angus Barber

3. Shell's Sort

On 28 July 1959, D. L. Shell described a minimal storage sorting method which has generally become known as the Shellsort, although it is sometimes called the Merge—Exchange or Diminishing Increment Sort. Much attention has been paid to it and there is still active discussion of its properties.

Keith McLuckie, Angus Barber

4. Binary Tree Sort

All the sorts that have so far been discussed have treated the input list as a linear succession of elements. Although they have achieved reasonable speeds their sort times will always be dependent on n ~2 and this has made some of them extremely slow and hence of little use for any large values of n. The next few chapters cover several sorts that impose a structure on the input list. As a result of this structure the lists are treated as a non-linear succession of elements. By treating the input list as non-linear it is possible to cut down on the number of comparisons and exchanges that need to be carried out to sort. Non-linear in this instance means that the list is accessed non-sequentially, that is not one item after another, necessarily.

Keith McLuckie, Angus Barber

5. Tournament Sort

This sort is another tree-based selection sort, and is included not so much for its speed as for the fact that it reduces the memory requirements needed for a tree sort. The sort derives its name from its close relationship with a tournament or knock-out competition. Consider the squash tournament outlined in figure

Keith McLuckie, Angus Barber

6. Quicksort

The Quicksort or partition-exchange sort was first described by C. A. R. Hoare in an article published in Computer Journal in 1962 and in algorithms 63, 64, 65 in the Communications of the Association o f Computing Machinery (CACM). The original article contained many ideas on improving the Quicksort and these speculations have been responsible for a number of variations on Hoare’s Quicksort. Like Shellsort, Quicksort is now a generic name for a number of algorithms, which reflect variations in the approaches to the development of a critical parameter that affects the performance of the method.

Keith McLuckie, Angus Barber

7. Improving the Quicksort

The most vital aspect of the Quicksort lies in the selection of the pivot. The partitioning procedure is also important but not to such a degree as the pivot – very often the method for selecting the pivot affects the partitioning procedure.

Keith McLuckie, Angus Barber

8. Sorting by Insertion

The sorts covered previously have shown how an input list may be sorted using counting, selection and exchanging techniques. The sorts contained in this and the next chapter will not improve upon the time achieved by the Quicksort but will demonstrate other methods of sorting, possibly not as obvious as the exchange and counting techniques already demonstrated. Although the sorts may not be faster, they do have advantages associated with them that might make them a better choice than some of the exchange sorts in some applications.

Keith McLuckie, Angus Barber

9. Distributive Sorts

We now come to the second set of sorts that use methods other than selection, exchanging or counting to rank an input list. This book covers only one distributive sort in detail but another is discussed; this is because they use features not normally accessible to everyone on a microcomputer.

Keith McLuckie, Angus Barber

10. Relative Merits

This chapter is intended to provide an overview of all the sorts we have considered, before we move on to our brief discussion of merges. When we began writing this book we had no intention of running a competition to find the fastest sort, although that is how it appears to have ended up! The idea of the QQ Sort and its hybrid also developed during the course of writing.

Keith McLuckie, Angus Barber

11. Merges

Merges are essentially the province of mainframe computers which have access to large numbers of disc and tape drives, and they are considered only in a minor way here. It is well within the bounds of possibility that, at some time, a programmer using a small computer is going to wish to form one file from several (for example, when sorting a large number of elements) and merging will permit this. Merges are generally external methods but they can be used effectively as internal methods, and two internal methods of merging are described here — the Multi-pass Two-way Merge and the Natural Two-way Merge. An internal method is one where no input or output operations occur during the course of the merge. By contrast an external method carries out input and output operations during the course of the merge. Both types write out their results when the merge ends of course.

Keith McLuckie, Angus Barber

12. Sort Systems

This chapter is written for the more serious designer of sorts, although it can offer useful insights into the world of sorting to less enthusiastic readers.

Keith McLuckie, Angus Barber

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise