Swift：マージソートでのスワップの計算

Question

マージソートのスワップをカウントしようとしています。それは非常に単純な命題のように思えましたが、私の論理に問題があるようです。ここで

が、私は私のカウントをインクリメントしようとしている私のコードの関連部分です：

unsortedArray = [2, 1, 3, 1, 2] 
sortedArray = [1, 1, 2, 2, 3] 
swapCount = 5 

：

while leftIndex < leftPile.count && rightIndex < rightPile.count { 
     if leftPile[leftIndex] < rightPile[rightIndex] { 
      // nothing swapped here 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } else if leftPile[leftIndex] > rightPile[rightIndex] { 
      orderedPile.append(rightPile[rightIndex]) 
      // item taken from right pile == swapped -> increment swapCount 
      swapCount += 1 
      rightIndex += 1 
     } else { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
      // item taken from left pile == swapped -> increment swapCount 
      swapCount += 1 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
     } 
    } 

が何らかの理由で、私は次の配列を持つ5つのスワップを数えていますここに私の完全なクラスです：

class MergeSortWithCounter { 

    var swapCount: Int64 

    init() { 
     swapCount = 0 
    } 

    func mergeSort<T: Comparable>(_ array: [T]) -> [T] { 
     guard array.count > 1 else { return array } 
     let middleIndex = array.count/2 
     let leftArray = mergeSort(Array(array[0..<middleIndex])) 
     let rightArray = mergeSort(Array(array[middleIndex..<array.count])) 
     return merge(leftPile: leftArray, rightPile: rightArray) 
    } 

    func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] { 

     var leftIndex = 0 
     var rightIndex = 0 
     var orderedPile = [T]() 
     if orderedPile.capacity < leftPile.count + rightPile.count { 
      orderedPile.reserveCapacity(leftPile.count + rightPile.count) 
     } 

     while leftIndex < leftPile.count && rightIndex < rightPile.count { 
      if leftPile[leftIndex] < rightPile[rightIndex] { 
       // nothing swapped here 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
      } else if leftPile[leftIndex] > rightPile[rightIndex] { 
       orderedPile.append(rightPile[rightIndex]) 
       // item taken from right pile == swapped -> increment swapCount 
       swapCount += 1 
       rightIndex += 1 
      } else { 
       orderedPile.append(leftPile[leftIndex]) 
       leftIndex += 1 
       // item taken from left pile == swapped -> increment swapCount 
       swapCount += 1 
       orderedPile.append(rightPile[rightIndex]) 
       rightIndex += 1 
      } 
     } 

     while leftIndex < leftPile.count { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } 

     while rightIndex < rightPile.count { 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
     } 

     return orderedPile 
    } 
} 

私はスーパーシンプルな何かが欠けている知っているが、私はより多くの時間股関節を費やしてきましたn私は自分の過ちがどこにあるかを認識しています。

ありがとうございます！

Answer 1

あなたが持っていないときは、等しい場合にスワップしている：5が間違っていると思いますなぜあなたは

 if leftPile[leftIndex] <= rightPile[rightIndex] { 
      // nothing swapped here