Algorithm_Sort

Algorithm_Sort#

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

QuickSort#

Implementation logic:
Take the value at the specified position index, compare it with the numbers before the index, and if the number before is greater than the number after, swap the positions.

For example:


[ 8 3 5 1 4 2 ]

Starting from index 1, the current element is 3, and the previous element is 8. Since 8 > 3, swap the positions. The array is still [ 3 8 5 1 4 2 ].
Then, at index 2, the current element is 5, and the previous element is 8. Since 8 > 5, swap the positions. The array is [ 3 5 8 1 4 2 ].
Then, at index 3, the current element is 1, and the previous element is 8. Since 8 > 1, swap the positions. The array is [ 3 5 1 8 4 2 ]. Since 5 > 1, swap the positions. The array is [ 3 1 5 8 4 2 ]. Since 3 > 1, swap the positions. The array is [ 1 3 5 8 4 2 ].
Then, at index 4, the current element is 4, and the previous element is 8. Since 8 > 4, swap the positions. The array is [ 1 3 5 4 8 2 ]. Since 5 > 4, swap the positions. The array is [ 1 3 4 5 8 2 ].
Then, at index 5, the current element is 2, and the previous element is 8. Since 8 > 2, swap the positions. The array is [ 1 3 4 5 2 8 ]. Since 5 > 2, swap the positions. The array is [ 1 3 4 2 5 8 ]. Since 4 > 2, swap the positions. The array is [ 1 3 2 4 5 8 ]. Since 3 > 2, swap the positions. The array is [ 1 2 3 4 5 8 ]. Since 1 < 2, stop.

The code is as follows:


class Solution {
    func sortedSquares(_ nums: [Int]) -> [Int] {
        // first, get the squareList
        var squareNums = nums.map({ $0 * $0 })
        for j in 0..<squareNums.count {
            let key = squareNums[j]
            var i = j - 1
            while (i >= 0 && squareNums[i] > key) {
                squareNums[i+1] = squareNums[i]
                i = i - 1
            }
            squareNums[i+1] = key
        }
        return squareNums
    }
}

Selection Sort#

Implementation logic:
Traverse the array to find the smallest value and place it at the index 0 of the result array.
Traverse the array to find the second smallest value and place it at the index 1 of the result array.
...

The code is as follows:


class Solution {
    func sortedSquares(_ nums: [Int]) -> [Int] {
        // first, get the squareList
        var squareNums = nums.map({ $0 * $0 })
        
        // selectionSort
        let count = squareNums.count
        for i in 0..<(count-1) {
            var j_min = i
            var j = i+1

            // Traverse to find the index of the smallest element starting from i
            while (j < count) {
                if squareNums[j] < squareNums[j_min] {
                    j_min = j
                } 
                j = j + 1
            }
            
            // If i and the index of the smallest element are not equal, swap the elements at the two positions
            if i != j_min {
                squareNums.swapAt(i, j_min)
            }
        }
        return squareNums
    }
}

Bubble Sort#

Logic:
Iterate through adjacent elements, if the previous element is larger, swap positions; then continue to compare the next elements;
Repeat the above steps
Repeat the above steps
...
Until there are no elements that can be swapped.

For example:


[2, 1, 6, 4, 7, 5]

First iteration:
index = 1; current element is 2, previous element is 1, 2 < 1, swap positions, [1, 2, 6, 4, 7, 5]
index = 2; current element is 6, previous element is 2, 6 > 2, no need to swap positions
index = 3; current element is 4, previous element is 6, 4 < 6, swap positions, [1, 2, 4, 6, 7, 5]
index = 4; current element is 7, previous element is 6, 7 > 6, no need to swap positions
index = 5; current element is 5, previous element is 7, 5 < 7, swap positions, [1, 2, 4, 5, 6, 7]
There are swaps in the middle

Second iteration:
index = 1; current element is 2, previous element is 1, 2 > 1, no need to swap positions, [1, 2, 4, 5, 6, 7]
index = 2; current element is 4, previous element is 2, 4 > 2, no need to swap positions
index = 3; current element is 6, previous element is 4, 6 > 4, no need to swap positions
index = 4; current element is 5, previous element is 6, 5 < 6, swap positions, [1, 2, 4, 5, 6, 7]
index = 5; current element is 7, previous element is 6, 7 > 6, no need to swap positions
There are swaps in the middle

Third iteration:
index = 1; current element is 2, previous element is 1, 2 > 1, no need to swap positions, [1, 2, 4, 5, 6, 7]
index = 2; current element is 4, previous element is 2, 4 > 2, no need to swap positions
index = 3; current element is 6, previous element is 4, 6 > 4, no need to swap positions
index = 4; current element is 6, previous element is 5, 6 > 5, no need to swap positions
index = 5; current element is 7, previous element is 6, 7 > 6, no need to swap positions
No swaps in this iteration, the traversal is complete

The code is as follows:


class Solution {
    func sortedSquares(_ nums: [Int]) -> [Int] {
        // first, get the squareList
        var squareNums = nums.map({ $0 * $0 })
        
        // bubble sort
        var sorted = false;
        while (!sorted) {
            sorted = true
            for i in 1..<(squareNums.count) {
                if (squareNums[i] < squareNums[i-1]) {
                    squareNums.swapAt(i, i-1)
                    sorted = false
                }
            }
        }
        return squareNums
    }
}

Merge Sort#

Implementation logic:
Split the array into two halves, then continue to split the two halves of the array until the number of elements in the array is 1, then compare and return the sorted last split smallest array, then sort and concatenate concatenate concatenate.

The diagram is as follows:

merge sort demo

The code is as follows:


class Solution {
    func merge(_ left: [Int], _ right: [Int]) -> [Int] {
        // Define a new array to store the sorted result
        var result: [Int] = []

        // Make the input parameters mutable
        var mutLeft = left
        var mutRight = right

        // Iterate and sort
        while mutLeft.count > 0 && mutRight.count > 0 {
            // Sort
            // If the left element is smaller, remove the first element from the left array and add it to the result array; otherwise, remove the first element from the right array and add it to the result array.
            result.append(mutLeft[0] < mutRight[0] ? mutLeft.removeFirst() : mutRight.removeFirst())
        }
        // Concatenate the non-empty array
        result += (mutLeft.count > 0 ? mutLeft : mutRight)
        // Return
        return result
    }
    
    func mergeSort(_ nums: [Int]) -> [Int] {
        // If the number of array elements is less than 2, no need to split further, return the array
        if nums.count < 2 {
            return nums
        }
        
        // Split the array in half
        let middle = nums.count / 2
        
        // Take the first half from 0 to middle, excluding middle, and continue to split
        let leftSlice = nums[0..<middle]
        // Then continue to split
        let subLeft = mergeSort(Array(leftSlice))
        
        // Take the second half from middle to the end
        let rightSlice = nums[middle..<nums.count]
        // Continue to split
        let subRight = mergeSort(Array(rightSlice))

        // After splitting to the smallest unit, sort, merge, and return
        return merge(subLeft, subRight)
    }
    
    func sortedSquares(_ nums: [Int]) -> [Int] {
        // first, get the squareList
        var squareNums = nums.map({ $0 * $0 })
        
        // merge sort
        return mergeSort(squareNums)
    }
}

Algorithm_Sort#

QuickSort#

Selection Sort#

Bubble Sort#

Merge Sort#

Reference#