algorithms.dart

// function to find the partition position
int partition(List<int> array, int low, int high) {
  // select the rightmost element as pivot
  int pivot = array[high];

  // pointer for greater element
  int i = (low - 1);

  // traverse each element of the array
  // compare them with the pivot
  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {
      // if element smaller than pivot is found
      // swap it with the greater element pointed by i
      i++;

      // swap element at i with element at j
      final temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }

  // swap the pivot element with the greater element at i
  final temp = array[i + 1];
  array[i + 1] = array[high];
  array[high] = temp;

  // return the partition point
  return i + 1;
}

void quickSort(List<int> array, int low, int high) {
  if (low < high) {
    // find the pivot element such that
    // elements smaller than pivot are on left of pivot
    // elements greater than pivot are on right of pivot

    int pi = partition(array, low, high);
    // array = r.array;
    // recursive call on the left of pivot
    quickSort(array, low, pi - 1);

    // recursive call on the right of pivot

    quickSort(array, pi + 1, high);
  }
}

// function to print array elements

// main function
void bubbleSort(List<int> array) {
  for (var i = 0; i < array.length; i++) {
    for (var j = i + 1; j < array.length; j++) {
      if (array[j] < array[i]) {
        final aux = array[i];
        array[i] = array[j];
        array[j] = aux;
      }
    }
  }
}

int linearFinder(
  List<int> array,
  int val,
) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] == val) return i;
  }
  return -1;
}

int binarySearch(List<int> arr, int low, int high, int search) {
  if (high >= low) {
    int mid = (low + (high - low) ~/ 2);

    // If the element is present at the middle
    // itself
    if (arr[mid] == search) {
      return mid;
    }

    // If element is smaller than mid, then
    // it can only be present in left subarray
    if (arr[mid] > search) {
      return binarySearch(arr, low, mid - 1, search);
    }

    // Else the element can only be present
    // in right subarray
    return binarySearch(arr, mid + 1, high, search);
  }

  // We reach here when element is not
  // present in array
  return -1;
}

void main() {
  var data = [
    8,
    7,
    2,
    1,
    0,
    9,
    6,
  ];

  int n = data.length;

  // perform quicksort on data
  // quickSort(data, 0, n - 1);
  bubbleSort(data);
  print(binarySearch(data, 0, n - 1, 8));
  print(data);
}