merge_sort/MergeSort.kt - master - uizadcz/Algorithm

merge_sort/MergeSort.kt
213 строк6 KB
ursa
MergeSort.kt
10 окт 2024, 16:31
10 окт 2024, 16:31dca208d
/**
 * https://leetcode.com/problems/sort-an-array/description/
 * 912. Sort an Array
 *
 *
 * Given an array of integers nums, sort the array in ascending order and return it.
 *
 * You must solve the problem without using any built-in functions in O(nlog(n)) time complexity
 * and with the smallest space complexity possible.
 *
 *
 *
 * Example 1:
 *
 * Input: nums = [5,2,3,1]
 * Output: [1,2,3,5]
 * Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3),
 * while the positions of other numbers are changed (for example, 1 and 5).
 *
 * Example 2:
 *
 * Input: nums = [5,1,1,2,0,0]
 * Output: [0,0,1,1,2,5]
 * Explanation: Note that the values of nums are not necessairly unique.
 *
 *
 * Constraints:
 *
 * 1 <= nums.length <= 5 * 104
 * -5 * 104 <= nums[i] <= 5 * 104
 */
class MergeSortWithComments {
    fun sortArray(nums: IntArray): IntArray {
        return mergeSort(nums)
    }

    private fun mergeSort(nums: IntArray): IntArray {
        // fast return if size <= 1
        if (nums.size <= 1) {
            return nums
        }

        // calculate mid value
        val mid = nums.size / 2

        // create sub array of left half
        val leftHalf = nums.copyOfRange(0, mid)
        // create sub array of right half
        val rightHalf = nums.copyOfRange(mid, nums.size)

        // sort left & right half
        val sortedLeft = mergeSort(leftHalf)
        val sortedRight = mergeSort(rightHalf)

        // return merged arrays
        return merge(sortedLeft, sortedRight)
    }

    private fun merge(left: IntArray, right: IntArray): IntArray {
        // array of left + right sizes
        val result = IntArray(left.size + right.size)

        // intermediate pointer variables
        var i = 0
        var j = 0
        var k = 0

        // merge while halves are bigger
        while (i < left.size && j < right.size) {
            // check if left value bigger than latter
            // and set values
            if (left[i] < right[j]) {
                result[k++] = left[i++]
            } else {
                result[k++] = right[j++]
            }
        }

        // what if there's still left half left?
        // just append to the result
        while (i < left.size) {
            result[k++] = left[i++]
        }
        // same here, the right side might still be holding values
        while (j < right.size) {
            result[k++] = right[j++]
        }

        // return merged halves
        return result
    }
}

class MergeSortArrayCopy {
    fun sortArray(nums: IntArray): IntArray {
        if (nums.size < 2) {
            return nums
        }

        var arrayA = IntArray(nums.size / 2)
        System.arraycopy(nums, 0, arrayA, 0, nums.size / 2)

        var arrayB = IntArray(nums.size - nums.size / 2)
        System.arraycopy(nums, nums.size / 2, arrayB, 0, nums.size - nums.size / 2)

        arrayA = sortArray(arrayA)
        arrayB = sortArray(arrayB)

        return mergeArray(arrayA, arrayB)
    }

    private fun mergeArray(arrayA: IntArray, arrayB: IntArray): IntArray {
        val arrayC = IntArray(arrayA.size + arrayB.size)
        var positionA = 0
        var positionB = 0

        for (i in arrayC.indices) {
            when {
                positionA == arrayA.size -> {
                    arrayC[i] = arrayB[positionB];
                    positionB++
                }

                positionB == arrayB.size -> {
                    arrayC[i] = arrayA[positionA];
                    positionA++
                }

                arrayA[positionA] < arrayB[positionB] -> {
                    arrayC[i] = arrayA[positionA];
                    positionA++
                }

                else -> {
                    arrayC[i] = arrayB[positionB];
                    positionB++
                }
            }
        }

        return arrayC
    }
}

class MergeSortTakeDrop {
    fun sortArray(nums: IntArray): IntArray {
        if (nums.size <= 1) return nums

        val dividedArray = divide(nums)
        return sort(dividedArray.first, dividedArray.second)
    }

    private fun sort(firstArray: IntArray, secondArray: IntArray): IntArray {
        if (firstArray.isEmpty()) return secondArray

        if (secondArray.isEmpty()) return firstArray

        if (firstArray.size == 1 && secondArray.size == 1) {
            val firstValue = firstArray[0]
            val secondValue = secondArray[0]
            return when {
                firstValue < secondValue -> intArrayOf(firstValue, secondValue)
                secondValue < firstValue -> intArrayOf(secondValue, firstValue)
                else -> intArrayOf(firstValue, secondValue)
            }
        }

        val dividedLeftArray = divide(firstArray)
        val sortedLeftArray = sort(dividedLeftArray.first, dividedLeftArray.second).toMutableList()

        val dividedRightArray = divide(firstArray)
        val sortedRightArray = sort(dividedRightArray.first, dividedRightArray.second).toMutableList()

        val resultSortedArray = mutableListOf<Int>()

        while (sortedLeftArray.isNotEmpty() && sortedRightArray.isNotEmpty()) {
            if (sortedLeftArray.isEmpty()) {
                resultSortedArray.addAll(sortedRightArray)
                sortedRightArray.clear()
            }
            if (sortedRightArray.isEmpty()) {
                resultSortedArray.addAll(sortedLeftArray)
                sortedLeftArray.clear()
            }

            val firstValue = sortedLeftArray.removeFirst()
            val secondValue = sortedRightArray.removeFirst()

            when {
                firstValue < secondValue -> {
                    resultSortedArray.add(firstValue)
                }

                secondValue < firstValue -> {
                    resultSortedArray.add(secondValue)
                }

                else -> {
                    resultSortedArray.add(firstValue)
                }
            }
        }

        return resultSortedArray.toIntArray()
    }

    private fun divide(array: IntArray): Pair<IntArray, IntArray> {
        val size = array.size
        if (size <= 1) throw IllegalArgumentException()
        val firstSize = size / 2
        return array.take(firstSize).toIntArray() to array.drop(firstSize).toIntArray()
    }
}