Вопрос о рекурсивном состоянии в быстрой сортировке - PullRequest
1 голос
/ 02 апреля 2020

Repl ниже:

https://repl.it/@Stylebender / quickSort

    // quickSort Conceptual

    // Select pivot from the middle of the array

    //All items to the left of the pivot should be smaller and vice versa

    // At this point the pivot will be consider to be sorted and in its proper position

    // Note: The values to the left and right of the pivot still remain UNSORTED, which is why this procedure needs to be called recursively for both partitions until there are no longer enough values to pick a pivot from

    // [24, 10, 17, 12, 5, 23, 300]

    function quickSortHelper(array, left, right) {
      var i = left; 
      var j = right;
      var pivot = array[Math.round((left + right) * .5)];
      // console.log(right);
      console.log('Pivot',pivot);

      // Loop
      while (i <= j) { //j must always be greater than or equal to i

        while (array[i] < pivot) {//Left of pivot: Is leftward value smaller than pivot? If so, increment.
          i++;
        }

        while (array[j] > pivot) {//Right of pivot: Is the rightward value greater than pivot? If so, decrement.
          j--;
        }

     //Swap Values 

        if (i <= j) { 
          var temp = array[i];
          array[i] = array[j];
          array[j] = temp;
          i++;
          j--;
        }

     // Initiate outer while loop until all items left of pivot are smaller and vice versa
      }

      console.log(array);

      // Resursively invoke function on the unsorted L and R partitions remaining in the array.
// line 47:
      if (left < j) {
        quickSortHelper(array, left, j);
      }

// line 51:
      if (i < right) {
        quickSortHelper(array, i, right);
      }


      return array;
    }

    function quickSort(input) {
        return quickSortHelper(input, 0, input.length - 1);
    }


    quickSort([24, 10, 17, 12, 5, 23, 300]);

Я обычно понимаю последовательность и логику c реализации позади quickSort, но может кто-то Объясните обоснование операторов IF в строках 47 и 51?

Я просто немного запутался, как эти условия IF используются для определения необходимости рекурсивного вызова функции quickSort.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...