Selection Sort

Problem Solved

Selection Sort solves the Sorting problem.

Design and Strategy

Selection sort is an iterative sorting algorithm that uses a brute-force approach to sort a list by repeatedly selecting the maximum (or minimum) element from the unsorted portion of the array and placing it in the correct position. The algorithm conceptually divides the array into two parts: a sorted subarray that grows from the end, and an unsorted subarray that shrinks with each pass. Thus, Selection Sort can be viewed as a decrease-and-conquer algorithm because the problem size decreases with every iteration.

In each iteration, the algorithm scans the unsorted portion of the array to find the largest unsorted element. Once identified, this maximum value is swapped with the rightmost element in the unsorted subarray. This operation effectively moves the largest unsorted value into its final position in the sorted subarray. After the swap, the boundary between the sorted and unsorted portions shifts one position to the left, expanding the sorted portion and reducing the unsorted one. This process continues until the unsorted portion is reduced to a single element, at which point the array is fully sorted.

The algorithm typically uses two pointers:

• The i pointer marks the boundary between the unsorted and sorted portions, starting at the end of the array and moving leftward.
• During each iteration, the j pointer traverses from the beginning of the unsorted portion up to index i, scanning to find the maximum value.

After each pass, the element at index i is guaranteed to be in the correct position. The algorithm proceeds by decrementing i and repeating the process until the array is sorted.

More formally, the algorithm works as follows:

1. Use pointer i, starting at the last index, moving leftward after each pass.
2. In each iteration:
   • Find the maximum value in the unsorted portion using pointer j (from start up to i).
   • Swap the maximum element found with the element at position i.
   • Move pointer i one step left.
3. Repeat until the unsorted portion contains only one element.

Implementation in Java, C++, Python

void selectionSort(int[] arr) {
   for (int i = arr.length - 1; i > 0; i--) {
     int maxIndex = i;
     for (int j = 0; j < i; j++) {
         if (arr[j] > arr[maxIndex]) {
           maxIndex = j;
         }
     }
     int temp = arr[i];
     arr[i] = arr[maxIndex];
     arr[maxIndex] = temp;
   }
}

void selectionSort(int arr[], int n) {
   for (int i = n - 1; i > 0; i--) {
     int maxIndex = i;
     for (int j = 0; j < i; j++) {
         if (arr[j] > arr[maxIndex]) {
           maxIndex = j;
         }
     }
     int temp = arr[i];
     arr[i] = arr[maxIndex];
     arr[maxIndex] = temp;
   }
}

def selection_sort(arr):
  for i in range(len(arr) - 1, 0, -1):
    max_idx = i
    for j in range(i):
      if arr[j] > arr[max_idx]:
        max_idx = j
    arr[i], arr[max_idx] = arr[max_idx], arr[i]

Time/Space Analysis

Time Complexity: To analyze the time complexity of Selection Sort, we consider the number of comparisons the algorithms does, since it only swaps once the inner loop has terminated. Given the fixed nature of Selection Sort, it performs the same number of comparisons regardless of the input. This means its best-, average-, and worst-case time complexities are identical.

On each pass through the array, Selection Sort scans the unsorted portion to find the maximum element and places it in its correct position. In the first pass, it makes \( n - 1 \) comparisons. In the second pass, it makes \( n - 2 \) comparisons, and so on, until just one element remains unsorted. Thus, the total number of comparisons is

\[ \sum_{i=1}^{n-1}i = \frac{(n-1)(n)}{2} = O(n^2). \]

Space Complexity: The algorithm uses only a constant amount of auxiliary memory (a few index variables and a swap variable). Therefore, the space complexity is \( O(1). \)

Variations/Improvements

• Left-to-Right Selection Sort (Minimum-Based): A commonly used variant of Selection Sort builds the sorted portion of the array from left to right by selecting the minimum value during each pass and placing it at the beginning of the unsorted region. This approach contrasts with the max-to-end version, where the largest value is placed at the end.
• Dual-Ended Optimization: A key optimization to standard Selection Sort involves simultaneously locating both the minimum and maximum elements during each pass through the array. This enhancement leverages the observation that, in each pass, one element can be placed at the beginning of the unsorted region and another at the end, effectively sorting two elements per iteration instead of one.

Helpful Links and Resources

1. Visualgo – Sorting Visualizations
2. GeeksforGeeks – Selection Sort
3. Wikipedia – Selection Sort
4. Select-sort with Gypsy folk dance
5. Sorting Demos
6. 15 Sorting Algorithms in 6 Minutes

Reading Comprehension Questions

1. Why does selection sort always have the same number of comparisons, regardless of input order?
2. What part of the array is considered “sorted” during the execution of selection sort?
3. What technique does selection sort use? Explain.
4. What is the time complexity of selection sort?
5. Perform selection sort on the array [46, 89, 8, 34, 33, 77].

In-class Activities

1. Go over the left-to-right Selection Sort (minimum-Based) variation of the algorithm.
2. Is the right-to-left or the left-to-right better? Explain.
3. Compare and contrast Selection Sort with Bubble Sort and Insertion Sort.
   1. How is it similar to each?
   2. How is it different than each?
   3. Which of them is better?
4. Discuss any potential optimizations to Selection Sort.

Problems

1. Implement Selection Sort so that it tracks both the minimum and maximum each pass and moves them to opposite ends.
2. Implement Selection Sort so that it sorts strings alphabetically. Does this affect the time complexity of the algorithm? Explain why.
3. Write a version of Selection Sort that uses recursion instead of iteration. What is the computational complexity of this version?
4. Give an implementation of Selection Sort using a linked list instead of an array.
5. Analyze the time complexity for Selection Sort on a linked list.
6. Given a list ['c','v','e','a','f','b','q','w'] show the steps necessary for Selection Sorts and Bubble Sort. Make sure to give the array at the end of each iteration of the outer loop.
   1. Compare the arrays from both algorithms at the end of each iteration. What do you notice?
   2. Compute the number of comparisons and swaps for each algorithm. Are the results what you expected?
   3. Discuss and compare the performance of both algorithms.