Void sort c что это
Array List. Sort Метод
Определение
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Сортирует элементы в списке ArrayList или в его части.
Перегрузки
Сортирует элементы во всем списке ArrayList.
Сортирует элементы во всем списке ArrayList с помощью указанной функции сравнения.
Сортирует элементы в диапазоне элементов списка ArrayList с помощью указанной функции сравнения.
Сортирует элементы во всем списке ArrayList.
Исключения
Объект ArrayList доступен только для чтения.
Примеры
Комментарии
В среднем этот метод является O(n log n) операцией, где n имеет значение Count ; в худшем случае это O(n^2) операция.
См. также раздел
Применяется к
Sort(IComparer)
Сортирует элементы во всем списке ArrayList с помощью указанной функции сравнения.
Параметры
Реализация интерфейса IComparer, которая используется при сравнении элементов.
-или- Пустая ссылка ( Nothing в Visual Basic) для использования реализации IComparable каждого элемента.
Исключения
Объект ArrayList доступен только для чтения.
При сравнении двух элементов возникла ошибка.
Примеры
В следующем примере кода показано, как сортировать значения в ArrayList с помощью компаратора по умолчанию и пользовательского компаратора, который изменяет порядок сортировки на обратный.
Комментарии
Используйте Sort метод для сортировки списка объектов с помощью пользовательского компаратора, реализующего IComparer интерфейс. При передаче в null comparer этот метод использует IComparable реализацию каждого элемента. В этом случае необходимо убедиться, что объекты, содержащиеся в списке, реализуют IComparer интерфейс, или возникнет исключение.
Кроме того, использование IComparable реализации означает, что список выполняет сортировку по сравнению (также называемую нестабильной сортировкой); то есть если два элемента равны, их порядок может не сохраняться. В отличие от этого, стабильная сортировка сохраняет порядок элементов, равных. Чтобы выполнить стабильную сортировку, необходимо реализовать пользовательский IComparer интерфейс.
В среднем этот метод является O(n log n) операцией, где n имеет значение Count ; в худшем случае это O(n^2) операция.
Definition
Some information relates to prerelease product that may be substantially modified before it’s released. Microsoft makes no warranties, express or implied, with respect to the information provided here.
Sorts the elements or a portion of the elements in the List using either the specified or default IComparer implementation or a provided Comparison delegate to compare list elements.
Overloads
Sorts the elements in a range of elements in List using the specified comparer.
Sorts the elements in the entire List using the default comparer.
Sorts the elements in the entire List using the specified comparer.
Sort(Comparison )
Parameters
The Comparison to use when comparing elements.
Exceptions
The implementation of comparison caused an error during the sort. For example, comparison might not return 0 when comparing an item with itself.
Examples
The following code demonstrates the Sort and Sort method overloads on a simple business object. Calling the Sort method results in the use of the default comparer for the Part type, and the Sort method is implemented using an anonymous method.
The following example demonstrates the Sort(Comparison ) method overload.
A List of strings is created and populated with four strings, in no particular order. The list also includes an empty string and a null reference. The list is displayed, sorted using a Comparison generic delegate representing the CompareDinosByLength method, and displayed again.
Remarks
If comparison is provided, the elements of the List are sorted using the method represented by the delegate.
This method uses Array.Sort, which applies the introspective sort as follows:
If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm
If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.
Otherwise, it uses a Quicksort algorithm.
This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
This method is an O(n log n) operation, where n is Count.
See also
Applies to
Sort(Int32, Int32, IComparer )
Sorts the elements in a range of elements in List using the specified comparer.
Parameters
The zero-based starting index of the range to sort.
The length of the range to sort.
The IComparer implementation to use when comparing elements, or null to use the default comparer Default.
Exceptions
index is less than 0.
count is less than 0.
The implementation of comparer caused an error during the sort. For example, comparer might not return 0 when comparing an item with itself.
Examples
The following example demonstrates the Sort(Int32, Int32, IComparer ) method overload and the BinarySearch(Int32, Int32, T, IComparer ) method overload.
A List of strings is created and populated with the names of five herbivorous dinosaurs and three carnivorous dinosaurs. Within each of the two groups, the names are not in any particular sort order. The list is displayed, the range of herbivores is sorted using the alternate comparer, and the list is displayed again.
The BinarySearch(Int32, Int32, T, IComparer ) method overload is then used to search only the range of herbivores for «Brachiosaurus». The string is not found, and the bitwise complement (the
Remarks
If comparer is provided, the elements of the List are sorted using the specified IComparer implementation.
This method uses Array.Sort, which applies the introspective sort as follows:
If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm
If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.
Otherwise, it uses a Quicksort algorithm.
This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
This method is an O(n log n) operation, where n is Count.
See also
Applies to
Sorts the elements in the entire List using the default comparer.
Exceptions
Examples
The following example adds some names to a List object, displays the list in unsorted order, calls the Sort method, and then displays the sorted list.
The following code demonstrates the Sort() and Sort(Comparison ) method overloads on a simple business object. Calling the Sort() method results in the use of the default comparer for the Part type, and the Sort(Comparison ) method is implemented by using an anonymous method.
The following example demonstrates the Sort() method overload and the BinarySearch(T) method overload. A List of strings is created and populated with four strings, in no particular order. The list is displayed, sorted, and displayed again.
The BinarySearch(T) method overload is then used to search for two strings that are not in the list, and the Insert method is used to insert them. The return value of the BinarySearch method is negative in each case, because the strings are not in the list. Taking the bitwise complement (the
Remarks
This method uses the Array.Sort method, which applies the introspective sort as follows:
If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm.
If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.
Otherwise, it uses a Quicksort algorithm.
This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
This method is an O(n log n) operation, where n is Count.
Функция sort и компаратор в C++: что это такое
Привет, дорогие читатели! Этот урок посвящен встроенной сортировке C++ и ее учителю — компаратору.
Что такое функция sort
Это функция, которая может сортировать указанный контейнер или обычный массив. По умолчанию она сортирует по неубыванию, но это можно изменить путем применения компаратора, об этом поговорим позже.
Принцип работы построен на алгоритме быстрой сортировки (quicksort), так что за быстроту можно не волноваться.
Также в C++ имеется другая сортировка — qsort, но она работает значительно медленнее текущей.
Функция sort для вектора
Вот как выглядит конструкция вызова:
Вот как выглядит пример запуска программы:
Функция sort для списка
Функция sort для массива (array)
Чтобы отсортировать массив нам нужно использовать схему ниже:
Так, например можно:
Что такое компаратор
Компаратор — это функция, которая как бы учит сортировать sort. Так например можно сортировать по:
Обычно его используют когда имеется например — vector > vec и нужно отсортировать вектора по второму элементу первой ячейки ( vec[i][0].second ).
Как создать компаратор
Самого начала создаём функцию, которая и будет компаратором.
Определение
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Сортирует элементы или части элементов в списке List с использованием заданного значения или значения по умолчанию IComparer реализации или предоставленного делегата Comparison для сравнения элементов списка.
Перегрузки
Сортирует элементы в диапазоне элементов списка List с помощью указанной функции сравнения.
Сортирует элементы во всем списке List с помощью функции сравнения по умолчанию.
Сортирует элементы во всем списке List с помощью указанной функции сравнения.
Sort(Comparison )
Параметры
Исключения
Реализация comparison вызвала ошибку во время сортировки. Например, comparison не может возвратить 0 при сравнении элемента с самим собой.
Примеры
В следующем коде показаны Sort Sort перегрузки методов и для простого бизнес-объекта. Вызов Sort метода приводит к использованию компаратора по умолчанию для типа Part, а Sort метод реализуется с помощью анонимного метода.
В следующем примере показана Sort(Comparison ) перегрузка метода.
List Строки создаются и заполняются четырьмя строками без определенного порядка. Список также содержит пустую строку и пустую ссылку. Список отображается, сортируется с помощью Comparison универсального делегата, представляющего CompareDinosByLength метод, и снова отображается.
Комментарии
Если comparison указано, элементы объекта List сортируются с помощью метода, представленного делегатом.
Если размер секции меньше 16 элементов или равен ему, он использует алгоритм сортировки вставки.
В противном случае используется алгоритм QuickSort.
Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраняться. В отличие от этого, стабильная сортировка сохраняет порядок элементов, равных.
См. также раздел
Применяется к
Sort(Int32, Int32, IComparer )
Сортирует элементы в диапазоне элементов списка List с помощью указанной функции сравнения.
Параметры
Индекс (с нуля) начала диапазона, который требуется отсортировать.
Длина диапазона сортировки.
Исключения
Значение параметра index меньше 0.
-или- Значение параметра count меньше 0.
-или- Реализация comparer вызвала ошибку во время сортировки. Например, comparer не может возвратить 0 при сравнении элемента с самим собой.
Примеры
В следующем примере демонстрируется Sort(Int32, Int32, IComparer ) перегрузка метода и BinarySearch(Int32, Int32, T, IComparer ) перегрузка метода.
List Строки создаются и заполняются именами из пяти динозавров хербивораус и трех динозавров карнивораус. В каждой из этих двух групп имена не имеют определенного порядка сортировки. Отобразится список, диапазон хербиворес будет отсортирован с помощью альтернативного компаратора, а список снова отобразится.
BinarySearch(Int32, Int32, T, IComparer )Затем перегрузка метода используется для поиска только диапазона хербиворес для «брачиосаурус». строка не найдена и побитовое дополнение (оператор
Комментарии
Если размер секции меньше 16 элементов или равен ему, он использует алгоритм сортировки вставки.
В противном случае используется алгоритм QuickSort.
Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраняться. В отличие от этого, стабильная сортировка сохраняет порядок элементов, равных.
См. также раздел
Применяется к
Сортирует элементы во всем списке List с помощью функции сравнения по умолчанию.
Исключения
Примеры
В следующем примере добавляются некоторые имена в List объект, отображается список в несортированном порядке, вызывается Sort метод, а затем отображается отсортированный список.
В следующем коде показаны Sort() Sort(Comparison ) перегрузки методов и для простого бизнес-объекта. Вызов Sort() метода приводит к использованию компаратора по умолчанию для типа Part, а Sort(Comparison ) метод реализуется с помощью анонимного метода.
В следующем примере демонстрируется Sort() перегрузка метода и BinarySearch(T) перегрузка метода. List Строки создаются и заполняются четырьмя строками без определенного порядка. Список отображается, сортируется и отображается снова.
BinarySearch(T)Затем перегрузка метода используется для поиска двух строк, которых нет в списке, и Insert для их вставки используется метод. Возвращаемое значение BinarySearch метода в каждом случае отрицательно, поскольку строки отсутствуют в списке. при получении побитового дополнения (оператор
Комментарии
Этот метод использует Array.Sort метод, который применяет сортировку гибридности следующим образом:
Если размер секции меньше 16 элементов или равен ему, он использует алгоритм сортировки вставки.
Если количество секций превышает 2 log n, где n — диапазон входного массива, используется алгоритм хеапсорт.
В противном случае используется алгоритм QuickSort.
Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраняться. В отличие от этого, стабильная сортировка сохраняет порядок элементов, равных.
.NET 1.0
А теперь собственно классы SorterObjectArray и SorterGenericArray:
Так что же тут происходит? Следующий код
это не что иное, как попытка использовать ковариацию массивов, которая, как известно, работает только для ссылочных типов. Получается, для ссылочных типов используется класс SorterObjectArray, а для значимых типов используется SorterGenericArray. Но подождите, чем отличаются данные классы? Как вы можете заметить, они отличаются только способом доступа к элементам массива. Для значимых типов используются методы GetValue и SetValue, которые как вы знаете, являются очень медленными… Получается, что массив целых чисел будет сортироваться очень долго (ведь целое число является значимым типом)? Нет! Массив целых чисел сортируется быстро, причем очень быстро. Все дело в следующем коде
Интерес представляет метод Array.TrySZSort. Этот метод вызывает нативную реализацию сортировки реализованную на С++ в самой CLR. Причем работает он для примитивных типов, когда мы используем стандартную логику сравнения элементов, то есть когда comparer == Comparer.Default || comparer == null.
А вот и нативная реализация:
Как видите, нативная сортировка работает только для примитивных типов. К ним относятся все числовые типы + логический + символьный. А для значимых пользовательских типов все будет работать плачевно медленно.
Переходим к рассмотрению реализации именно самого алгоритма сортировки. Будем рассматривать реализацию в классе SorterObjectArray, так как и нативная реализация и реализация для значимых типов аналогична.
1. В качестве опорного элемента всегда берется середина массива:
Это не хорошо, так как при плохих входных данных время выполнения алгоритма может стать квадратичным. К тому же середина берется по формуле num1 + num2 >> 1, что может привести к переполнению типа int. Такая же ошибка была сделана в алгоритме бинарного поиска и сортировки в Java (ссылка на баг).
2. Для того, чтобы избежать переполнения стека в данной реализация предусмотрена оптимизация, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии, ни при каких обстоятельствах не превысит log2n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
.NET 2.0
А вот собственно метод, который сортирует
Следует сказать, что оптимизация для встроенных примитивных типов все еще есть, не смотря на наличие обобщений (смотри комментарий разработчиков). То есть примитивные типы по-прежнему используют нативную сортировку.
В качестве опорного элемента теперь берется не середина массива, а медиана из первого, серединного и последнего элементов массива.
К тому же теперь середина вычисляется по формуле index1 + (index2 — index1 >> 1), что исключает ошибок связанных с переполнением.
В остальном все по-прежнему без изменений.
Теперь маленькое отступление: пусть нам надо отсортировать по убыванию массив целых чисел. Как вы будете это делать?
Учитывая все вышесказанное, следующий код
на моем компьютере работает примерно в 3 раза быстрее, чем
Вас может смутить тот факт, что метод Array.Reverse не обобщен, а значит, со значимыми типами будет работать медленно (упаковка и методы GetValue, SetValue), но если взглянуть на его реализацию мы опять увидим оптимизацию для встроенных значимых типов, а именно он вызывает нативный метод Array.TrySZReverse, который выглядит так:
В общем оптимизации в стандартной библиотеке нас поджидают за каждым углом.
Кстати весьма странно, что нет обобщенной версии данного метода. Есть метод Reverse как метод расширение у Enumerable, но его недостаток в том, что он это делает не на месте. Получается, что вызов Array.Reverse на массиве пользовательских значимых типов всегда приводит к автобоксингу.
Алгоритм не претерпел изменений.
.NET 4.5
Самое интересное начинается здесь!
Как видите это та же быстрая сортировка за исключением одного: алгоритм переключается на пирамидальную сортировку, если мы исчерпаем глубину рекурсии, которая по умолчанию равна 32.
А вот собственно и пирамидальная сортировка:
Алгоритм DepthLimitedQuickSort есть ни что иное как IntroSort.
Introsort или интроспективная сортировка — алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень. Этот подход сочетает в себе достоинства обоих методов с худшим случаем O(n log n) и быстродействием, сравнимым с быстрой сортировкой. Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений.
Теперь посмотрим на то, что происходит в IntrospectiveSort. Фактически это та же интроспективная сортировка только более оптимизированная. Кстати, MSDN по-прежнему говорит, что использует быструю сортировку.
Теперь сортировка в массивах представляет собой смесь сортировок: сортировку вставками, быструю сортировку и пирамидальную сортировку.
Использование Introsort положительно влияет на производительность, поскольку в реальных задачах данные бывают частично упорядочены, а на таких данных, как известно сортировка вставками работает очень быстро.
Сравнение производительности
Сравнение с Java
Как известно быстрая сортировка является неустойчивой, что является недостатком при сортировке ссылочных типов. Поскольку в Java «всё как бы объекты», то эта проблема усиливается, поэтому для сортировки ссылочных типов используется сортировка слиянием. Данная сортировка является устойчивой и гарантирует O(n logn) времени выполнения в худшем случае, однако и требует O(n) дополнительной памяти.
Поскольку проблема устойчивости касается только ссылочных типов, для примитивов не имеет значения, меняем ли мы элементы с одним ключом или нет. Поэтому для сортировки примитивов Java использует улучшенный алгоритм быстрой сортировки — DualPivotQuicksort. Обычный Quicksort делит массив на два отрезка, выбрав случайный элемент P. Потом сортирует массив так, чтобы все элементы меньше P попали в первый отрезок, а остальные — во второй. Затем алгоритм рекурсивно повторяется на первом и на втором отрезках. DualPivotQuicksort делит массив на три отрезка, вместо двух. В результате количество операций перемещения элементов массива существенно сокращается.
В Java 7 алгоритм сортировки ссылочных типов поменялся на TimSort.
Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7 и реализован в Android JDK 1.5. Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки.
Timsort — быстр, однако на случайных данных уступает примерно на 30 процентов быстрой сортировке.