Understanding MIT-Style Selection Sort in Python (Q&A Learning Post)

[Rajeev Bagra]

Understanding MIT-Style Selection Sort in Python (Q&A Learning Post

A learner studying sorting algorithms in Python was experimenting with Selection Sort and eventually arrived at the following implementation:

def selectionsort(L):

    for i in range(len(L)):

        for j in range(i, len(L)):

            if L[i] > L[j]:

                L[i], L[j] = L[j], L[i]

During the discussion, the learner wanted to understand:

• whether this was truly Selection Sort
• why it differed from Bubble Sort
• why MIT sometimes teaches this simplified version

The following Q&A explains the algorithm step-by-step.

---

Q1. Is this code actually Selection Sort?

Yes.

The code is a simplified MIT-style implementation of Selection Sort.

def selectionsort(L):

    for i in range(len(L)):

        for j in range(i, len(L)):

            if L[i] > L[j]:

                L[i], L[j] = L[j], L[i]

It works by:

• fixing one position i
• searching the remaining array using j
• bringing smaller values toward the front

That is the core idea behind Selection Sort.

---

Q2. How does the algorithm work conceptually?

Suppose the list is:

L = [64, 25, 12, 22, 11]

During the first pass:

i = 0

the algorithm compares:

64 vs 64
64 vs 25
25 vs 12
12 vs 22
12 vs 11

Whenever a smaller value is found, swapping occurs immediately.

Eventually the smallest value reaches the front.

---

Q3. Why is this considered Selection Sort?

The key comparison is:

if L[i] > L[j]

This means:

• one fixed position i is selected
• the remaining portion of the array is searched using j

That searching behavior is the defining idea behind Selection Sort.

---

Q4. Why is this not Bubble Sort?

Bubble Sort compares neighboring elements only.

Example:

if L[j - 1] > L[j]

That means Bubble Sort performs comparisons like:

5 vs 1
1 vs 4
4 vs 2

Only adjacent values are compared.

However, the learner’s Selection Sort compares distant elements too:

64 vs 11

That is not Bubble Sort behavior.

---

Q5. Why does MIT sometimes teach this simplified Selection Sort?

MIT often prefers teaching versions that are:

• easy to visualize
• easy to trace manually
• simple for beginners to understand

This version avoids introducing an additional variable like:

min_index

which can initially confuse some learners.

---

Q6. What is the standard textbook Selection Sort?

A more optimized version usually looks like this:

def selectionsort(L):

    for i in range(len(L)):

        min_index = i

        for j in range(i + 1, len(L)):

            if L[j] < L[min_index]:

                min_index = j

        L[i], L[min_index] = L[min_index], L[i]

This version:

• finds the smallest element first
• performs only one swap per pass

---

Q7. What is the role of min_index?

This line:

min_index = i

means:

“Assume the current position contains the minimum value for now.”

The algorithm then searches for a smaller value.

---

Q8. Why does the MIT version perform more swaps?

The MIT-style version swaps immediately whenever a smaller value is found:

L[i], L[j] = L[j], L[i]

That can cause multiple swaps during one pass.

The standard version waits until the smallest value is fully identified.

---

Q9. Is the learner’s code logically correct?

Yes.

The learner’s code correctly sorts the list in ascending order.

Example:

numbers = [64, 25, 12, 22, 11]

selectionsort(numbers)

print(numbers)

Output:

[11, 12, 22, 25, 64]

---

Q10. Why does this line create one unnecessary comparison?

The learner wrote:

range(i, len(L))

This includes:

j = i

which compares:

L[i] > L[i]

An element compared with itself is unnecessary.

---

Q11. How can the inner loop be slightly optimized?

Many programmers prefer:

for j in range(i + 1, len(L))

instead.

This avoids self-comparison while preserving the same Selection Sort behavior.

---

Q12. What is the time complexity of this algorithm?

Selection Sort commonly has time complexity:

O(n²)

because nested loops are used.

---

Q13. Why are sorting algorithms important to learn?

Even though Python already provides:

sorted(L)

learning sorting algorithms helps developers understand:

• loops
• comparisons
• swapping
• time complexity
• algorithmic thinking
• problem-solving strategies

These concepts form an important foundation in computer science and software engineering.

[Author]

Posts