Сообщение Re[18]: Java vs C# vs C++ от 03.10.2015 10:17
Изменено 03.10.2015 11:07 vdimas
Здравствуйте, Evgeny.Panasyuk, Вы писали:
V>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива.
V>>В этом случае он представляет из себя разновидность пузырьковой сортировки.
EP>Это не разновидность пузырьковой сортировки.
Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
Не помнишь, почему сортировка названа "пузырьковой"?
Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
V>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней.
EP>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
"Обычно" — это из-за std::sort, что ле? ))
Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
V>>В std::sort идет линейный поиск по той причине, которую уже многократно обсуждали на этом сайте — до, примерно, 16-ти элементов на современных процессорах выгодней искать элемент линейно, а не двоичным поиском.
EP>В том числе и по этой причине.
На самом деле только по этой причине.
Как раз для поиска в маленьких массивах использование линейного поиска — обычно.
EP>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой. Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
V>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. ))
EP>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива.
Я же тебе намекаю уже многократно, что пузырьковая сортировка — это целое семейство алгоритмов.
EP>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код.
V>>Стандартная и есть без лишнего прохода.
EP>Код в студию, иначе наш спор не разрешится.
В западной литературе шейкерную выделяют в отдельный вид сортировки, нас же её давали как разновидность пузырьковой.
Более того, визуализация шейкерной сортировки на видео — ошибочна, ы-ы-ы.
В шейкерной необходимо запоминать первое и последнее место обмена, т.е. должно происходить сужение диапазона.
На прямом проходе обнаруживается единственный обмен 5 с 6, на обратном проходе должно быть одно сравнение 5 с 4 и сразу выход.
Код тривиальный, писать не буду. ))
V>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива.
V>>В этом случае он представляет из себя разновидность пузырьковой сортировки.
EP>Это не разновидность пузырьковой сортировки.
Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
Не помнишь, почему сортировка названа "пузырьковой"?
Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
V>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней.
EP>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
"Обычно" — это из-за std::sort, что ле? ))
Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
V>>В std::sort идет линейный поиск по той причине, которую уже многократно обсуждали на этом сайте — до, примерно, 16-ти элементов на современных процессорах выгодней искать элемент линейно, а не двоичным поиском.
EP>В том числе и по этой причине.
На самом деле только по этой причине.
Как раз для поиска в маленьких массивах использование линейного поиска — обычно.
EP>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой. Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
V>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. ))
EP>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива.
Я же тебе намекаю уже многократно, что пузырьковая сортировка — это целое семейство алгоритмов.
EP>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код.
V>>Стандартная и есть без лишнего прохода.
EP>Код в студию, иначе наш спор не разрешится.
В западной литературе шейкерную выделяют в отдельный вид сортировки, нас же её давали как разновидность пузырьковой.
Более того, визуализация шейкерной сортировки на видео — ошибочна, ы-ы-ы.
В шейкерной необходимо запоминать первое и последнее место обмена, т.е. должно происходить сужение диапазона.
На прямом проходе обнаруживается единственный обмен 5 с 6, на обратном проходе должно быть одно сравнение 5 с 4 и сразу выход.
Код тривиальный, писать не буду. ))
Re[18]: Java vs C# vs C++
Здравствуйте, Evgeny.Panasyuk, Вы писали:
V>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива.
V>>В этом случае он представляет из себя разновидность пузырьковой сортировки.
EP>Это не разновидность пузырьковой сортировки.
Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
Не помнишь, почему сортировка названа "пузырьковой"?
Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
V>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней.
EP>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
"Обычно" — это из-за std::sort, что ле? ))
Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
V>>В std::sort идет линейный поиск по той причине, которую уже многократно обсуждали на этом сайте — до, примерно, 16-ти элементов на современных процессорах выгодней искать элемент линейно, а не двоичным поиском.
EP>В том числе и по этой причине.
На самом деле только по этой причине.
Как раз для поиска в маленьких массивах использование линейного поиска — обычно.
EP>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой. Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
V>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. ))
EP>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива:
Чуть меньше, чем квадратичная, не?
Я же тебе намекаю уже многократно, что пузырьковая сортировка — это целое семейство алгоритмов.
EP>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код.
V>>Стандартная и есть без лишнего прохода.
EP>Код в студию, иначе наш спор не разрешится.
В западной литературе шейкерную выделяют в отдельный вид сортировки, нам же её давали как разновидность пузырьковой.
Более того, самих разновидностей шейкерной как минимум три. Визуализация шейкерной сортировки на видео — самая неэффективная, ы-ы-ы.
В одной из разновидностей шейкерной запоминают последнее место обмена, при движении вперед это будет верхняя граница, при движении назад аналогично обнаруживается нижняя граница. Т.е. сужение диапазона на каждом проходе будет происходить не на 1 элемент (как на видео), а до фактического места последнего обмена.
В еще одной разновидности шейкерной можно запоминать не только последнее место обмена, но и первое, храня информацию о границах отсортированных областей по краям массива (отсортированным не в том смысле, что элементы на своих местах уже, а в том смысле, что они упорядочены в пределах своей области).
Код тривиальный, но длинный, открывать студию и писать не буду. ))
Вербально как-то так:
1. движение вперед от нижней до верхней границы неотсортированной области, поиск первой пары для обмена, запоминание нижней границы отсортированного диапазона (минус одна позиция от текущей); если обмена не было — выход.
2. продолжаем движение вперед, обмен при необходимости, запоминание верхней границы отсортированного диапазона.
3. сравнение с первым элементом из отсортированной области, при необходимости продолжаем "всплытие" (в любом случае, запомненная на предыдущем шаге граница не изменяется).
4. движение назад аналогично, потом goto 1.
На каждом шаге у нас "всплывает" максимальный (или "тонет" минимальный) элемент из неотсортированной области к её краю, т.е. применяется обычный пузырёк; на границе отсортированной области алгоритм меняется — мы движемся лишь до тех пор, пока необходим обмен.
V>>Линейный он лишь для случая одновременного поиска и сдвига элементов массива.
V>>В этом случае он представляет из себя разновидность пузырьковой сортировки.
EP>Это не разновидность пузырьковой сортировки.
Извини, но сравнение и обмен строго с соседним элементом — это характеристика сортировок из семейства пузырьковой.
Не помнишь, почему сортировка названа "пузырьковой"?
Блин, да я когда-то лабы делал по разным модификациям пузырьковых сортировок, а тут некоторые утверждают, что она только одна. ))
Аналогично по сортировкам слиянием — мы их штук пять-шесть проходили (если склероз не изменяет). А на визуализации я вижу лишь один из вариантов.
V>>Если же сначала найти необходимую позицию, а затем сдвинуть все необходимые элементы за раз, то так может оказаться эффективней.
EP>Может, не спорю что есть вариант с двоичным поиском, и что у него есть область применения. Я говорю что обычно он линейный.
"Обычно" — это из-за std::sort, что ле? ))
Там, как раз, всё очень необычно, а весьма специфично для специфичного этапа сортировки.
V>>В std::sort идет линейный поиск по той причине, которую уже многократно обсуждали на этом сайте — до, примерно, 16-ти элементов на современных процессорах выгодней искать элемент линейно, а не двоичным поиском.
EP>В том числе и по этой причине.
На самом деле только по этой причине.
Как раз для поиска в маленьких массивах использование линейного поиска — обычно.
EP>Там вообще говоря swap использовать не выгодно — там нет необходимости менять каждый соседний элемент между собой. Оптимальнее переместить текущий элемент в temp, все остальные переместить вправо, а потом переместить temp в левый край. Это операция ЕМНИП rotate_by_one.
Об этом и речь, чтобы не производить на каждом шаге сравнение с перестановкой. Но искать-то выгодней двоично, а не линейно, для массива из более 16-ти элементов на современных машинах!
V>>Похоже, что в тех реализациях, что ты представляешь — пузырьковая сортировка отработает N! (факториал) раз независимо от исходных данных. ))
EP>Очень смешно. Пузырьковая сортировка квадратична в худщем случае.
Вот как раз не смешно. Самый простой вариант пузырьковой сортировки отрабатывает фиксированное кол-во раз, независимо от содержимого массива:
for(int end = size - 1, end > 0, end--)
for(int i = 0; i < end; i++)
swap_if_needed(array[i], array[i+1]);Чуть меньше, чем квадратичная, не?
Я же тебе намекаю уже многократно, что пузырьковая сортировка — это целое семейство алгоритмов.
EP>>>Покажи реализацию без лишнего прохода, или хотя бы дай ссылку на код.
V>>Стандартная и есть без лишнего прохода.
EP>Код в студию, иначе наш спор не разрешится.
В западной литературе шейкерную выделяют в отдельный вид сортировки, нам же её давали как разновидность пузырьковой.
Более того, самих разновидностей шейкерной как минимум три. Визуализация шейкерной сортировки на видео — самая неэффективная, ы-ы-ы.
В одной из разновидностей шейкерной запоминают последнее место обмена, при движении вперед это будет верхняя граница, при движении назад аналогично обнаруживается нижняя граница. Т.е. сужение диапазона на каждом проходе будет происходить не на 1 элемент (как на видео), а до фактического места последнего обмена.
В еще одной разновидности шейкерной можно запоминать не только последнее место обмена, но и первое, храня информацию о границах отсортированных областей по краям массива (отсортированным не в том смысле, что элементы на своих местах уже, а в том смысле, что они упорядочены в пределах своей области).
Код тривиальный, но длинный, открывать студию и писать не буду. ))
Вербально как-то так:
1. движение вперед от нижней до верхней границы неотсортированной области, поиск первой пары для обмена, запоминание нижней границы отсортированного диапазона (минус одна позиция от текущей); если обмена не было — выход.
2. продолжаем движение вперед, обмен при необходимости, запоминание верхней границы отсортированного диапазона.
3. сравнение с первым элементом из отсортированной области, при необходимости продолжаем "всплытие" (в любом случае, запомненная на предыдущем шаге граница не изменяется).
4. движение назад аналогично, потом goto 1.
На каждом шаге у нас "всплывает" максимальный (или "тонет" минимальный) элемент из неотсортированной области к её краю, т.е. применяется обычный пузырёк; на границе отсортированной области алгоритм меняется — мы движемся лишь до тех пор, пока необходим обмен.