Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.01.2008, 15:19
Andrey K

 
Сообщений: n/a

Эффективность алгоритмов сортировки
Хочу тут поднять вопрос:
Почему при оценке эффективности учитывается только количество сравнений?
Ведь операция копирования элемента - занимает ,примерно, столько-же времени, что и операция сравнения а количество переносов элементов ,с места на место, в разных алгоритмах не пропорционально количеству сравнений.

И ,к стати, ао поводу СОРТИРОВКИ ВСТАВКОЙ:
В общепринятом описании алгоритма есть довольно крупная ошибка:
там почему-то предлагается "для пущей эффективности" ставить стоповый нулевой элемент в начало списка ... но не учитывается что элемент вставляется уже в отсортированный кусок и ,следовательно, тут надо применять не перебор, а метод половинного деления (для поиска места вставки).
Я реализовал у себя в ,одной проге, такой алгоритм и пока он является самым эффективным из всех, не говоря уже про частично отсортированные списки (а такие обычно и встречаются в реальных задачах).
  #2  
Старый 11.01.2008, 16:05
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Почему при оценке эффективности учитывается только количество сравнений?
Это не так. Количество передвижений (обменов при обменных сортировках) также анализируется - например, сортировка выбором хороша по этому критерию

>В общепринятом описании алгоритма есть довольно крупная ошибка
А где это такое "общепринятое" ????
  #3  
Старый 11.01.2008, 16:06
гость

 
Сообщений: n/a

Цитата:
И ,к стати, ао поводу СОРТИРОВКИ ВСТАВКОЙ:
В общепринятом описании алгоритма есть довольно крупная ошибка:
"Общепринятый" источник в студию.

Цитата:
но не учитывается что элемент вставляется
уже в отсортированный кусок и ,следовательно, тут надо применять не перебор,
а метод половинного деления (для поиска места вставки).
У Кнута такой алгоритм описан, под названием "Сортировка двоичными вставками".

Проблема в том, что хотя место для вставки и можно найти достаточно быстро
двоичным поиском, чтобы этот элемент вставить приходится сдвигать, в среднем,
половину этого отсортированного куска (а в худшем случае - весь),
поэтому выигрыш от двоиного поиска небольшой, время работы все равно
останется порядка O(n^2) шагов.

Правда, если в массиве оставлять пустые места для будущих элементов, то можно
и достичь оптимального времени работы O(n log n), как показано в
этой статье - http://citeseer.ist.psu.edu/630187.html

