DSA : Selection Sort with Example

This code implements the Selection Sort algorithm to sort the array my_array in ascending order. Here's a line-by-line explanation:

---

Line-by-Line Explanation

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

• Creates an array called my_array with the given unsorted integers.
• Example: my_array = [64, 34, 25, 12, 22, 11, 90, 5].

---

n = len(my_array)

• Calculates the length of the array and stores it in the variable n.
• Example: n = 8 because there are 8 elements in the array.

---

for i in range(n):

• Starts a loop that iterates over each element of the array using the index i from 0 to n-1.
• Example: For n = 8, i will take values: 0, 1, 2, ..., 7.

---

min_index = i

• Assumes the current element (at index i) is the smallest in the unsorted portion of the array.
• Example (first iteration): When i = 0, min_index = 0 (the value at index 0 is 64).

---

for j in range(i+1, n):

• Starts another loop from i+1 to n-1 using index j to find the smallest element in the unsorted portion of the array.
• Example (first iteration, i = 0): j will take values: 1, 2, 3, ..., 7.

---

if my_array[j] < my_array[min_index]:
    min_index = j

• Compares the current element at index j with the element at min_index. If the element at j is smaller, updates min_index to j.
• Example (first iteration):
  • i = 0, min_index = 0.
  • j = 7 (value = 5) is smaller than my_array[0] (value = 64), so min_index = 7.

---

my_array[i], my_array[min_index] = my_array[min_index], my_array[i]

• Swaps the smallest element (found at min_index) with the element at index i.
• Example (first iteration):
  • Swap my_array[0] (64) with my_array[7] (5).
  • Result after first iteration: [5, 34, 25, 12, 22, 11, 90, 64].

---

print("Sorted array:", my_array)

• Prints the sorted array after all iterations.
• Final output: Sorted array: [5, 11, 12, 22, 25, 34, 64, 90].

---

Example Walkthrough

Initial Array:

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

Iteration 1 (i = 0):

• Unsorted portion: [64, 34, 25, 12, 22, 11, 90, 5].
• Smallest element = 5 (index 7).
• Swap 64 and 5.
• Result: [5, 34, 25, 12, 22, 11, 90, 64].

Iteration 2 (i = 1):

• Unsorted portion: [34, 25, 12, 22, 11, 90, 64].
• Smallest element = 11 (index 5).
• Swap 34 and 11.
• Result: [5, 11, 25, 12, 22, 34, 90, 64].

Iteration 3 (i = 2):

• Unsorted portion: [25, 12, 22, 34, 90, 64].
• Smallest element = 12 (index 3).
• Swap 25 and 12.
• Result: [5, 11, 12, 25, 22, 34, 90, 64].

Iteration 4 (i = 3):

• Unsorted portion: [25, 22, 34, 90, 64].
• Smallest element = 22 (index 4).
• Swap 25 and 22.
• Result: [5, 11, 12, 22, 25, 34, 90, 64].

Iteration 5 (i = 4):

• Unsorted portion: [25, 34, 90, 64].
• Smallest element = 25 (index 4).
• No swap needed.
• Result: [5, 11, 12, 22, 25, 34, 90, 64].

Iteration 6 (i = 5):

• Unsorted portion: [34, 90, 64].
• Smallest element = 34 (index 5).
• No swap needed.
• Result: [5, 11, 12, 22, 25, 34, 90, 64].

Iteration 7 (i = 6):

• Unsorted portion: [90, 64].
• Smallest element = 64 (index 7).
• Swap 90 and 64.
• Result: [5, 11, 12, 22, 25, 34, 64, 90].

Final Sorted Array:

[5, 11, 12, 22, 25, 34, 64, 90]

 Let’s analyze the second iteration of the selection sort algorithm to understand how min_index = i works.

---

Second Iteration (i = 1)

Array at the start of the second iteration:

my_array = [5, 34, 25, 12, 22, 11, 90, 64]

• At this point, the first element (5) is already sorted, so the remaining unsorted portion of the array is: [34, 25, 12, 22, 11, 90, 64]

Step-by-Step Explanation

1. Initialize min_index:

   min_index = i
   

   • i = 1, so min_index = 1.
   • This assumes that the current element at index 1 (34) is the smallest in the remaining unsorted portion.

---

2. Start the inner loop (j from i+1 to n-1):

   for j in range(i+1, n):
   

   • Here, j starts at 2 and goes to 7.

---

3. Compare values to find the smallest element:

   if my_array[j] < my_array[min_index]:
       min_index = j
   

   • First comparison (j = 2):
     • my_array[2] = 25 is less than my_array[1] = 34, so update min_index = 2.
   • Second comparison (j = 3):
     • my_array[3] = 12 is less than my_array[2] = 25, so update min_index = 3.
   • Third comparison (j = 4):
     • my_array[4] = 22 is greater than my_array[3] = 12, so min_index remains 3.
   • Fourth comparison (j = 5):
     • my_array[5] = 11 is less than my_array[3] = 12, so update min_index = 5.
   • Fifth comparison (j = 6):
     • my_array[6] = 90 is greater than my_array[5] = 11, so min_index remains 5.
   • Sixth comparison (j = 7):
     • my_array[7] = 64 is greater than my_array[5] = 11, so min_index remains 5.

