Understanding Why Some Selection Sort Implementations Store Both the Smallest Value and Its Index

[Rajeev Bagra]

Understanding Why Some Selection Sort Implementations Store Both the Smallest Value and Its Index

A beginner learning Selection Sort may encounter code like this:

smallest = L[i]
smallestj = i

At first glance, this can feel unnecessary because:

• if the index is already known,
• the value can always be accessed using:

L[smallestj]

This naturally raises an important question:

Why store the value separately at all?

Let’s break it down carefully.

---

1. Two Different Approaches

There are two common ways to track the smallest element during Selection Sort.

---

2. Approach 1 — Store Only the Index

Some implementations use:

minindex = i

and compare values like this:

if L[j] < L[minindex]:

In this approach:

• only the position of the smallest element is stored
• the value is retrieved whenever needed using indexing

Conceptually:

minindex → where the smallest value exists
L[minindex] → what that smallest value is

This is compact and efficient.

---

3. Approach 2 — Store Both Value and Index

Other implementations use:

smallest = L[i]
smallestj = i

and later:

if L[j] < smallest:
smallest = L[j]
smallestj = j

Here:

• smallest stores the actual minimum value found so far
• smallestj stores where that value exists in the list

---

4. Why Do Some Teachers Prefer This Style?

The main reason is readability and teaching clarity.

For beginners, this:

if L[j] < smallest:

often reads more naturally than:

if L[j] < L[minindex]:

The first version almost sounds like plain English:

“If the current element is smaller than the smallest value found so far…”

This can make the algorithm easier to mentally follow during early learning.

---

5. Is Storing the Value Necessary?

Technically, no.

If the index is known:

minindex

then the value can always be obtained using:

L[minindex]

So storing both variables is somewhat redundant.

That is why many experienced programmers prefer the shorter approach that stores only the index.

---

6. Historical and Performance Perspective

In older computing systems:

• memory access was slower
• repeated indexing operations could be more expensive

So programmers sometimes stored values separately to avoid repeated lookups.

In modern Python, however, the performance difference here is extremely small.

The choice today is usually based more on:

• readability
• coding style
• teaching preference

than speed.

---

7. Conceptually, Both Versions Are the Same

Both implementations follow the exact same Selection Sort idea:

1. search the unsorted portion of the list
2. find the smallest element
3. swap it into the correct position
4. repeat

The only real difference is how the “current smallest value” is tracked during the search.

---

8. The Core Insight

This discussion highlights an important programming principle:

• multiple implementations can represent the same algorithm
• some versions prioritize compactness
• others prioritize readability and teaching clarity

Learning to recognize that two differently written programs are conceptually identical is an important step toward becoming comfortable with algorithms and programming logic.

[Author]

Posts