Как я могу создать реализацию QuickSort в Swift? - PullRequest
Новая
       13

Как я могу создать реализацию QuickSort в Swift?

0 голосов
/ 05 октября 2019

Я быстро учусь, и я реализовал алгоритмы сортировки по вариусам в качестве ADT для практики. Я просто борюсь с быстрой сортировкой, которая как-то не сработает. Может кто-нибудь сказать мне, где недостаток в коде? 

func quickSort(start: Int, end: Int) {
    if (end <= start) { return }
    let pivot = self.srtdArr[end]
    var left = start
    var right = end - 1
    while left < right {
        while ((self.srtdArr[left] <= pivot) && (left < end)) {
            left += 1
        }
        while ((self.srtdArr[right] >= pivot) && (right > start)) {
            right -= 1
        }
        if left < right { self.srtdArr.swapAt(left, right) }
    }
    self.srtdArr.swapAt(left, end)
    quickSort(start: start, end: right)
    quickSort(start: right+1, end: end)
    return
}

Честно говоря, я часто менял код, чтобы больше обдумывать проблему, поэтому мне нужен свежий ввод. Во время отладки я впервые заметил, что иногда код оказывается в рекурсивном цикле. Я изменил какой-то итератор или логический оператор, и теперь он определяет, но не правильно, и я не знаю почему.

Ответы [ 2 ]

1 голос
/ 05 октября 2019

Было бы лучше, если вы начнете с Java-алгоритма и просто конвертируете его в Swift https://www.baeldung.com/java-quicksort

enter image description here

Версия Swift должна выглядеть примерно такнапример: 

func quickSort(_ arr: inout [Int], begin: Int, end: Int) {
    if begin < end {
        let partitionIndex = partition(&arr, begin: begin, end: end)
        quickSort(&arr, begin: begin, end: partitionIndex - 1)
        quickSort(&arr, begin: partitionIndex + 1, end: end)
    }
}
func partition(_ arr: inout [Int], begin: Int, end: Int) -> Int {
    let pivot = arr[end]
    var i = begin - 1
    for j in begin..<end {
        if arr[j] <= pivot {
            i += 1
            arr.swapAt(i, j)
        }
    }
    arr.swapAt(i + 1, end)
    return i + 1
}

Если вы хотите сделать quickSort изменяемым универсальным методом в коллекции для использования с любым сопоставимым элементом: 

extension MutableCollection where Self: RandomAccessCollection, Element: Comparable, Index == Int {
    mutating func quickSort(begin: Int, end: Int) {
        if begin < end {
            let partitionIndex = partition(begin: begin, end: end)
            quickSort(begin: begin, end: partitionIndex - 1)
            quickSort(begin: partitionIndex + 1, end: end)
        }
    }
    mutating func partition(begin: Int, end: Int) -> Int {
        let pivot = self[end]
        var i = begin - 1
        for j in begin..<end where self[j] <= pivot {
            i += 1
            swapAt(i, j)
        }
        swapAt(i + 1, end)
        return i + 1
    }
}

Тестирование игровой площадки: 

var array = [1,3,2,5,4,7,6]
array.quickSort(begin: 0, end: 6)
array  // [1, 2, 3, 4, 5, 6, 7]
0 голосов
/ 05 октября 2019

Ваши рекурсивные вызовы неверны

После завершения цикла вы меняете шарнир на left:
self.srtdArr.swapAt(left, end)
, поэтому ваш стержень находится в положении left после цикла

Это означает, что теперь вам нужно отсортировать массивы [start, left-1] и [left+1, end]: 

quickSort(start: start, end: left-1)
quickSort(start: left+1, end: end)
...