Selection Sort with list

• Another O(n^2) sorting algorithm that repeatedly selects the smallest element from the unsorted portion of the array.

def selection_sort(arr):
    # takes an input list arr
    n = len(arr)
    # calculates the length of the list.

    # Traverse through all array elements; iterates over the entire list. 
    # Each iteration places the next smallest element at the correct position in the sorted subarray.

    for i in range(n):
        min_idx = i
         # Find the minimum element in the remaining unsorted array
         # initializes the minimum index to the current position of the outer loop.
        for j in range(i+1, n):
            # iterates through the unsorted part of the list to find the index of the smallest element.
            if arr[j] < arr[min_idx]:
                # updates the minimum index if a smaller element is found.
                min_idx = j
        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

• outer loop for i in range(n) iterates through each element of the list.
• Inside the outer loop, we find the index of the minimum element (min_idx) in the unsorted portion of the list using the inner loop for j in range(i+1, n). If we find an element smaller than the current minimum (arr[j] < arr[min_idx]), we update min_idx. After finding the minimum element, we swap it with the first unsorted element (arr[i]) using arr[i], arr[min_idx] = arr[min_idx], arr[i]. Step 1. Initialization:
• The algorithm starts at the beginning of the list.
• It maintains two subarrays: one that is already sorted and one that is unsorted.

Step 2. Finding the Minimum:

• In each iteration, the algorithm finds the minimum element from the unsorted subarray.

Step 3. Swapping:

• It swaps the found minimum element with the first element of the unsorted subarray.
• After each iteration, the boundary between the sorted and unsorted subarrays moves one element to the right.

Step 4. Repeat:

• The process is repeated for the remaining unsorted part of the list until the whole list is sorted.

Selection Sort with tuple

• Tuples are like immutable lists – you can’t change their elements once created.
• However, you can still apply Selection Sort to a tuple. Just create a new tuple with the sorted elements.
• Immutability: If the data structure is immutable (like tuples), you’ll need to create a new structure to store the sorted result.

def sort_tuple(data):
"""Sorts a tuple using Selection Sort.
Returns a new sorted tuple.
"""
  n = len(data)
  sorted_data = []  # Use a list to store sorted elements
  for i in range(n):
    min_index = i
    for j in range(i + 1, n):
      if data[j] < data[min_index]:
        min_index = j
    sorted_data.append(data[min_index])  # Add to list
  return tuple(sorted_data)  # Convert list to tuple

my_tuple = (5, 2, 8, 1, 9)
sorted_tuple = selection_sort_tuple(my_tuple)
print(sorted_tuple)  # Output: (1, 2, 5, 8, 9)

• The function uses a list (sorted_data) to store the sorted elements because tuples are immutable.
• After finding the minimum element in each pass, it’s appended to the list.
• the list is converted back to a tuple using tuple(sorted_data).

Selection Sort with tuple

• Sets (unordered collections of unique elements) for Selection Sort wouldn’t be a traditional way to sort a set.
• However, you can still use Selection Sort to get a sorted list representation of a set’s elements

def selection_sort_set(data):
  """Sorts a set using Selection Sort and returns a sorted list."""
  n = len(data)
  sorted_data = []
  for i in range(n):
    min_element = min(data)  # Find the minimum element directly
    data.remove(min_element)  # Remove it from the set
    sorted_data.append(min_element)  # Add it to the list
  return sorted_data

my_set = {5, 2, 8, 1, 9}
sorted_list = selection_sort_set(my_set)
print(sorted_list)  # Output: [1, 2, 5, 8, 9]

• find the minimum element in the set directly.
• then remove this element from the set using data.remove(min_element).
• the sorted elements are collected into a list.
• Efficiency: Selection Sort, while easy to understand, is generally less efficient than algorithms like Merge Sort or Quick Sort, especially for large datasets.