如何计算合并排序中的比较数？

This is my algorithm. I've tried placing numCompares and numMoves in many different locations, but I'm not able to get it where I can see valid results. Compare = 2 integers being evaluated by one another move = an element has been moved from its position. So a swap would be 2 moves.

这是我的算法。我已经尝试将numCompares和numMoves放在许多不同的位置,但是我无法在可以看到有效结果的地方找到它。比较= 2彼此评估的整数move =元素已从其位置移动。因此交换将是2个动作。

 /**
   * Internal method that merges two sorted halves of a subarray.
   * @param a an array of Comparable items.
   * @param tmpArray an array to place the merged result.
   * @param leftPos the left-most index of the subarray.
   * @param rightPos the index of the start of the second half.
   * @param rightEnd the right-most index of the subarray.
   */
  private static void merge( int[] a, int[ ] tmpArray, int leftPos, int rightPos, int rightEnd )
  {
      int leftEnd = rightPos - 1; //left's last position
      int tmpPos = leftPos; //left-most
      int numElements = rightEnd - leftPos + 1;

      // Main loop
      while( leftPos <= leftEnd && rightPos <= rightEnd ){ //left and right pointers don't meet limit
        //numCompares = numCompares+1; //+2 because of 2 conditions
          if(a[leftPos] <= a[rightPos]){ //if left half element <= right half element
              tmpArray[ tmpPos++ ] = a[ leftPos++ ]; //copy left side elements
            }else{
              tmpArray[ tmpPos++ ] = a[ rightPos++ ]; //copy right side elements
        }
        numMoves++;
        numCompares = numCompares+2;
      }
      while( leftPos <= leftEnd ){    // Copy rest of first half while left is <= left end
          tmpArray[ tmpPos++ ] = a[ leftPos++ ];
          numCompares++;
          numMoves++;
      }
      while( rightPos <= rightEnd ){  // Copy rest of right half while right is < right-most
          tmpArray[ tmpPos++ ] = a[ rightPos++ ];
          numCompares++;
          numMoves++;
      }
      // Copy tmpArray back
      for( int i = 0; i < numElements; i++, rightEnd-- ){
          a[ rightEnd ] = tmpArray[ rightEnd ];
      }
  }

1 个解决方案

#1

This would be my approach given that you want max precision:

鉴于您需要最大精度,这将是我的方法:

/**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge( int[] a, int[ ] tmpArray, int leftPos, int rightPos, int rightEnd )
    {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        while( leftPos <= leftEnd){
            numCompares++; // this is for leftPos <= leftEnd
            if(rightPos <= rightEnd) {
                numCompares++; // this is for rightPos <= rightEnd
                if (a[leftPos] <= a[rightPos]) { //if left half element <= right half element
                    tmpArray[tmpPos++] = a[leftPos++]; //copy left side elements
                } else {
                    tmpArray[tmpPos++] = a[rightPos++]; //copy right side elements
                }
                numMoves++;
                numCompares++; // this is for a[leftPos] <= a[rightPos]
            } else {
                break;
            }
        }
        numCompares++; //The while loop exited. This has happened because (leftPos <= leftEnd) or (rightPos <= rightEnd) failed.


        while( leftPos <= leftEnd ){    // Copy rest of first half while left is <= left end
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            numCompares++;
            numMoves++;
        }
        numCompares++; //The while loop exited. This has happened because leftPos <= leftEnd failed.

        while( rightPos <= rightEnd ){  // Copy rest of right half while right is < right-most
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
            numCompares++;
            numMoves++;
        }
        numCompares++; //The while loop exited. This has happened because rightPos <= rightEnd failed.


        // Copy tmpArray back
        // I assume that you don't want account for this operation in your measurements, since you didn't try to do it yourself?
        for( int i = 0; i < numElements; i++, rightEnd-- ){
            a[ rightEnd ] = tmpArray[ rightEnd ];
            // numCompares++; // This is for (i < numElements)
            // numMoves++;
        }
        // numCompares++; //The for loop exited. This has happened because (i < numElements) failed.
    }

If you are comparing it to the asymptotic running time, then try to increase the size gradually and graph the measurements. It's unlikely that it will fit well on small sample sizes. Also as a sidenote, this code count the amount of writes in the array. If you want to account for reads too, you would need to add two instead of one everywhere numMoves is incremented.

如果要将其与渐近运行时间进行比较,请尝试逐渐增大尺寸并绘制测量值图表。它不太可能适合小样本量。另外,作为旁注,此代码计算数组中的写入量。如果你想考虑读取,你需要添加两个而不是一个numMoves递增的地方。

Hope it helps. Good luck :)

希望能帮助到你。祝好运 :)

#1