Understanding Why Swapping With smallest Does Not Properly Work in Selection Sort

[Rajeev Bagra]

Understanding Why Swapping With smallest Does Not Properly Work in Selection Sort

A beginner learning Selection Sort may naturally wonder:

If smallest already contains the smallest value, why can’t we simply swap using:

L[i], smallest = smallest, L[i]

At first glance, this seems logical because:

• smallest already contains the correct smallest value
• Python supports tuple swapping
• the smallest value appears to move into the correct position

This naturally raises an important question:

If smallest contains the value, why is L[smallest_j] still necessary?

Let’s break it down carefully.

---

1. The Original List

Suppose the list is:

L = [7, 3, 9, 1]

During Selection Sort, the algorithm eventually finds:

smallest = 1 smallest_j = 3

Meaning:

• smallest stores the value 1
• smallest_j stores where that value exists in the list

---

2. A Crucial Difference

This is the key idea:

Expression	Meaning
smallest	the value 1
smallest_j	the index 3
L[smallest_j]	the actual storage location inside the list

This distinction is extremely important.

---

3. Why Real Swapping Requires Locations

A true swap means:

Move value A into location B
AND
Move value B into location A

So Python must modify:

• two actual positions inside the list

That is why Selection Sort correctly uses:

L[i], L[smallest_j] = L[smallest_j], L[i]

because both sides refer to real list locations.

---

4. What Goes Wrong With Using smallest

Now consider:

L[i], smallest = smallest, L[i]

Suppose:

i = 0

Python performs:

L[0] = 1
smallest = 7

Result:

L = [1, 3, 9, 1]

Notice something important:

• the original 1 still remains at index 3
• the value 7 disappeared from the list

The algorithm accidentally duplicated one value and lost another.

---

5. Why This Happens

The reason is subtle but fundamental.

The variable:

smallest

is only a temporary variable holding a value.

It is NOT the same thing as:

• the actual slot inside the list structure

Changing:

smallest

does not automatically change:

L[3]

because they are not the same storage location.

---

6. Visualizing the Difference

Conceptually:

Index:   0   1   2   3
Value:   7   3   9   1

Now:

smallest = 1

can be imagined like:

• a sticky note containing the number 1

But:

L[3]

is:

• an actual box inside the list memory structure

Swapping requires moving contents between boxes.

Changing the sticky note does not modify the original box.

---

7. The Correct Selection Sort Swap

That is why Selection Sort correctly uses:

L[i], L[smallest_j] = L[smallest_j], L[i]

because:

• both sides refer to actual list positions
• both values remain preserved
• nothing gets duplicated or lost

---

8. The Core Insight

This example introduces an important programming principle:

• a variable holding a value is not always the same as a reference to mutable storage
• algorithms often depend on modifying real data structures, not temporary copies

Understanding this distinction is a major step toward understanding:

• memory
• references
• data structures
• algorithm implementation

So even this small Selection Sort detail introduces a foundational programming concept.

[Author]

Posts