bubbleSort<T>

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

Function Signature

List<T> bubbleSort<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) - When the list is already sorted
• Average Case: O(n²)
• Worst Case: O(n²) - When the list is sorted in reverse order

Space Complexity

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

Implementation

List<T> bubbleSort<T extends Comparable<T>>(List<T> list) {
  final length = list.length;

  for (var i = 0; i < length - 1; i++) {
    for (var j = 0; j < length - i - 1; j++) {
      if (list[j].compareTo(list[j + 1]) > 0) {
        // Swap elements
        final temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }

  return list;
}

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:

   • Gets the length of the input list
   • Uses nested loops to traverse and compare adjacent elements
   • The outer loop runs length - 1 times
   • The inner loop runs length - i - 1 times for each outer loop iteration
   • Compares adjacent elements using compareTo method
   • Swaps elements if they are in wrong order

Example Usage

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

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = bubbleSort(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 stable - maintains relative order of equal elements
   • Useful when maintaining original order is important