Как мне добиться сортировки на месте для поддиапазона элементов в массиве<T> в swift?

Question

Стандартные методы сортировки для типа Array не имеют варианта, в котором область сортируемого массива может быть сужена. Использование ArraySlice не приводит к сортировке исходных данных из-за семантики копирования при записи.

Должен ли я написать новую реализацию сортировки для достижения сортировки на месте в поддиапазоне массива? Или есть уродливый способ создать второй массив, который псевдоним желаемого диапазона элементов из исходного массива?

Answer 1

Подстрочная операция, которая принимает диапазон, возвращает изменяемое значение. Если вы напрямую вызываете мутирующий метод, он будет мутировать исходный массив на месте:

var numbers = [3,5,2,4,1]
numbers[1..<4].sort()
print(numbers) // [3, 2, 4, 5, 1]

Что касается Swift 4.2, я думаю, что это не более эффективно, чем сделать временную копию среза (Источник: сообщение на форуме 1, сообщение на форуме 2. В этих сообщениях рассказывается обо всех видах операций срезов, в том числе тех, которые изменяют длину источника сбор, но он должен быть таким же для сортировки на месте.)

В предстоящем выпуске Swift 5 было много скрытых изменений, направленных на то, чтобы сделать это более эффективным (история вопроса: манифест владения). В Swift 5 сеттер (например, мутирующий индекс) может быть смоделирован как сопрограмма, которая позволяет выполнять операции такого типа на месте. Но я не уверен на 100%, будет ли это так в Swift 5.0.

Answer 2

Трудно понять, что вы думаете, в чем проблема:

var arr = [9,8,7,6,5,4,3,2,1]
let range = 4...7
arr.replaceSubrange(range, with: arr[range].sorted())
print(arr) // [9, 8, 7, 6, 2, 3, 4, 5, 1]

Не было ли это намеченной целью?

Answer 3

Я бы предложил использовать пользовательскую реализацию быстрой сортировки:

// MARK: - Array<Element: Comparable>

extension Array where Element: Comparable {

    // MARK: - Internal

    mutating func quickSort(subrange: Range<Int>) {
        privateQuickSort(left: subrange.lowerBound, right: subrange.upperBound - 1)
    }

    // MARK: - Private

    mutating private func partition(left: Int, right: Int) -> Int {
        var i = left
        for j in (left + 1)..<(right + 1) {
            if self[j] < self[left] {
                i += 1
                (self[i], self[j]) = (self[j], self[i])
            }
        }
        (self[i], self[left]) = (self[left], self[i])
        return i
    }
    mutating private func privateQuickSort(left: Int, right: Int) {
        if right > left {
            let pivotIndex = partition(left: left, right: right)
            privateQuickSort(left: left, right: pivotIndex - 1)
            privateQuickSort(left: pivotIndex + 1, right: right)
        }
    }
}

var array = [10,0,2,1,4,5,6,7,8,3]

array.quickSort(subrange: 0..<array.count)
print(array)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]

Но для

var array = [10,0,2,1,4,5,6,7,8,3]

array.quickSort(subrange: 0..<2)

[0, 10, 2, 1, 4, 5, 6, 7, 8, 3]

Исходный алгоритм быстрого быстродействия