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

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

0 голосов
/ 23 декабря 2018

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

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

Ответы [ 3 ]

0 голосов
/ 23 декабря 2018

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

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 было много скрытых изменений, направленных на повышение эффективности (фон: манифест владения *)1015 *).В Swift 5 сеттер (например, мутирующий индекс) может быть смоделирован как сопрограмма, которая позволяет выполнять операции такого типа на месте.Но я не уверен на 100%, будет ли это так в Swift 5.0.

0 голосов
/ 23 декабря 2018

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

// 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]

Оригинальная быстрая сортировкабыстрый алгоритм источник

0 голосов
/ 23 декабря 2018

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

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]

Разве это не была намеченная цель?

...