• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?