shellSort<T>

A generic implementation of the Shell Sort algorithm that can sort any list of comparable elements using a gap sequence approach.

Function Signature

List<T> shellSort<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 log n)
• Average Case: O(n^1.25)
• Worst Case: O(n^2)

Space Complexity

• O(1) - Only requires a constant amount of additional memory space

Implementation

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

  // Start with a large gap, then reduce the gap
  for (var gap = n ~/ 2; gap > 0; gap ~/= 2) {
    // Do a gapped insertion sort for this gap size
    for (var i = gap; i < n; i++) {
      var temp = result[i];
      var j = i;

      // Shift earlier gap-sorted elements up until the correct location for temp is found
      while (j >= gap && result[j - gap].compareTo(temp) > 0) {
        result[j] = result[j - gap];
        j -= gap;
      }

      // Put temp in its correct location
      result[j] = 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 a gap sequence starting with n/2 and dividing by 2 each iteration
   • For each gap size, performs a gapped insertion sort
   • Reduces gap size until it becomes 0
   • Returns the sorted array

Example Usage

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

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = shellSort(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:

   • More efficient than simple insertion sort
   • Performance depends on gap sequence used
   • Works well for medium-sized arrays
   • Generally slower than Quick Sort for large datasets

3. Stability:

   • Not stable - may change the relative order of equal elements
   • Consider using stable sorting algorithms if order preservation is important