Swift: подсчет свопов в сортировке слияния

Question

Я пытаюсь подсчитать свопы в сортировке слияния. Это казалось очень простым предложением, но, похоже, проблема с моей логикой.

Вот соответствующая часть моего кода, где я пытаюсь, чтобы увеличить свой счет:

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 свопов со следующим массивом:

unsortedArray = [2, 1, 3, 1, 2] 
sortedArray = [1, 1, 2, 2, 3] 
swapCount = 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

Вы обменивать в равном случае, когда вы не должны:

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

Вы имели в виду

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