I am trying to implement quick sort in dart, The code below works fine When I do not include a negative number. However whenever I include a negative number in the array I get a stack overflow error. I'll be glad if anyone can point me in the right direction as to what I'm doing wrong.

main() {

  // The Partition Function

  int partitionArray(List array, int lowerbound, int upperbound) {
    int start = lowerbound;
    int end = upperbound;
    int pivotElement = array[lowerbound];

    while (start < end) {
      while (array[start] <= pivotElement) {
        start  ;
      }

      while (array[end] > pivotElement) {
        end--;
      }

      // Swap the elements
      if (start < end) {            
        int swapHolder;
        swapHolder = array[start];
        array[start] = array[end];
        array[end] = swapHolder;
      }
    }

    // Swap Pivot element and current element at end
    int pivotSwapHolder;
    pivotSwapHolder = array[lowerbound];
    array[lowerbound] = array[end];
    array[end] = pivotSwapHolder;

    return end;
  }

  List arr = [ 7,5,6,3,7,-5,3,8,];

  

  quickSortElements(List arr, int lower, int upper) {
    if (lower < upper) {
      int midLocation = partitionArray(arr, lower, arr.length - 1);
      quickSortElements(arr, lower, midLocation - 1);
      quickSortElements(arr, midLocation   1, upper);
    }
    print(arr);
  }

  quickSortElements(arr, 0, arr.length - 1);
}

CodePudding user response：

Your bug is not due to the negative value in the array, it could have been any low value and you would have the same problem. The mistake you did was to pass arr.length - 1 as the upperbound value in your recursive call to quickSortElements. See below, I put in comment the line that has been corrected:

quickSortElements(List arr, int lower, int upper) {
  if (lower < upper) {
    //int midLocation = partitionArray(arr, lower, arr.length - 1);
    int midLocation = partitionArray(arr, lower, upper); // corrected line
    quickSortElements(arr, lower, midLocation - 1);
    quickSortElements(arr, midLocation   1, upper);
  }
}