---

4. Swap the smallest element with the element at index i:

   my_array[i], my_array[min_index] = my_array[min_index], my_array[i]
   

   • min_index = 5 (smallest element = 11).
   • Swap my_array[1] (34) with my_array[5] (11).
   • Array after the swap: my_array = [5, 11, 25, 12, 22, 34, 90, 64]

---

Key Point:

• At the start of the second iteration, min_index = i = 1, which assumes the element 34 is the smallest in the unsorted portion.
• By checking the remaining elements, the algorithm identifies 11 as the smallest and updates min_index accordingly.

The purpose of keeping and updating min_index is to track the position of the smallest element in the unsorted portion of the array during each iteration. This allows the algorithm to efficiently swap the smallest element into its correct position without unnecessary swaps.

---

The given code implements the Selection Sort algorithm. To understand the values of i, min_index, and the element being pointed to, let's analyze the code step by step.

The outer loop runs i from 0 to n-1, and during each iteration:

• i represents the current position in the array where the smallest value (from i to n-1) will be placed.
• min_index is initialized to i and updated within the inner loop whenever a smaller element is found.

The inner loop iterates over the remaining unsorted portion of the array (from i+1 to n-1) to find the index of the smallest element.

Step-by-step Analysis

Given my_array = [64, 34, 25, 12, 22, 11, 90, 5], let's break it down:

1. First iteration (i = 0)

   • min_index = 0, pointing to 64.
   • The inner loop (j) starts comparing elements:
     • j = 1: 34 < 64, so min_index = 1.
     • j = 2: 25 < 34, so min_index = 2.
     • j = 3: 12 < 25, so min_index = 3.
     • j = 4: 22 > 12, min_index stays 3.
     • j = 5: 11 < 12, so min_index = 5.
     • j = 6: 90 > 11, min_index stays 5.
     • j = 7: 5 < 11, so min_index = 7.
   • After the inner loop, min_index = 7, pointing to 5. Swap my_array[0] with my_array[7].
   • Array after the swap: [5, 34, 25, 12, 22, 11, 90, 64].

2. Second iteration (i = 1)

   • min_index = 1, pointing to 34.
   • Inner loop:
     • j = 2: 25 < 34, so min_index = 2.
     • j = 3: 12 < 25, so min_index = 3.
     • j = 4: 22 > 12, min_index stays 3.
     • j = 5: 11 < 12, so min_index = 5.
     • j = 6: 90 > 11, min_index stays 5.
     • j = 7: 64 > 11, min_index stays 5.
   • After the inner loop, min_index = 5, pointing to 11. Swap my_array[1] with my_array[5].
   • Array after the swap: [5, 11, 25, 12, 22, 34, 90, 64].

3. Third iteration (i = 2)

   • min_index = 2, pointing to 25.
   • Inner loop:
     • j = 3: 12 < 25, so min_index = 3.
     • j = 4: 22 > 12, min_index stays 3.
     • j = 5: 34 > 12, min_index stays 3.
     • j = 6: 90 > 12, min_index stays 3.
     • j = 7: 64 > 12, min_index stays 3.
   • After the inner loop, min_index = 3, pointing to 12. Swap my_array[2] with my_array[3].
   • Array after the swap: [5, 11, 12, 25, 22, 34, 90, 64].

General Observations

• During each iteration of the inner loop, i indicates the position being processed.
• When min_index is updated (min_index = j), it means a smaller element has been found in the array at index j.
• At that moment, i points to the current position of the outer loop, and the current element at i is compared with the element at j.

Reason for min_index:

1. Efficiently Find the Smallest Element:
   • Instead of swapping elements multiple times as we iterate through the array, we simply keep track of the smallest element's position (min_index).
   • This reduces unnecessary operations and ensures that the array is sorted with minimal swaps.

---

2. Separate Finding and Swapping:
   • The inner loop (j) finds the smallest element in the unsorted portion of the array by comparing each element with the current smallest (at min_index).
   • Once the smallest element is identified, only one swap operation is performed (outside the inner loop).
   • This separation makes the algorithm clear and efficient.

---

3. Why Track the Index (and Not the Value)?
   • Tracking the index (e.g., min_index) instead of the value allows us to:
     • Compare elements during the inner loop (my_array[j] < my_array[min_index]).
     • Swap the smallest element to its correct position (my_array[i], my_array[min_index]).
   • If we only kept the smallest value, we wouldn't know where it is in the array, making the swap impossible.

---

Example to Show Its Importance:

Without min_index:

If we tried to directly find and swap the smallest element without keeping track of its index:

1. Current Array: [64, 34, 25, 12, 22, 11, 90, 5]
2. In the first iteration, we find 5 as the smallest value.
3. But without min_index, we wouldn't know that 5 is at index 7, and we can't swap it with 64 (at index 0).

This shows how min_index helps locate the smallest element and ensures the correct swap.

---

Conclusion:

The variable min_index serves as a pointer to the smallest element in the current unsorted portion of the array. It is crucial for identifying the correct element to swap without needing multiple swaps or additional complex logic.