Существует ли этот алгоритм сортировки? (реализовано в Swift) - PullRequest
Новая
       37

Существует ли этот алгоритм сортировки? (реализовано в Swift)

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

Это может быть плохой вопрос, но мне любопытно.

Я следил за онлайн-курсами по некоторым структурам данных и алгоритмам, и я наткнулся на такие алгоритмы, как выборка, вставка, пузырьковая сортировка, сортировка слиянием,быстрая сортировка, сортировка в куче. Они почти никогда не приближаются к O (n), когда массив сортируется в обратном порядке.

Мне было интересно одно: почему мы не используем пространство вместо времени?

Когда я что-то организовываю, я беру это и кладу туда, где оно принадлежит. Поэтому я подумал, что если у нас есть массив элементов, мы могли бы просто поместить каждое значение в индекс с этим значением.

Вот моя реализация в Swift 4: 

let simpleArray = [5,8,3,2,1,9,4,7,0]
let maxSpace = 20

func spaceSort(array: [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    var realResult = [Int]()
    var result = Array<Int>(repeating: -1, count: maxSpace)

    for i in 0..<array.count{
        if(result[array[i]] != array[i]){
            result[array[i]] = array[i]
        }
    }
    for i in 0..<result.count{
        if(result[i] != -1){
            realResult.append(i)
        }
    }
    return realResult
}

var spaceSorted = [Int]()

var execTime = BenchTimer.measureBlock {
    spaceSorted = spaceSort(array: simpleArray)
}
print("Average execution time for simple array: \(execTime)")
print(spaceSorted)

Результаты, которые я получаю:

enter image description here

Этот алгоритм сортировки уже существует?

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

И почему я не могу использовать Int.max для maxSpace?

Редактировать: я получаю ошибку ниже

ошибка: выполнение было прервано.

при использовании let maxSpace = Int.max

MyPlayground (6961,0x7000024af000) malloc: обнаружено повреждение кучи, свободный список поврежден при0x600003b7ebc0 * Неверное значение защиты: 0 MyPlayground (6961,0x7000024af000) malloc: * установить точку останова в malloc_error_break для отладки

Спасибо за ответы

1 Ответ

2 голосов
/ 26 октября 2019

Это экстремальный вариант сортировки по основанию. Цитируется из Wikipedia :

radix sort - это не сравнительный алгоритм сортировки. Это позволяет избежать сравнения путем создания и распределения элементов в ведра в соответствии с их осями. Для элементов с более чем одной значащей цифрой этот процесс группирования повторяется для каждой цифры, сохраняя при этом порядок предыдущего шага, пока все цифры не будут учтены. По этой причине радикальная сортировка также называется сортировкой по сегментам и цифровой сортировкой.

В этом случае вы выбираете основание как maxSpace, и поэтому у вас нет элементов с более чемодна значащая цифра "(из цитаты выше).

Теперь, если бы вы использовали структуру данных Hash Set вместо массива, вам на самом деле не нужно было бы выделять место длявесь спектр. Вы все равно сохраните все итерации цикла (от 0 до maxSpace), и он проверит, содержит ли хэш-набор значение i (переменная цикла), и, если это так, выведет его.

Это может быть эффективным алгоритмом, только если maxSpace имеет тот же порядок величины, что и количество элементов во входном массиве. Другие алгоритмы сортировки могут сортировать с O (nlogn) сложностью по времени, поэтому для случаев, когда maxSpace намного больше, чем nlogn , алгоритм не настолько убедителен.

...