Advanced Algorithms: Variable Decrease-and-Conquer

decrease_and_conquer.dart

// Advanced Algorithms: Decrease and Conquer

// https://gist.github.com/Esgrima/7d49182a728fe0a96d32c23da21919c2
// View and Run at this link:
// https://dartpad.dev/7d49182a728fe0a96d32c23da21919c2

// Utility class of Partitioning algorithms
class Partition {
  
  static int lomuto(List list){
    int pivot = list[0];
    int pivot_index = 0;
    
    for (int i = 1; i < list.length; i++){
      if (list[i] < pivot){
        pivot_index += 1;
        list.swap(pivot_index, i);
      }
    }
    
    list.swap(0, pivot_index);
    
    return pivot_index;
  }
}

// Class of different selection/search algorithms
class Selection{
  
  static Object quickSelect(List list, int kth){
    
    assert (0 < kth && kth < list.length);
    
    // n - 1 key comparisons => O(n)
    var pivot_index = Partition.lomuto(list);
    
    // Best Case: O(n)
    if (pivot_index == kth - 1) {
      return list[pivot_index];
    } 
    // Potential Worst Case: Poorly partitioned list
    // ( 1 part empty and other part n - 1 )  => O(n^2)
    else if (pivot_index > kth - 1){
      return quickSelect(list.sublist(0, pivot_index - 1), kth);
    } else {
      return quickSelect(list.sublist(pivot_index + 1, list.length), kth - 1 - pivot_index);
    }
        
  }
}

// https://dart.dev/guides/language/extension-methods
extension Swap on List {
  
  void swap(int a, int b){
    int temp = this[a];
    this[a] = this[b];
    this[b] = temp;
  }
}


// In reality, there would be <file>_test.dart
void main() {
  List list = [4, 1, 10 , 8, 7, 12, 9, 2, 15];
  
  int selected = Partition.lomuto(list);
  
  print(list);
  print(selected);
  
  
  list = [4, 1, 10 , 8, 7, 12, 9, 2, 15];
    
  assert(Selection.quickSelect(list, 5) == 8);
  print(Selection.quickSelect(list, 5));
}