selectionSort<T>

A generic implementation of the Selection Sort algorithm that can sort any list of comparable elements.

Function Signature

List<T> selectionSort<T extends Comparable<T>>(List<T> list)

Parameters

• list: A list of elements of type T that implements the Comparable interface

Return Value

• Returns the sorted list of type List<T>

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(n²)
• Average Case: O(n²)
• Worst Case: O(n²)

Space Complexity

• O(1) - Only requires a single additional memory space for the swap operation

Implementation

List<T> selectionSort<T extends Comparable<T>>(List<T> list) {
  final length = list.length;
  final result = List<T>.from(list);

  for (var i = 0; i < length - 1; i++) {
    var minIndex = i;

    for (var j = i + 1; j < length; j++) {
      if (result[j].compareTo(result[minIndex]) < 0) {
        minIndex = j;
      }
    }

    if (minIndex != i) {
      final temp = result[i];
      result[i] = result[minIndex];
      result[minIndex] = temp;
    }
  }

  return result;
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes a single parameter list of type List<T>
   • Returns a sorted list of the same type

2. Algorithm Steps:

   • Creates a copy of the input list to preserve the original
   • Uses nested loops to find the minimum element
   • The outer loop runs length - 1 times
   • The inner loop finds the minimum element in the unsorted portion
   • Swaps the found minimum with the first element of unsorted portion

Example Usage

void main() {
  // Sorting integers
  var numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Original list: $numbers');
  var sortedNumbers = selectionSort(numbers);
  print('Sorted list: $sortedNumbers');

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = selectionSort(fruits);
  print('Sorted list: $sortedFruits');
}

Output

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

Original list: [banana, apple, orange, grape]
Sorted list: [apple, banana, grape, orange]

Usage Notes

1. Type Constraints:

   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable
   • Custom classes must implement Comparable interface to be sorted

2. Performance Considerations:

   • Best suited for small lists (< 1000 elements)
   • Not recommended for large datasets due to O(n²) complexity
   • Consider using more efficient algorithms like Quick Sort for larger lists

3. Stability:

   • The implementation is not stable - may change relative order of equal elements
   • Consider using Bubble Sort or Insertion Sort if stability is required