Сортировка в Java
1,00
р.
Прочел в документации и нигде не нашел объяснения (гуглил без результата), почему для реализации сортировки выбран метод слияния (пишут модифицированный, а что именно модифицировано ?), а не Qsort ?
Только из-за устойчивости алгоритма слияния или какие-то особенности работы с памятью в реализации JVM обуславливают этот выбор ?
Ведь Qsort требует значительно меньше дополнительной памяти да и по скорости (при разумной реализации) почти всегда превосходит (если верить Кнуту) MergeSort.
Какие есть соображения на эту тему ?
UPD
Ответов больше нет, обсуждение закончено. Всем огромное спасибо.
Просмотр материалов по MergeSort в Wiki навел меня на мысль попробовать реализовать ее (невзирая на предупреждение в Вики о большой сложности алгоритма) без выделения дополнительной памяти размером O(n).
yozh, одна реализация (или минимум реализаций) это мне тоже приходило в голову. Хотелось бы узнать, так ли это на самом деле.
Nikolay Artamonov, а какие еще устойчивые сложностью n*log(n) есть ? Я сходу не припоминаю.
Тогда уж еще один вопрос, почему не дали выбирать из нескольких (устойчивая/неустойчивая) ? Я имею в виду наличие нескольких алгоритмов в стандартных пакетах. Возможно, что бы путаницы меньше было. И так в Java огромное количество классов-методов.
1) Спасибо за ссылку, буду смотреть (это к комментарию с ссылкой на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms)
2) Нашел там интересный линк на реализацию в jdk7 - http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 Обещают замечательные характеристики (по дополнительной памяти max n/2 !) и вообще интересно.
Ответ
В стандартной библиотеке Java существует три группы перегруженных методов для сортировки:
java.util.Arrays.sort(prim[], ...) — для сортировки массивов примитивов prim (int, byte, char, и т.д.). Использует алгоритм быстрой сортировки (quick sort). java.util.Arrays.sort(T[], ...) и java.util.Arrays.sort(Object[], ...) — для сортировки массивов комплексных объектов произвольного типа T или Object. Использует алгоритм сортировки слиянием (merge sort). java.util.Collections.sort() — для сортировки коллекций. Использует алгоритм сортировки слиянием (merge sort).
Причина, по которой для сортировки коллекций и массивов комплексных объектов выбран алгоритм сортировки слиянием, заключается в том, что данный алгоритм является устойчивой сортировкой, в отличие от быстрой сортировки, являющейся неустойчивой. Устойчивой сортировкой называется такой алгоритм, который сохраняет порядок следования элементов с одинаковыми ключами сортировки. К примеру, пусть нам требуется отсортировать следующие пары чисел по первому числу пары:
(4, 2) (3, 7) (3, 1) (5, 6)
Тогда на выходе, в зависимости от использованного алгоритма сортировки, мы можем получить два различных результата:
(3, 7) (3, 1) (4, 2) (5, 6) (порядок сохранен) (3, 1) (3, 7) (4, 2) (5, 6) (порядок изменен)
В первом случае пары (3, 7) и (3, 1) с равными ключами сортировки остались в том же порядке следования, как и изначально. Во втором случае они поменялись местами.
Почему важна устойчивая сортировка? Она позволяет производить цепочку последовательных сортировок, добиваясь сортировки в группах и подгруппах коллекции. Покажем, что это означает, на примере (примеры записаны на языке Scala для минимизации избыточного кода, присущего Java, но смысл будет ясен). Пусть мы имеем структуру данных для представления музыкальных записей:
// `albumName` - имя музыкального альбома // `trackNumber` - номер трека в альбоме. case class Record(albumName: String, trackNumber: Int)
Разместим в списке несколько музыкальных произведений (из дискографии группы Metallica) в произвольном порядке:
val records = List(Record("Master of Puppets", 7), Record("Load", 4), Record("Load", 2), Record("Reload", 5), Record("Load", 3), Record("Reload", 3))
Теперь отсортируем записи по номеру трека:
scala> val byTrackNumber = records.sortBy(_.trackNumber) byTrackNumber: List[Record] = List(Record(Load,2), Record(Load,3), Record(Reload,3), Record(Load,4), Record(Reload,5), Record(Master of Puppets,7))
А затем отсортируем еще раз, но уже по имени альбома:
scala> byTrackNumber.sortBy(_.albumName) res4: List[Record] = List(Record(Load,2), Record(Load,3), Record(Load,4), Record(Master of Puppets,7), Record(Reload,3), Record(Reload,5))
Что мы получили? Мы получили список записей, отсортированный по имени альбома, а в каждом альбоме отсортированный по номеру трека! Для этого мы сначала применили сортировку по менее значимому ключу (номер трека), которая сортирует для нас записи в подгруппах (альбомах). Затем сортировку по более значимому ключу - имени альбома. Такая последовательность важна. Следует заметить, что этот результат можно было бы получить, если сразу отсортировать записи по альбому И номеру трека за один раз, но существуют ситуации, когда нам неизвестны заранее все ключи, по которым мы будем сортировать коллекцию. К примеру, пользователь программы может выбрать в графическом интерфейсе сначала сортировку по полю "номер трека", а только затем по полю "альбом".
В случае, если бы мы применили нестабильную сортировку, вышеуказанный результат не гарантирован. Почему тогда для сортировки примитивов используется быстрая сортировка, являющаяся неустойчивой? Потому что равные примитивы (числа, символы) неотличимы друг от друга при перестановке, в отличие от комплексных объектов. Иными словами, примитивы можно сортировать только по одному ключу (их значениям). Поэтому для них допустимо применить более быстрый алгоритм, коим и является быстрая сортировка.
Только из-за устойчивости алгоритма слияния или какие-то особенности работы с памятью в реализации JVM обуславливают этот выбор ?
Ведь Qsort требует значительно меньше дополнительной памяти да и по скорости (при разумной реализации) почти всегда превосходит (если верить Кнуту) MergeSort.
Какие есть соображения на эту тему ?
UPD
Ответов больше нет, обсуждение закончено. Всем огромное спасибо.
Просмотр материалов по MergeSort в Wiki навел меня на мысль попробовать реализовать ее (невзирая на предупреждение в Вики о большой сложности алгоритма) без выделения дополнительной памяти размером O(n).
yozh, одна реализация (или минимум реализаций) это мне тоже приходило в голову. Хотелось бы узнать, так ли это на самом деле.
Nikolay Artamonov, а какие еще устойчивые сложностью n*log(n) есть ? Я сходу не припоминаю.
Тогда уж еще один вопрос, почему не дали выбирать из нескольких (устойчивая/неустойчивая) ? Я имею в виду наличие нескольких алгоритмов в стандартных пакетах. Возможно, что бы путаницы меньше было. И так в Java огромное количество классов-методов.
1) Спасибо за ссылку, буду смотреть (это к комментарию с ссылкой на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms)
2) Нашел там интересный линк на реализацию в jdk7 - http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 Обещают замечательные характеристики (по дополнительной памяти max n/2 !) и вообще интересно.
Ответ
В стандартной библиотеке Java существует три группы перегруженных методов для сортировки:
java.util.Arrays.sort(prim[], ...) — для сортировки массивов примитивов prim (int, byte, char, и т.д.). Использует алгоритм быстрой сортировки (quick sort). java.util.Arrays.sort(T[], ...) и java.util.Arrays.sort(Object[], ...) — для сортировки массивов комплексных объектов произвольного типа T или Object. Использует алгоритм сортировки слиянием (merge sort). java.util.Collections.sort() — для сортировки коллекций. Использует алгоритм сортировки слиянием (merge sort).
Причина, по которой для сортировки коллекций и массивов комплексных объектов выбран алгоритм сортировки слиянием, заключается в том, что данный алгоритм является устойчивой сортировкой, в отличие от быстрой сортировки, являющейся неустойчивой. Устойчивой сортировкой называется такой алгоритм, который сохраняет порядок следования элементов с одинаковыми ключами сортировки. К примеру, пусть нам требуется отсортировать следующие пары чисел по первому числу пары:
(4, 2) (3, 7) (3, 1) (5, 6)
Тогда на выходе, в зависимости от использованного алгоритма сортировки, мы можем получить два различных результата:
(3, 7) (3, 1) (4, 2) (5, 6) (порядок сохранен) (3, 1) (3, 7) (4, 2) (5, 6) (порядок изменен)
В первом случае пары (3, 7) и (3, 1) с равными ключами сортировки остались в том же порядке следования, как и изначально. Во втором случае они поменялись местами.
Почему важна устойчивая сортировка? Она позволяет производить цепочку последовательных сортировок, добиваясь сортировки в группах и подгруппах коллекции. Покажем, что это означает, на примере (примеры записаны на языке Scala для минимизации избыточного кода, присущего Java, но смысл будет ясен). Пусть мы имеем структуру данных для представления музыкальных записей:
// `albumName` - имя музыкального альбома // `trackNumber` - номер трека в альбоме. case class Record(albumName: String, trackNumber: Int)
Разместим в списке несколько музыкальных произведений (из дискографии группы Metallica) в произвольном порядке:
val records = List(Record("Master of Puppets", 7), Record("Load", 4), Record("Load", 2), Record("Reload", 5), Record("Load", 3), Record("Reload", 3))
Теперь отсортируем записи по номеру трека:
scala> val byTrackNumber = records.sortBy(_.trackNumber) byTrackNumber: List[Record] = List(Record(Load,2), Record(Load,3), Record(Reload,3), Record(Load,4), Record(Reload,5), Record(Master of Puppets,7))
А затем отсортируем еще раз, но уже по имени альбома:
scala> byTrackNumber.sortBy(_.albumName) res4: List[Record] = List(Record(Load,2), Record(Load,3), Record(Load,4), Record(Master of Puppets,7), Record(Reload,3), Record(Reload,5))
Что мы получили? Мы получили список записей, отсортированный по имени альбома, а в каждом альбоме отсортированный по номеру трека! Для этого мы сначала применили сортировку по менее значимому ключу (номер трека), которая сортирует для нас записи в подгруппах (альбомах). Затем сортировку по более значимому ключу - имени альбома. Такая последовательность важна. Следует заметить, что этот результат можно было бы получить, если сразу отсортировать записи по альбому И номеру трека за один раз, но существуют ситуации, когда нам неизвестны заранее все ключи, по которым мы будем сортировать коллекцию. К примеру, пользователь программы может выбрать в графическом интерфейсе сначала сортировку по полю "номер трека", а только затем по полю "альбом".
В случае, если бы мы применили нестабильную сортировку, вышеуказанный результат не гарантирован. Почему тогда для сортировки примитивов используется быстрая сортировка, являющаяся неустойчивой? Потому что равные примитивы (числа, символы) неотличимы друг от друга при перестановке, в отличие от комплексных объектов. Иными словами, примитивы можно сортировать только по одному ключу (их значениям). Поэтому для них допустимо применить более быстрый алгоритм, коим и является быстрая сортировка.
