SHARE
TWEET

Untitled

a guest Oct 16th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // First write the swap function, which is just a helper function to swap values of the array.
  2. function swap(array, i, j) {
  3.     var temp = array[i];
  4.     array[i] = array[j];
  5.     array[j] = temp;
  6. }
  7.  
  8. function quicksortLomuto(array, left, right) {
  9.     // left-pointer would be the index of the first element which is 0 and right-pointer would be the index of the last element which would be (length -1).
  10.     left = left || 0;
  11.     right = right || array.length - 1;
  12.  
  13.     var pivot = partitionLomuto(array, left, right);
  14.  
  15.     if (left < pivot - 1) {
  16.         quicksortLomuto(array, left, pivot - 1);
  17.     }
  18.  
  19.     if (right > pivot) {
  20.         quicksortLomuto(array, pivot - 1, right)
  21.     }
  22.  
  23.     return array;
  24. }
  25.  
  26. function partitionLomuto(array, left, right) {
  27.     // Lomuto algorithm always uses the last element, array[right], for the pivot.
  28.     var pivot = right;
  29.     var i = left;
  30.  
  31.     /*The logic under Lomuto is, we start from the leftmost element and keep track of index of smaller (or equal to) elements as j. While traversing, if we find a smaller element, we swap current element with arr[j]. Otherwise we ignore current element.*/
  32.     for (var j = left; j < right; j++) {
  33.         if (array[j] <= array[pivot]) {
  34.             swap(array, i, j);
  35.             i++
  36.         }
  37.     }
  38.     swap(array, i, j);
  39.     return i;
  40. }
  41.  
  42. /******************* Testing Lomuto algorithm *********************/
  43.  
  44. function getRandomInt(min, max) {
  45.     return Math.floor(Math.random() * (max - min + 1)) + min;
  46.     // By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1
  47. }
  48.  
  49. var arr = [];
  50.  
  51. for (var i = 0; i < 5; i++) { //initialize a random integer unsorted array
  52.     arr.push(getRandomInt(1, 100));
  53. }
  54.  
  55. console.log("Unsorted array: ");
  56. console.log(arr); //printing unsorted array
  57.  
  58. arr = quicksortLomuto(arr, 0, arr.length - 1);
  59. console.log("Sorted array: ");
  60. console.log(arr);
  61.  
  62. /* Output:
  63. Unsorted array:
  64. [ 83, 52, 89, 42, 6, 87, 50, 17, 34, 96 ]
  65. Sorted array:
  66. [ 6, 17, 34, 42, 50, 52, 83, 87, 89, 96 ]
  67. [Finished in 0.1s] */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top