Python Program for Selection Sort Algorithm

Hi everyone! In this article, we’ll guide you through the Python Program for Selection Sort Algorithm. With detailed examples, approach, code, it’s explanation & dry run with a comprehensive complexity analysis.

So let’s get started with the [Problem Link].

Problem Statement:

Given an unsorted array of size “N”, use selection sort to sort “arr[]” in increasing order.

Example 1:

  Input:   N = 5
           arr[] = {4, 1, 3, 9, 7}
  Output:  1 3 4 7 9

  Explanation:  Maintain sorted (in bold) and unsorted subarrays.
                Select 1. Array becomes 1 4 3 9 7.
                Select 3. Array becomes 1 3 4 9 7.
                Select 4. Array becomes 1 3 4 9 7.
                Select 7. Array becomes 1 3 4 7 9.
                Select 9. Array becomes 1 3 4 7 9.

Example 2:

  Input:  N = 10
          arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
  Output: 1 2 3 4 5 6 7 8 9 10

Your Task: You don’t need to read input or print anything. Complete the functions “select()” and “selectionSort()” ,where “select()” takes “arr[]” and starting point of unsorted array “i” as input parameters and returns the selected element for each iteration in selection sort, and “selectionSort()” takes the array and it’s size and sorts the array.

Expected Time Complexity: O(N²)

Expected Auxiliary Space: O(1)

Constraints: 1 ≤ N ≤ 10³

Approach for Selection Sort in Python:

The “Selection Sort” algorithm works by dividing the array into two parts: the sorted and unsorted portions. It repeatedly selects the smallest element from the unsorted portion and swaps it with the first element of that unsorted section, effectively growing the sorted portion one element at a time.

Key Steps in the Approach:

1. Start with the first element as the current minimum
2. Compare it with every other element in the unsorted portion of the array
3. If a smaller element is found, update the current minimum index
4. Swap the minimum element with the first element of the unsorted portion
5. Move the boundary of the sorted and unsorted portions by one and repeat until the entire array is sorted

Read about the Python Program to Reverse Array Using Recursion and While Loop.

Code:

class Solution:
    def select(self, arr, i):
        n = len(arr)
        for i in range(0, n):
            min_index = i
            for j in range(i + 1, n):
                if arr[j] < arr[min_index]:
                    min_index = j
            arr[i], arr[min_index] = arr[min_index], arr[i]

    def selectionSort(self, arr, n):
        self.select(arr, 0)

Code Explanation:

1. Outer Loop (for “i” in range(0, n)):
   • This loop iterates through the entire array
   • At each iteration, it considers the element at index “i” as the current minimum
2. Initialization of “min_index”:
   • The variable “min_index” stores the index of the smallest element in the unsorted portion of the array
   • Initially, “min_index” is set to “i”
3. Inner Loop (for “j” in range(i + 1, n)):
   • This loop iterates through the unsorted portion of the array, starting from i + 1
   • If a smaller element than the current minimum is found (arr[j] < arr[min_index]), the “min_index” is updated to “j”
4. Swapping (arr[i], arr[min_index] = arr[min_index], arr[i]):
   • After finding the smallest element in the unsorted portion, it is swapped with the element at index “i”
   • This ensures that the element at index “i” is the smallest in the remaining array
5. Repeat Until Sorted:
   • The boundary of the sorted and unsorted portions of the array moves forward with each iteration, and the process is repeated until the array is completely sorted

Dry Run:

Let’s see an example below:

Complexity Analysis:

1. Time Complexity:
   • Outer Loop: Runs n times
   • Inner Loop: Runs n−1, n−2, …, 1 times
   • Total comparisons: n × (n−1)/2 = O(n²)
   • Worst Case: O(n²), when the array is in reverse order
   • Best Case: O(n²), as no early exit optimization is included
   • Average Case: O(n²)
2. Space Complexity:
   • The algorithm operates in-place, so no additional memory is required apart from a few variables
   • Space Complexity: O(1)

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.