This chapter is from the book
This chapter is from the book
This chapter is from the book
Summary
The sorting algorithms in this chapter all assume an array as a data storage structure.
Sorting involves comparing the keys of data items in the array and moving the items (actually, references to the items) around until they're in sorted order.
All the algorithms in this chapter execute in O(N2) time. Nevertheless, some can be substantially faster than others.
An invariant is a condition that remains unchanged while an algorithm runs.
The bubble sort is the least efficient, but the simplest, sort.
The insertion sort is the most commonly used of the O(N2) sorts described in this chapter.
A sort is stable if the order of elements with the same key is retained.
None of the sorts in this chapter require more than a single temporary variable, in addition to the original array.