Sorting and Ordering

The Central Idea

Sorting takes a collection of items and rearranges them according to an ordering rule.

If

are numbers, an ascending sort produces a sequence satisfying

The important point is that the algorithm changes the arrangement, not the underlying collection of values.

Why Sorting Matters

Ordered data is easier to search, compare, summarize, and interpret.

Sorting can support:

• binary search;
• finding minimum and maximum values;
• detecting duplicates;
• grouping equal or related records;
• ranking objects;
• merging datasets;
• preparing data for later algorithms.

Ordering Rules

A sorting algorithm needs a rule that tells us which of two items should come first.

For numbers, we often use the usual order:

For words, we may use alphabetical order.

For records, we may compare a chosen field such as date, price, score, or priority.

Comparison Functions

A comparison function determines the relative order of two items.

For example, a comparison might ask:

• Is \(x
• Does record \(A\) have an earlier date than record \(B\)?
• Does task \(P\) have greater priority than task \(Q\)?

Many sorting algorithms depend entirely on repeated comparisons of this kind.

Ascending and Descending Order

In ascending order, values increase:

In descending order, values decrease:

The same algorithmic ideas can usually be adapted to either direction by reversing the comparison rule.

Sorting Must Preserve the Elements

A correct sort must not lose, duplicate, or invent entries.

If the original collection is

then an ascending result is

Both copies of \(8\) must remain.

Permutation Viewpoint

Sorting rearranges positions.

The output is a permutation of the input: it contains the same elements with the same multiplicities, but possibly in a different order.

Correctness therefore requires two properties:

1. the output is ordered;
2. the output is a permutation of the input.

Selection Sort

Selection sort repeatedly selects the smallest remaining entry and places it into the next output position.

Consider

The smallest value is \(2\), so place it first:

The first position is now fixed.

Continuing Selection Sort

From

examine the unsorted portion

Its smallest entry is \(4\), which is already in the correct next position.

Next, among

the smallest is \(6\), so swap it into place:

The Selection Sort Invariant

After each selection-sort pass:

The positions already completed contain the smallest elements in their correct sorted order.

The algorithm repeatedly extends this correctly sorted prefix.

Selection Sort Procedure

1. Begin at the first unsorted position.
2. Search the remaining positions for the smallest entry.
3. Swap that entry into the current position.
4. Advance the boundary between sorted and unsorted positions.
5. Repeat until no unsorted positions remain.

Selection Sort Comparisons

For \(n\) entries, selection sort compares the first position with \(n-1\) later entries.

Then it makes

comparisons for the next position, then

and so on.

The total is

Triangular Growth in Selection Sort

The sum

equals

Thus the number of comparisons grows proportionally to

Later lessons will formalize this kind of growth using complexity notation.

Insertion Sort

Insertion sort builds a sorted region one item at a time.

Each new item is inserted into the correct position among the items already sorted.

Consider

Treat \(7\) as initially sorted.

Continuing Insertion Sort

Insert \(4\) before \(7\):

The first two entries are now sorted.

The next value, \(9\), already belongs after \(7\):

Then insert \(2\) before all three:

The Insertion Sort Invariant

After each insertion:

The processed prefix is sorted and contains exactly the items that originally appeared in that prefix.

Each step extends the sorted prefix by one element.

Insertion Sort Procedure

1. Treat the first entry as a sorted region of size one.
2. Take the next unsorted entry.
3. Compare it with entries in the sorted region.
4. Shift larger entries as needed.
5. Insert the new entry into its correct location.
6. Repeat until all entries are included.

Insertion Sort Can Exploit Existing Order

Suppose the list is nearly sorted:

Only the value \(5\) needs to move significantly.

Insertion sort can take advantage of this existing order because each item is inserted only as far as necessary.

This contrasts with algorithms whose comparison pattern changes very little even when the input is almost sorted.

Bubble Sort

Bubble sort repeatedly compares adjacent entries and swaps them when they appear in the wrong order.

Consider

Compare \(5\) and \(2\). Since

swap them:

A Bubble Sort Pass

Continue comparing adjacent entries:

Since \(5<8\), leave them.

Since \(8>3\), swap:

After one full left-to-right pass, the largest entry has moved to the end.

The Bubble Sort Invariant

After each complete pass through the unsorted region:

At least one largest remaining element has moved into its final position at the right end.

Repeated passes shrink the unsorted region.

Bubble Sort Procedure

1. Compare the first adjacent pair.
2. Swap them if they are out of order.
3. Move one position to the right.
4. Continue through the current unsorted region.
5. Repeat passes until the sequence is sorted.

Stopping Bubble Sort Early

A useful refinement records whether any swap occurred during a pass.

If a full pass makes no swaps, then every adjacent pair is already in order.

Therefore, the entire sequence is sorted and the algorithm may stop early.

Comparing the Three Basic Methods

Selection sort, insertion sort, and bubble sort all eventually produce a sorted sequence, but they organize their work differently.

• Selection sort chooses the next smallest remaining item.
• Insertion sort inserts each new item into a sorted prefix.
• Bubble sort repeatedly fixes adjacent inversions.

Different internal strategies can solve the same abstract problem.

What Is an Inversion?

In an ascending-order sequence, an inversion is a pair of positions \(i \[ a_i>a_j. \]

For example, in

the pairs \((4,1)\) and \((4,3)\) are inversions.

Sorting as Removing Inversions

A sequence is sorted in ascending order exactly when it has no inversions.

Bubble sort attacks inversions locally by swapping adjacent entries that are out of order.

Insertion sort removes inversions as each new entry is moved left to its proper position.

The inversion viewpoint provides a useful mathematical way to measure disorder.

Stable Sorting

A sorting algorithm is stable if equal-key items keep their original relative order.

Suppose records are labeled

If the records are sorted by score and \(A\) originally appears before \(C\), a stable sort keeps \(A\) before \(C\) among the equal-score records.

Why Stability Matters

Stability becomes important when records have multiple fields.

Suppose employee records have both:

• department;
• last name.

If records are first sorted by last name and then stably sorted by department, the alphabetical order within each department is preserved.

In-Place Sorting

An in-place sorting algorithm rearranges entries primarily within the original storage rather than building a separate full-sized copy of the collection.

Swapping entries inside an array is a typical in-place operation.

Memory usage is therefore another dimension along which sorting methods can differ.

Comparisons and Swaps Are Different Costs

Sorting algorithms may perform:

• comparisons;
• swaps;
• shifts;
• copies;
• temporary storage operations.

Two algorithms with similar comparison counts may behave differently if one moves data much more often than the other.

Best Case and Worst Case

The same algorithm can require different amounts of work on different inputs of the same size.

For example, insertion sort processes an already sorted list with relatively little movement.

A reverse-sorted list may require many shifts.

Algorithm analysis therefore often distinguishes best-case, worst-case, and typical behavior.

Sorting and Search Work Together

Sorting may require computational effort up front, but once the data is ordered, later operations may become easier.

For example, binary search relies on ordered data.

This creates a common tradeoff:

Spend work organizing the data now in order to save work on later queries.

Sorting by More Than One Key

Records are often ordered by a sequence of criteria.

For example:

1. sort by state;
2. within each state, sort by city;
3. within each city, sort by last name.

Such rules define a lexicographic or hierarchical ordering.

Lexicographic Order

Lexicographic order compares the first available component where two objects differ.

For ordered pairs, one possible rule is

if either

Partial Orders Are Different

Not every useful relation gives a complete ranking.

In a partial order, some pairs of elements may be incomparable.

For example, divisibility on positive integers satisfies

and

but neither \(2\mid 3\) nor \(3\mid 2\).

Total Orders and Ordinary Sorting

Standard sorting algorithms generally assume a total order: for any two items \(x\) and \(y\), the comparison rule can determine whether

Sorting with Duplicate Values

Duplicate values do not prevent sorting.

For

an ascending order is

Stability determines how associated records with equal keys are arranged, not whether equal values may occur.

Sorting Is Not the Same as Ranking

Sorting produces an ordered sequence.

Ranking assigns positions such as first, second, and third.

When ties occur, additional conventions are needed to determine rank.

Thus sorting can support ranking, but the two tasks are not identical.

Correctness of a Sorting Algorithm

A sorting algorithm is correct if, when it terminates:

1. the output satisfies the required ordering relation;
2. the output contains exactly the same multiset of items as the input.

Loop invariants are often used to prove these properties.

Termination of Basic Sorting Algorithms

Selection sort, insertion sort, and bubble sort all work on finite lists.

Each major pass either:

• fixes another position;
• extends a sorted prefix;
• or shrinks the unsorted region.

Because only finitely many positions exist, the process terminates.

Common Error: Sorting Without a Clear Comparison Rule

A statement such as "sort these records" is incomplete unless the ordering key is known.

Should records be ordered by:

• name;
• date;
• price;
• score;
• priority?

The comparison rule is part of the problem definition.

Common Error: Losing Duplicate Entries

Sorting is a rearrangement, not a duplicate-removal procedure.

If the input is

then

is not a correct sorted output because one copy of \(4\) has disappeared.

Common Error: Assuming One Sort Is Always Best

Different algorithms can be preferable under different constraints.

Relevant considerations include:

• input size;
• how nearly sorted the data already is;
• memory limits;
• need for stability;
• cost of comparisons;
• cost of moving records.

Common Error: Confusing Stable with Sorted

A sequence can be correctly sorted even if equal-key records change their relative order.

Stability is an additional property.

It matters only when equal keys correspond to distinct underlying records whose original relative order may be meaningful.

Common Error: Assuming Fewer Swaps Means Fewer Comparisons

Selection sort may make relatively few swaps, but it still performs many comparisons while searching for each minimum.

Comparison count and movement count measure different aspects of performance.

A Reliable Procedure for Selection Sort

1. Identify the first unsorted position.
2. Scan the remaining entries for the smallest value.
3. Swap that value into the current position.
4. Advance the sorted boundary by one position.
5. Repeat until the entire list is sorted.

A Reliable Procedure for Insertion Sort

1. Begin with a one-item sorted prefix.
2. Take the next entry from the unsorted region.
3. Move larger sorted entries one position to the right as needed.
4. Insert the new entry into the open location.
5. Repeat until all entries have been inserted.

A Reliable Procedure for Bubble Sort

1. Start at the left edge of the unsorted region.
2. Compare adjacent entries.
3. Swap them if they are out of order.
4. Continue to the right.
5. After the pass, reduce the unsorted region.
6. If a pass makes no swaps, stop early.
7. Otherwise repeat.

Example: Selection Sort

Sort

First choose the smallest entry, \(1\):

The smallest remaining entry is \(3\), already in place.

The smallest among \(8\) and \(6\) is \(6\):

Example: Insertion Sort

Sort

Insert \(2\) before \(5\):

The \(7\) is already correctly placed relative to the sorted prefix.

Insert \(4\) between \(2\) and \(5\):

Example: Bubble Sort

Sort

First pass:

Second pass:

The list is sorted.

Practice 1: Identify the Order

Is the sequence

sorted in ascending order?

Practice 2: Selection Sort

Use selection sort on

Show the list after each position is fixed.

Practice 3: Insertion Sort

Use insertion sort on

Show the sorted prefix after each insertion.

Practice 4: Bubble Sort

Perform one complete left-to-right bubble-sort pass on

Practice 5: Inversions

List the inversions in

Practice 6: Stability

Records appear in the order

If they are sorted by score in ascending order using a stable sort, which of \(A\) and \(C\) appears first among the score-\(80\) records?

Practice 7: Duplicate Values

Sort

into ascending order.

Practice 8: Selection Sort Comparisons

How many comparisons does standard selection sort make on a list of \(5\) entries?

Practice 9: Nearly Sorted Data

Which of the three basic methods in this lesson is naturally well suited to data that is already nearly sorted?

Practice 10: Sorting Correctness

A program receives

and returns

Explain why this is not a correct sorting result.

Practice Answers

Practice 1

Yes. Equal adjacent values are allowed because ascending order requires

Practice 2

Start with

Place \(1\) first:

The remaining positions are already in order, so the fixed-prefix stages are

Practice 3

Begin with the sorted prefix

Insert \(3\):

Insert \(8\):

Insert \(4\):

Practice 4

One complete pass gives

Practice 5

In

the inversions are

Practice 6

A stable sort preserves the original relative order of equal-key records. Therefore,

Practice 7

Practice 8

Standard selection sort makes

comparisons.

Therefore,

Practice 9

The natural choice among these three is

It can exploit existing order because entries move only as far as needed.

Practice 10

The input contains two copies of \(5\), but the output contains only one.

A correct sort must preserve the entire multiset of input values.

What to Remember

• Sorting rearranges data according to an ordering rule.
• A correct sorted output must be ordered and must preserve all input elements.
• Selection sort repeatedly chooses the smallest remaining item.
• Insertion sort builds a sorted prefix by inserting one new item at a time.
• Bubble sort repeatedly swaps adjacent inversions.
• Stable sorting preserves the relative order of equal-key records.
• In-place sorting primarily rearranges data within its original storage.
• Comparison count, movement count, memory use, and existing order can all affect algorithm choice.

The most important habit is to separate the abstract goal produce a valid order from the specific strategy used to create that order.

Where We Go Next

Search and sorting both rely on repeated, carefully structured steps. Another central algorithmic pattern appears when a procedure solves a problem by calling or defining itself on smaller instances.

The next lesson, Recursive Algorithms, develops recursive procedures, base cases, recursive reduction, call structure, and the relationship between recursion and iteration.