了解排序平方算法

Question

我目前很难理解排序平方算法的以下逻辑。我列出了有问题的代码。有人可以帮我分解一下以下算法的逻辑吗？

func sortedSquareAlgorithm(_ array: [Int]) -> [Int] {
    //Initilizing Empty Array.
    //?? variable sortedSquares initilizing empty tupil ??
    var sortedSquares = Array(repeating: 0, count: array.count)
    //Pointers are initilized for left and right side of array
    var smallerValueIdx = 0
    var largeValueIdx = array.count - 1
    // stride method is initilized
    //?? what is this line codes purpose? ??
    for idx in stride(from: array.count - 1, through: 0, by: -1) {
        //constant variale is declared for each pointer
        let smallerValue = array[smallerValueIdx]
        let largerValue = array[largeValueIdx]
        
        //?? what is abs in this line code ??
        if abs(smallerValue) > abs(largerValue) {
            sortedSquares[idx] = smallerValue * smallerValue
            smallerValueIdx += 1
        } else {
            sortedSquares[idx] = largerValue * largerValue
            largeValueIdx -= 1
        }
    }
    return sortedSquares
}

Answer 1

我已经为代码的每一行添加了注释。

func sortedSquareAlgorithm(_ array: [Int]) -> [Int] {
    
    /* Initialising an empty array.
       Array size is equal to the size of the input array.
       Array contains value 0 in all the places.
     */
    
    var sortedSquares = Array(repeating: 0, count: array.count)
    
    // pointer for the first element of the array.
    var smallerValueIdx = 0
    
    //pointer for the last element of the array
    var largeValueIdx = array.count - 1

    // stride returns a sequence from a starting value toward, and possibly including, an end value, stepping by the specified amount.
    for idx in stride(from: array.count - 1, through: 0, by: -1) {
        //assign the first element of the input array to smallerValue
        let smallerValue = array[smallerValueIdx]
        
        //assign the last element of the input array to smallerValue
        let largerValue = array[largeValueIdx]
        
        //abs -> returns the absolute value of the given number.
        /* Square values of all positive and negative numbers are positive.
            So you have to compare the absolute number of each element to decide which has the larger square value.
         */
        if abs(smallerValue) > abs(largerValue) {
            //if the smallerValue is largest among two the squre of that will be added to the end of the unsorted array.
            //smallerValue * smallerValue gives the square value of that smallerValue
            sortedSquares[idx] = smallerValue * smallerValue
            smallerValueIdx += 1
        } else {
            //if the smallerValue is smallest among two the squre of that will be added to the beginning of the unsorted array.
            sortedSquares[idx] = largerValue * largerValue
            largeValueIdx -= 1
        }
    }

    return sortedSquares
}

以下解释了如果数组 [3, -1, 5] 作为输入

算法将如何工作

sortedSquareAlgorithm([3,-1,5])

/*
 input_array = [3, -1, 5]

 sortedSquares = [0,0,0]
 
 smallerValueIdx = 0
 largeValueIdx = 2
 
 idx will return the sequence [2,1,0]
 
 inside for loop
 
    iteration 1 ---> idx = 2
 
        smallerValue = array[0] = 3
        largerValue = array[2] = 5
 
        abs(3) > abs(5) ---> 3 > 5 ---> false //so else part will execute
 
        sortedSquares[2] ---> 5 * 5 = 25
        largeValueIdx = 2-1 = 1
 
        // after the 1st iteration sortedSquares = [0,0,25]
 
     iteration 2 ---> idx = 1

         smallerValue = array[0] = 3
         largerValue = array[1] = -1

         abs(3) > abs(-1) ---> 3 > 1 ---> true //so if part will execute

         sortedSquares[1] ---> 3 * 3 = 9
         smallerValue = 0+1 = 1

         // after the 2nd iteration sortedSquares = [0,9,25]

     iteration 3 ---> idx = 0

         smallerValue = array[1] = -1
         largerValue = array[1] = -1

         abs(-1) > abs(-1) ---> 1 > 1 ---> false //so else part will execute

         sortedSquares[0] ---> -1 * -1 = 1
         largeValueIdx = 1-1 = 0

         // after the 3rd iteration sortedSquares = [1,9,25]


 end of for loop
 
 returns sortedSquares = [1,9,25]
 */

更新

您还可以使用以下代码获取所需的输出。

let array = [-1,2,5,3,-2]
let squaredArray = array.map({ number in number * number }).sorted()
print(squaredArray)

我没有比较这两种代码的性能。但是这个对我来说看起来更简单。

了解排序平方算法

Understanding Sorted Square Algorithm

algorithm

data-structures

swift