refactor(sorts): quicksort

Gapur · Gapur · commit 63cc8a988ebd · 2020-01-24T21:54:24.000+06:00
diff --git a/algorithms/sorts/quicksort.js b/algorithms/sorts/quicksort.js
@@ -1,40 +1,29 @@
-const swap = (arr, i, j) => {
-  const temp = arr[i];
-  arr[i] = arr[j];
-  arr[j] = temp;
-};
-
-const partition = (array, left, right) => {
-  const pivot = array[Math.floor((right + left) / 2)];
-  let i = left;
-  let j = right;
-  while (i <= j) {
-    while (array[i] < pivot) {
-      i++;
-    }
-    while (array[j] > pivot) {
-      j--;
-    }
-    if (i <= j) {
-      swap(array, i, j);
-      i++;
-      j--;
-    }
+const QuickSort = (array) => {
+  if (array.length <= 1) {
+    return array;
   }
-  return i;
-};
 
-const sort = (array, left, right) => {
-  if (array.length > 1) {
-    const index = partition(array, left, right);
-    if (left < index - 1) {
-      sort(array, left, index - 1);
-    }
-    if (index < right) {
-      sort(array, index, right);
+  const leftArray = [];
+  const rightArray = [];
+
+  const pivotElement = array.shift();
+  const centerArray = [pivotElement];
+
+  while (array.length) {
+    const currentElement = array.shift();
+    if (currentElement === pivotElement) {
+      centerArray.push(currentElement);
+    } else if (currentElement < pivotElement) {
+      leftArray.push(currentElement);
+    } else {
+      rightArray.push(currentElement);
     }
   }
-  return array;
+
+  const leftArraySorted = QuickSort(leftArray);
+  const rightArraySorted = QuickSort(rightArray);
+
+  return leftArraySorted.concat(centerArray, rightArraySorted);
 };
 
-module.exports = sort;
+module.exports = QuickSort;
