Comments 6
Статье поставил «+» и в закладки, но если бы на интервью кандидат на iOS-разработчика на просьбу отсортировать массив начал писать код вручную вместо использования sort() или sort(by:), я бы, пожалуй, засчитал это задание в минус.
Другое дело, если бы в задании было прямо сказано, что стандартные функции использовать нельзя.
Кстати, в первом листинге import UIKit не требуется.
Время выполнения для быстрой сортировки равно O(n log n), как и для сортировки слиянием, но это более быстрый алгоритм, чем сортировка слиянием.Можно пояснить, откуда такой вывод? Знаю только, что в худшем случае quicksort работает гораздо медленней сортировки слиянием (за О(n²)), и mergesort можно распараллелить вплоть до достижения O(log(n)). А среднее время выполнения у merge и quick одинаково, даже в статье так написано. Тогда почему первое место — быстрая сортировка?
спасиибо за вопрос, чтобы ответить я загуглил и теперь знаю ответ)
Быстрая сортировка имеет время выполнения O (n2) в худшем случае и время выполнения O (nlogn) в среднем. Однако во многих сценариях сортировка слиянием предпочтительнее, потому что на время выполнения алгоритма влияет множество факторов, но, если взять их все вместе, побеждает быстрая сортировка. В частности, часто упоминаемое время выполнения алгоритмов сортировки относится к количеству сравнений или количеству перестановок, необходимых для сортировки данных. Это действительно хороший показатель производительности, особенно потому, что он не зависит от аппаратного обеспечения. Однако другие вещи, такие как локальность ссылки (т.е. мы читаем много элементов, которые, вероятно, находятся в кеше?) также играют важную роль на текущем оборудовании. Быстрая сортировка, в частности, требует немного дополнительного места и демонстрирует хорошую локальность кэша, что во многих случаях делает ее быстрее, чем сортировка слиянием. Кроме того, очень легко почти полностью избежать наихудшего времени выполнения быстрой сортировки O(n2), используя соответствующий выбор точки опоры, например, выбирая ее случайным образом (это отличная стратегия). На практике многие современные реализации быстрой сортировки (в частности, std::sort в libstdc++) на самом деле представляют собой интросортировку, чей теоретический наихудший случай равен O(nlogn), как и при сортировке слиянием. Это достигается путем ограничения глубины рекурсии и переключения на другой алгоритм (heapsort), когда он превышает logn.
Ужасные объяснения, вы сами перечитывали свое сумбурное повествование? Вот например абзац:
Давайте посмотрим, как теперь сортировка слиянием разбивает массив.
Теперь? Что-то изменилось, я что то пропустил?
Когда алгоритм сортировки слиянием задается в массиве,
алгоритм задается в массиве?
первое, что он делает, это берет этот массив и разбивает его на составляющие его наименьшие части,
поэтому он берет каждый элемент этого массива и создает массив самого себя,
Помимо корявых фраз, непонятно, что такое массив самого себя?
в основном путем непрерывного деления на два, пока он не сократит этот массив до наименьших элементов (отдельных чисел) в массиве.
А не в основном?
Несколько раз перечитал абзац - ничего не понял... Уж простите за докапывание, но ведь это всего лишь объяснения базовых алгоритмов...
Вот и все, друзья, которых вы только что покорили и только что прошлись по всем основным алгоритмам сортировки.
Жесть конечно...
Алгоритмы сортировки в Swift