Login
schnelle Sortierung
NEW 22.02.08 20:11
in Antwort scorpi_ 22.02.08 19:24
но второй цикл идёт с конца навстречу первому.
-----
Смотри тут: http://www.intuit.ru/department/algorithms/algocombi/14/2.html
Второй (внутренний) цикл вообще не зависит от первого цикла - просто тупо гоняется перебор смежных пар пока есть перестановки. А так как есть гарантия для N^2, то просто пишутся два цикла до N... Остальное - модификаци, сокращающие количество сравниваемых пар...
-----
Смотри тут: http://www.intuit.ru/department/algorithms/algocombi/14/2.html
Второй (внутренний) цикл вообще не зависит от первого цикла - просто тупо гоняется перебор смежных пар пока есть перестановки. А так как есть гарантия для N^2, то просто пишутся два цикла до N... Остальное - модификаци, сокращающие количество сравниваемых пар...
NEW 22.02.08 20:20
in Antwort scorpi_ 22.02.08 20:11
Сортировка вставками
-----
Ну на разницу в одно слово хорошие программеры внимания не обращают.... :)
В сортировке простыми вставками вставки выполняются в новый массив, уменьшая число сдвигаемых элементов.
-----
Ну на разницу в одно слово хорошие программеры внимания не обращают.... :)
В сортировке простыми вставками вставки выполняются в новый массив, уменьшая число сдвигаемых элементов.
NEW 22.02.08 20:30
Естественно, можно написать два полных цикла, со всплыванием большего элемента:
Но для этого надо быть совсем тупым... Обычно везде приводят встречные циклы.
Объясни мне плиз разницу (и дай ссылки) между "сортировка простыми вставками" и "сортировка вставками".
in Antwort Murr 22.02.08 20:11
В ответ на:
Смотри тут: http://www.intuit.ru/department/algorithms/algocombi/14/2.html
Второй (внутренний) цикл вообще не зависит от первого цикла - просто тупо гоняется перебор смежных пар пока есть перестановки. А так как есть гарантия для N^2, то просто пишутся два цикла до N... Остальное - модификаци, сокращающие количество сравниваемых пар...
Смотри тут: http://www.intuit.ru/department/algorithms/algocombi/14/2.html
Второй (внутренний) цикл вообще не зависит от первого цикла - просто тупо гоняется перебор смежных пар пока есть перестановки. А так как есть гарантия для N^2, то просто пишутся два цикла до N... Остальное - модификаци, сокращающие количество сравниваемых пар...
Естественно, можно написать два полных цикла, со всплыванием большего элемента:
В ответ на:
template<class Iterator>
void bubble_sort( Iterator First, Iterator Last )
{
for( Iterator i = First; i < Last; ++i )
for( Iterator j = First; j < Last - 1; ++j )
if ( *j > *(j + 1) )
std::iter_swap( (j + 1), j );
}
Но для этого надо быть совсем тупым... Обычно везде приводят встречные циклы.
В ответ на:
Ну на разницу в одно слово хорошие программеры внимания не обращают.... :)
В сортировке простыми вставками вставки выполняются в новый массив, уменьшая число сдвигаемых элементов.
Ну на разницу в одно слово хорошие программеры внимания не обращают.... :)
В сортировке простыми вставками вставки выполняются в новый массив, уменьшая число сдвигаемых элементов.
Объясни мне плиз разницу (и дай ссылки) между "сортировка простыми вставками" и "сортировка вставками".
NEW 22.02.08 20:47
in Antwort scorpi_ 22.02.08 20:30, Zuletzt geändert 22.02.08 20:48 (scorpi_)
Ещё раз для полной ясности. Пузырек делается либо с погружением наименьшего элемента:
либо со всплыванием наибольшего:
В ответ на:
template<class Iterator>
void bubble_sort( Iterator First, Iterator Last )
{
for( --Last; First < Last; ++First )
for( Iterator i = Last; i > First; --i )
if ( *i < *(i - 1) )
std::iter_swap( (i - 1), i );
}
либо со всплыванием наибольшего:
В ответ на:
template<class Iterator>
void bubble_sort( Iterator First, Iterator Last )
{
while( First < --Last )
for( Iterator i = First; i < Last; ++i )
if ( *i > *(i + 1) )
std::iter_swap( (i + 1), i );
}
NEW 22.02.08 21:33
in Antwort scorpi_ 22.02.08 20:30
Но для этого надо быть совсем тупым...
------
Или быть в жестком цейтноте, когда на обдумывание времени просто нет...
Обычно везде приводят встречные циклы.
------
Но это уже не базовый пузырек.
Объясни мне плиз разницу (и дай ссылки) между
-----
Насколько Я помню - Д.Кнут. Том 3.
http://www.intuit.ru/department/pl/plpascal/4/
Обрати внимание на примечание в конце описания.
------
Или быть в жестком цейтноте, когда на обдумывание времени просто нет...
Обычно везде приводят встречные циклы.
------
Но это уже не базовый пузырек.
Объясни мне плиз разницу (и дай ссылки) между
-----
Насколько Я помню - Д.Кнут. Том 3.
http://www.intuit.ru/department/pl/plpascal/4/
Обрати внимание на примечание в конце описания.
NEW 22.02.08 22:03
Вполне базовый.
Ну посмотрел. Ничего там про два массива нет. Вообще говоря Кнут в вопросе сортировок несколько устарел, ибо после написания третьего тома в этой области кое-что продвинулось. Конкретно по вставкам - он рассматривает простые вставки, бинарные и Шелла. О бинарных собственно давно уже никто не вспоминает, ибо двигать элементы всё равно надо, Шелла с тех пор уже досконально изучили с целью нахождения идеальной последовательности шагов, и во всех современных книгах он рассматривается совершенно отдельно. Так что никто в современной литературе между "простыми" и "непростыми" вставками не различает. Короче говоря - в данном вопросе лучше изучать что-нибудь посвежее, хотя бы Седжвика (он кстати ученик Кнута).
В ссылке также ничего про второй массив нет нет.
in Antwort Murr 22.02.08 21:33
В ответ на:
Обычно везде приводят встречные циклы.
------
Но это уже не базовый пузырек.
Обычно везде приводят встречные циклы.
------
Но это уже не базовый пузырек.
Вполне базовый.
В ответ на:
Объясни мне плиз разницу (и дай ссылки) между
-----
Насколько Я помню - Д.Кнут. Том 3.
http://www.intuit.ru/department/pl/plpascal/4/
Обрати внимание на примечание в конце описания.
Объясни мне плиз разницу (и дай ссылки) между
-----
Насколько Я помню - Д.Кнут. Том 3.
http://www.intuit.ru/department/pl/plpascal/4/
Обрати внимание на примечание в конце описания.
Ну посмотрел. Ничего там про два массива нет. Вообще говоря Кнут в вопросе сортировок несколько устарел, ибо после написания третьего тома в этой области кое-что продвинулось. Конкретно по вставкам - он рассматривает простые вставки, бинарные и Шелла. О бинарных собственно давно уже никто не вспоминает, ибо двигать элементы всё равно надо, Шелла с тех пор уже досконально изучили с целью нахождения идеальной последовательности шагов, и во всех современных книгах он рассматривается совершенно отдельно. Так что никто в современной литературе между "простыми" и "непростыми" вставками не различает. Короче говоря - в данном вопросе лучше изучать что-нибудь посвежее, хотя бы Седжвика (он кстати ученик Кнута).
В ссылке также ничего про второй массив нет нет.
NEW 22.02.08 22:27
in Antwort scorpi_ 22.02.08 22:03
Вполне базовый.
-----
Базовый - смежные пары и тупой перебор. Именно так, как описано по приведенной ссылке.
в данном вопросе лучше изучать что-нибудь посвежее
-----
А нужно ли? Если писать самому - вполне достаточно тупого пузырька.
Для чего-то более сложного - либы. По крайней мере некоторые из сортировок Я не
возьмусь писать с нуля и по памяти - просто не помню всех деталей... Хотя когда-то писал все доступные...
Ничего там про два массива нет.
В ссылке также ничего про второй массив нет нет.
-----
Да, там один массив. Правда - второй. Вот про первый - там ничего нет, кроме ссылки на то, что данные надо последовательно откуда-то брать.
-----
Базовый - смежные пары и тупой перебор. Именно так, как описано по приведенной ссылке.
в данном вопросе лучше изучать что-нибудь посвежее
-----
А нужно ли? Если писать самому - вполне достаточно тупого пузырька.
Для чего-то более сложного - либы. По крайней мере некоторые из сортировок Я не
возьмусь писать с нуля и по памяти - просто не помню всех деталей... Хотя когда-то писал все доступные...
Ничего там про два массива нет.
В ссылке также ничего про второй массив нет нет.
-----
Да, там один массив. Правда - второй. Вот про первый - там ничего нет, кроме ссылки на то, что данные надо последовательно откуда-то брать.
NEW 22.02.08 23:53
Это твой выбор. Мне лично пузырька недостаточно.
Конкретно из того что было придумано после Кнута и реально используется - introsort, in-place mergesort, вариант heapsort'а в среднем более быстрого чем quicksort. Это из внутренних сортировок. А уж зарекаться насчёт внешних сортировок, что не придётся их писать, я тем более не стану.
in Antwort Murr 22.02.08 22:27
В ответ на:
А нужно ли? Если писать самому - вполне достаточно тупого пузырька.
Для чего-то более сложного - либы. По крайней мере некоторые из сортировок Я не
возьмусь писать с нуля и по памяти - просто не помню всех деталей... Хотя когда-то писал все доступные...
А нужно ли? Если писать самому - вполне достаточно тупого пузырька.
Для чего-то более сложного - либы. По крайней мере некоторые из сортировок Я не
возьмусь писать с нуля и по памяти - просто не помню всех деталей... Хотя когда-то писал все доступные...
Это твой выбор. Мне лично пузырька недостаточно.
Конкретно из того что было придумано после Кнута и реально используется - introsort, in-place mergesort, вариант heapsort'а в среднем более быстрого чем quicksort. Это из внутренних сортировок. А уж зарекаться насчёт внешних сортировок, что не придётся их писать, я тем более не стану.
23.02.08 00:21
in Antwort scorpi_ 22.02.08 23:53
Это твой выбор.
-----
Разумеется.
И если будет необходимо именно писать одну из перечисленных тобой сортировок - Я увенрен, что Я ее напишу.
Но если мне надо иметь отсортированные данные и нет времени писать - пузырек, с минимальными модификациями. Будет необходимость - можно заменить позднее.
-----
Разумеется.
И если будет необходимо именно писать одну из перечисленных тобой сортировок - Я увенрен, что Я ее напишу.
Но если мне надо иметь отсортированные данные и нет времени писать - пузырек, с минимальными модификациями. Будет необходимость - можно заменить позднее.