QuickSort Lomuto Algorithm

Question

I'm running an implementation of the Lomuto Quicksort algorithm based on: https://en.wikipedia.org/wiki/Quicksort

To test it, I'm trying out a couple of arrays to see if the sorting algorithm implements correctly.

Test Cases:

Array # 1: [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92] 
Array # 2: [11,8,14,3,6,2,7]

This is the code from wikipedia followed to a tee according to my understanding of the Lomuto algorithm:

function quickSort(array) {
  // change code below this line
  var n = array.length;
  var low, hii;
  low = 0;
  hii = n - 1;
  // console.log(sub_qs(array, low, hii));
  array = sub_qs(array, low, hii);
  console.log(array);

  /***** Lomuto Algorithm Scheme *****/
  function sub_qs(arr, lo, hi) {
    if (lo < hi) {
      var p = partition(arr, lo, hi);
      sub_qs(arr, lo, p - 1);
      sub_qs(arr, p + 1, hi)
    }
    return arr;
  }

  function partition(a, l, h) {
    var pivot = a[h];
    var i = l;
    for (var j = l; j < h - 1; j++) {
      if (a[j] < pivot) {
        var temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
      }
      var temp_1 = a[i];
      a[i] = a[h];
      a[h] = temp_1;
    }
    return i;
  }
  /***** Lomuto Algorithm Scheme *****/

  // change code above this line
  return array;
}

And after running the program, my results are:

Results # 1: [1, 1, 8, 2, 32, 2, 63, 43, 55, 43, 123, 4, 92, 345, 123, 234, 5643]
Results # 2: [3, 6, 8, 7, 11, 2, 14]

Something is amiss. What could I be doing wrong?

Answer 1

In your partition the second swap should be outside of the for loop and the for loop needs to include h - 1 so either use for (var j = l; j < h; j++) or for (var j = l; j <= h -1; j++) :

function quickSort(array) {
  // change code below this line
  var n = array.length;
  var low, hii;
  low = 0;
  hii = n - 1;
  array = sub_qs(array, low, hii);

  /***** Lomuto Algorithm Scheme *****/
  function sub_qs(arr, lo, hi) {
    if (lo < hi) {
      var p = partition(arr, lo, hi);
      sub_qs(arr, lo, p - 1);
      sub_qs(arr, p + 1, hi)
    }
    return arr;
  }

  function partition(a, l, h) {
    var pivot = a[h];
    var i = l;
    for (var j = l; j < h; j++) { // << need to be  j < h not h - 1
      if (a[j] < pivot) {
        var temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
      }
    }
    // this swap should be outside the above for loop <---
    var temp_1 = a[i];
    a[i] = a[h];
    a[h] = temp_1;

    return i;
  }
  /***** Lomuto Algorithm Scheme *****/

  // change code above this line
  return array;
}

let array1 = [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
let array2 = [11, 8, 14, 3, 6, 2, 7]
console.log(quickSort(array1).join(','))
console.log(quickSort(array2).join(','))