Цитата:
Я реализовал у себя в ,одной проге, такой алгоритм и пока он является
самым эффективным из всех, не говоря уже про частично отсортированные
списки (а такие обычно и встречаются в реальных задачах).
Да ну?
Сравните его и стандартную процедуру сортировки в вашем языке (которая, скорее всего будет вариантом quicksort'а) на обратно-упорядоченном массиве: N,N-1,N-2,...,3,2,1, скажем для N=1000000.
  #4  
Старый 11.01.2008, 21:03
Andrey K

 
Сообщений: n/a

>"Общепринятый" источник в студию.
http://algolist.manual.ru/sort/insert_sort.php
Этот алгоритм я на здешнем сайте и увидал, поэтому собственно тут и создал тему ... если это не "общепринятый" - то надо подправить... а то люди будут неправильные проги писать.

>Сравните его и стандартную процедуру сортировки в вашем языке (которая, скорее всего будет вариантом quicksort'а) на обратно-упорядоченном массиве: N,N-1,N-2,...,3,2,1, скажем для N=1000000.

Зачем же крайние случаи рассматривать?
Вероятность такого варианта очень мала и её можно не учитывать.

>>Почему при оценке эффективности учитывается только количество >сравнений?
>Это не так. Количество передвижений (обменов при обменных >сортировках) также анализируется - например, сортировка выбором >хороша по этому критерию

Я везде встречал только оценку по сравнениям, поэтому невозможно найти ДЕЙСТВИТЕЛЬНО самый быстрый вариант ... мой-же опыт пока говорит о самой быстрой сортировке - вставками.
  #5  
Старый 11.01.2008, 21:42
гость

 
Сообщений: n/a

Сообщение от Andrey K Посмотреть сообщение
Зачем же крайние случаи рассматривать?
Вероятность такого варианта очень мала и её можно не учитывать.
Этот случай как раз очень даже вероятен на практике.

Но если не хотите его, попробуйте случайный вход.
Мат. ожидание числа перемещений элементов у сортировки вставкой все равно порядка O(n^2), а точнее - N^2/4.
  #6  
Старый 15.01.2008, 16:35
Andrey K

 
Сообщений: n/a

Провёл у себя статистику:
В моей задаче списки ,в среднем, оказались частично отсортированы на 80-90%... может поэтому и лучшие показатели.

А вообще видимо много зависит от задачи.

Например при слиянии отсортированных списков - очень важен процент взаимного перекрытия двух объединяемых списков и их относительные размеры - для каждого случая свой алгоритм.

Я по этому поводу тоже как-то провёл статистику - и оказалось, что значительная часть всех слияний - это добавление одного элемента в большой список - по алгоритму получается он простым перебором сравнивался со всеми элементами для поиска места вставки - учёт этого частного случая дал ускорение в 10 раз!
  #7  
Старый 16.01.2008, 17:03
гость

 
Сообщений: n/a

Цитата:
Например при слиянии отсортированных списков - очень важен процент взаимного перекрытия двух объединяемых списков и их относительные размеры - для каждого случая свой алгоритм.
Два отсортированных списка можно легко слить за время O(n) -- всего лишь одним проходом по массивам.
Перекрытие элементов списков на время работы не влияет.
  #8  
Старый 16.01.2008, 18:53
Andrey K

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Два отсортированных списка можно легко слить за время O(n) -- всего лишь одним проходом по массивам.
Перекрытие элементов списков на время работы не влияет.
А теперь примените этот свой алгоритм к случаю когда 1 элемент в одном массиве и n элементов в другом - у вас на слияние этих списков потратится ,как вы справедливо заметили, O(n) ... но если я этот элемент буду добавлять методом вставки половинным делением , то время слияния этих списков будет ~log(n) а если в списке два элемента?
Выходит что если списки сильно различаются по размеру простой проход - это не самый эффективный алгоритм... то-же для непересекающихся списков - их вообще можно обьединить за одну операцию копирования (ускорение в n раз)... а вы перебор всех элементов предлагаете.
  #9  
Старый 16.01.2008, 19:49
гость

 
Сообщений: n/a

Цитата:
А теперь примените этот свой алгоритм к случаю когда 1 элемент в одном массиве и n элементов в другом - у вас на слияние этих списков потратится ,как вы справедливо заметили, O(n) ... но если я этот элемент буду добавлять методом вставки половинным делением , то время слияния этих списков будет ~log(n)
O(log n) будет только если вы храните элементы списков в виде сбалансированного дерева, или в аналогичной структуре данных.
А это слишком накладно для такой простой задачи как отсортировать массив.

Если вы используете массивы, то, как пример, чтобы вставить элемент 1 в массив {2,3,4,...,N} нужно переместить N-1 элемент массива, т.е. O(n) времени.
Двоичный поиск тут не поможет - что с того, что он быстро (т.е. за O(log n) времени) может вычислить куда вставлять элемент, если вставить в это место так же быстро не получится?
  #10  
Старый 12.12.2009, 18:35
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Если вы используете массивы, то, как пример, чтобы вставить элемент 1 в массив {2,3,4,...,N} нужно переместить N-1 элемент массива, т.е. O(n) времени.
А зачем перемещать каждый элемент, массив линеен (в плане расположения в памяти), можно сдвинуть элементы вправо простым копированием памяти.
это очень быстро, поверьте.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Российский конкурс алгоритмов Gribok Участие 0 15.12.2007 13:28
Исследование эффективности методов сортировки 10asTAII Сортировка и поиск 3 30.11.2007 10:20
помогите решить (код поразрядной сортировки) незарегистрированный Реализация, исходники, языки 5 01.06.2007 13:16