我的Quicksort实现在降序情况下失败

My Quicksort implementation fails for descending numbers case

本文关键字：情况下 失败 降序 Quicksort 实现 我的      更新时间：2023-09-26

我正在为快速排序代码编写代码。

代码如下，

function quickSort(inputArray){
  var pivotIndex = undefined;
  var low_Index = undefined;
  var high_Index = undefined;
  pivotIndex = inputArray.length - 1;
  low_Index = 0;
  high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;
  partition(pivotIndex,low_Index,high_Index);
  function partition(pivot_Index,low_Index,high_Index){
    var hasSwapped = false
    var temp = 0;
    for(var low = low_Index; low < pivot_Index; low++){
        if(inputArray[low] > inputArray[pivot_Index]){
            hasSwapped = true;
            temp = inputArray[low];
            inputArray[low] = inputArray[high_Index];
            inputArray[high_Index] = inputArray[pivot_Index];
            inputArray[pivot_Index] = temp;
            pivot_Index = high_Index;
            high_Index--;
            low--;              
        }
    }

    //console.log("PIVOT_INDEX "+inputArray[pivot_Index]);
    if(pivot_Index < inputArray.length - 1){
        if((pivot_Index + 1) < inputArray.length - 1){
            partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);   
        }
        if((pivot_Index - 2) >= 1){
            partition((pivot_Index - 1),0,(pivot_Index - 2));   
        }

      }

  }

  return inputArray;
}

以上代码运行于以下输入

console.log(quickSort([3,7,8,5,2,1,9,5,4]));
console.log(quickSort([4,7,3,15,2,1]));
console.log(quickSort([4,7,3]));
console.log(quickSort([7,3]));

输出是

rahul@rahul:~/myPractise/Algo$ node sorting.js 
[ 1, 2, 3, 4, 5, 5, 7, 8, 9 ]
[ 1, 2, 3, 4, 7, 15 ]
[ 3, 4, 7 ]
[ 3, 7 ]

但在所有数字都按降序排列的情况下，以下输入失败

console.log(quickSort([15,12,10,7,4,1]));
rahul@rahul:~/myPractise/Algo$ node sorting.js 
[ 1, 12, 10, 7, 4, 15 ]
rahul@rahul:~/myPractise/Algo$

我认为原因是我的枢轴索引指向15是最大值，因此不会被替换。

我如何对代码进行更改，以使上述输入的算法正常工作？

注意：我从维基百科中的图表中得到了快速排序的解释

大家好，

我通过添加代码解决了上述问题

    if(inputArray[low_Index] > inputArray[high_Index]){
        temp = inputArray[low_Index];
        inputArray[low_Index] = inputArray[high_Index];
        inputArray[high_Index] = temp;      
        pivot_Index = high_Index;           
    }

刚好低于for循环，高于函数"分区"内的if条件

所以现在我的代码看起来像这个

function quickSort(inputArray){
    var pivotIndex = undefined;
    var low_Index = undefined;
    var high_Index = undefined;
    pivotIndex = inputArray.length - 1;
    low_Index = 0;
    high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;
    partition(pivotIndex,low_Index,high_Index);
    function partition(pivot_Index,low_Index,high_Index){       
       var temp = 0;
       console.log("'nPivot Number : "+inputArray[pivot_Index]);
       console.log("input Array : "+inputArray);
       console.log("partitioned array : "+inputArray.slice(low_Index,pivot_Index+1));
       for(var low = low_Index; low < pivot_Index; low++){
        if(inputArray[low] > inputArray[pivot_Index]){
            temp = inputArray[low];
            inputArray[low] = inputArray[high_Index];
            inputArray[high_Index] = inputArray[pivot_Index];
            inputArray[pivot_Index] = temp;
            pivot_Index = high_Index;
            high_Index--;
            low--;              
        }
      }
      // added if condition, which solves my problem
      if(inputArray[low_Index] > inputArray[high_Index]){
        temp = inputArray[low_Index];
        inputArray[low_Index] = inputArray[high_Index];
        inputArray[high_Index] = temp;      
        pivot_Index = high_Index;           
      }


      if(pivot_Index < inputArray.length - 1){
        if((pivot_Index + 1) < inputArray.length - 1){
            partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);   
        }
        if((pivot_Index - 2) >= 1){
            partition((pivot_Index - 1),0,(pivot_Index - 2));   
        }

      }

    }//partition

    return inputArray;
}

运行以上代码输入后

console.log(quickSort([15,12,10,7,4,1]));

输出如下，

rahul@rahul:~/myPractise/Algo$ node sorting.js 
Pivot Number : 1
input Array : 15,12,10,7,4,1
partitioned array : 15,12,10,7,4,1
Pivot Number : 15
input Array : 1,12,10,7,4,15
partitioned array : 12,10,7,4,15
Pivot Number : 7
input Array : 1,4,10,7,12,15
partitioned array : 1,4,10,7
Pivot Number : 15
input Array : 1,4,7,10,12,15
partitioned array : 10,12,15
[ 1, 4, 7, 10, 12, 15 ]
rahul@rahul:~/myPractise/Algo$

代码工作正常。

当数据轴是数组的最大数时，partition函数不工作（[2,1,3]将不会排序…）。事实上，这种情况永远不会成立：

if(inputArray[low] > inputArray[pivot_Index]){

因此，pivot_Index永远不会改变，因此最后一个条件将始终为假：

if(pivot_Index < inputArray.length - 1){

除了用错误的参数递归调用partition函数之外：

partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);

实际上，您总是取整个数组的最后一个元素（(inputArray.length - 2），而不是子数组。所以你可能会得到这样的东西：

                  [A,B,C,D,E,F]
        [A,B,C,D]              [E,F]
    [A,B]    **[C,D,E,F]** WRONG

您应该简化代码。从这样的东西开始：

function quicksort(array, lo, hi){
    if (lo < hi){ 
        indicePivot  := partition(array, lo, hi) // partition your array [values < pivot ... , pivot, values > pivot ...]
        // Divide and conquer: recursively call quicksort on sub arrays [values < pivot] and [values > pivot]
        quicksort(array, lo, indicePivot – 1) 
        quicksort(array, indicePivot + 1, hi)
    }
}

你的分区函数：

function partition(array, lo, hi){
   indicePivot = hi;
   // do the magic to have [values < pivot ..., pivot, values > pivot]
   // ...
   return indicePivot;
}
相关文章：