SESO41 - Editorial

editorial
, ,
1

Problem Link

Selection Sort works by dividing the array into two parts: a sorted section and an unsorted section. Initially, the sorted section is empty, and the unsorted section contains all the elements. The algorithm proceeds as follows:

  1. Outer Loop: The outer loop iterates over each element of the array, treating the current element as the first unsorted element.

  2. Finding the Minimum: For each position in the outer loop, an inner loop is used to search through the unsorted portion of the array to find the index of the minimum element (minIdx).

  3. Swapping: After finding the minimum element in the unsorted section, it is swapped with the first unsorted element (the current element of the outer loop). This effectively moves the minimum element into the sorted section of the array.

  4. Progression: The algorithm continues, reducing the size of the unsorted section by one with each iteration of the outer loop until the entire array is sorted.

Code Explanation

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        // Find the minimum element in the unsorted portion of the array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // Swap the found minimum element with the first unsorted element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

How It Works

  • Initial Step: The algorithm starts by considering the first element as the minimum and iterates through the rest of the array to find the actual minimum element.
  • Swapping: Once the minimum element is found, it is swapped with the first unsorted element, effectively moving it to its correct position in the sorted portion.
  • Subsequent Steps: The process is repeated for the next element in the array until the entire array is sorted.

Complexity Analysis

  • Time Complexity: The time complexity of Selection Sort is O(n^2), where n is the number of elements in the array. This is because for each element, the algorithm scans the remaining unsorted elements to find the minimum.

  • Space Complexity: The space complexity is O(1) since Selection Sort is an in-place sorting algorithm, requiring no additional space beyond the input array and a few auxiliary variables.