Пригодился ли вам алгоритм сортировки?

Уточни какой именно

повод для гордости?

Мне пригодился как-то. На собеседовании тестовое задание решил, правда туда все равно не пошел работать

Сортирую пузырьком и ниипёт

Бинарный поиск - вещь!

Пригождалось для понимания того, какое место в коде оптимизировать и как.
Грубо говоря, можно не помнить как работает qsort, но знать что в 1С именно он, и знать его алгоритмическую сложность.

Когда-то оч.давно, в СССР-е, когда я, МНС в красноярском Институте Физики программно моделировал движение доменных стенок в тонких плёнках, почти вся программа сводилось к непрерывной пересортировке двумерных массивов. И да, замена алгоритма пузырька на шейкер-сортировку ускорила работу программки раз так в тридцать. Так что Вирту я очень благодарен.

А в 1С-ке ни разу не пригодилась...

Да, я по нему и другим алгоритмам изучал алгоритмирование :)

(8) Да, Вирт (http://cv01.twirpx.net/0001/0001776.jpg) в свое время стал внезапным открытием. Когда писали ассемблер (или дизассемблер - уже не помню) - были поражены, насколько квиксорт быстрее "интуитивного" пузырька.

А знание модели OSI, а способность рассчитать, сколько памяти требуется для n-цветного дисплея c количеством пикселей MxK?

Учат всегда не тому, что нужно в жизни...

А мне очень пригождается Сортировать() таблицу значений, полученную например при чтении строк из файла. Ну а чем еще сортировать?

(0) эти задачки нужны были для построения алгоритмического мышления. ВАШ КЭП

(12) а можно не сортировать, а построить индекс, и выбирать по индексу...

(14) можно, только зачем если есть готовый метод сортировки?

разве что он вероятно, медленнее

(15) так индекс - это по сути та же сортировка, только без передвигания содержимого.

(14) Самому построить индекс нужно уметь.

Нет. Чтобы отсортировать тот же массив, можно использовать список значений.

(17) это да, но если ТЗ это реквизит ТП, то проще сортировать() ее перед выводом на форму

(0) пригодился бинарный поиск, когда понадобилось ускорить формирование таблицы 1.5 в книге учета по ОСНО 1С:Предприниматель (для 7.7). В 2004 году.

в 1С эффективней использовать функции платформы сортировки
для не стандартных случаев в типовых пишут "свои" сортировки

(10) Там ещё метод быстрой перестановки был - который очень даже хорошо сортирует.
Только сама сортировка не спасает - нужно ещё и упорядочивание хранить как-то, чтобы объекты в памяти не переставлять.

Сортировки - нет, а вот поиск в отсортированном - да.
А в 1С всегда достаточно встроенной сортировки.

а как же. на собеседование без пузырька еще ни разу не обошлось.

Нет никогда.

(25) А вот интересно - вопрошающе про метод перестановок рассказать сами смогут или им википедия понадобится ?

(27) нет ничего проще "пузырька". даже википедия вопрошающим не нужна

Кстати а какой лучший алгоритм десортировки?

Чтобы в отсортированных данных навел полный бардак, так чтобы отсортировать заняло дофига времени?

Причем очень быстро это сделал и качественно! Примерно как перетасовка карточной колоды.

(29) Сначала нужно знать как будут сортировать.

(30) Хорошо лучший для каждого из известных/популярных как будут сортировать и в среднем по всем

(29) смотря какой алгоритм сортировки
насколько я помню быструю сортировку убивал напрочь если выбраемый элемент есть мнмальный
если выбираемый первый, то отсортированный массив будет сортироваться дольше всего
если центральный, но ставим в центр минимальный, а остальные по возрастанию добавляем справа и слева.

сортировке слияниями пофиг, она не зависит от порядка.
сортировке вставками если используется список, то по возрастанию самое страшное.

Кстати, вот чисто случайно наткнулся на наглядный пример того, как понимание алгоритмов позволяет существенно оптимизировать специфическую выборку данных по скорости:
http://catalog.mista.ru/public/551583/

(34) Илдарович товарищ конечно умный, но иногда слишком заумно решает проблему которая имеет намного более простое решение.

Кто мешает в его "задачке интервалов" построить на отдельных таблицах свой индекс, который получается путем наложения интервалов друг на друга, получением всех "точек пересечений".
Затем из этих "точек пересечений" получаем "минимальные отрезки не пересекающиеся отрезки" и строим из них индекс, где будет отрезок и в какие исходные интервалы он входит.

В результате поиск нужных исходных интервалов (записей) по искомой позиции будет банальным, путем одного индекса (неважно слева или справа) для нашей таблицы индексов.

Вспомнилась газетная статья из тех времен, когда появились первые калькуляторы. В статье обсуждался вопрос, нужно ли современному школьнику знать таблицу умножения и умение считать в столбик. ИМХО - нужно. И об алгоритмах сортировки программист представление тоже должен иметь.

Пригодился при поступлении в институт)

(36) Лучше ещё и о хранении данных подумать, так как сама по себе сортировка - ничего не решает, особенно, если в набор данных будут добавления или удаления.
Там уже будут немного другие слова об оптимальности.

(0)Программист - понятие широкое.
Большая часть современных программистов работает с фреймворками.
Т.е это не чисто программирование, а больше конфигурирование фремворка.
Это и 1с, и вся веб-разработка, и создание оконных приложений в большинстве своем.
И любые задачи надо решать встроенными в фреймворк методами.
Если ты использовал самописный алгоритм - это gовнокод, велосипедостроение, в общем - вон из профессии.
Тут ценится скорость разработки, и понятность коду, а не быстродействие и эффективное использование ресурсов.
Это не плохо, не хорошо, просто так есть.

А алгоритмы, в том числе и сортировки нужны при низкоуровневом программировании, без их знания там будет трудно.

(39) Даже прикладнику надо знать о порядке быстродействия и потребности в памяти используемых алгоритмов, чтобы не написать код, который умрет при определенном объеме данных. Типичный пример такой ситуации - сохранение большого количества строк с автовысотой в xls из 7.7. Так что, считаю, программист в любом случае должен знать об сортировках, двоичных и прочих деревьях и вообще о всём что написано у Вирта. Это как сопромат для инженера-строителя.

Да пригодился. Особенно пригодились внешние методы сортировки. А так же всякая мелочевка типа решающих деревьев и т.д.

(40) Не факт.
Работая с фреймворком довольно трудно предсказать потребность в памяти и эффективность работы алгоритма, через несколько уровней абстракции.

(42) Приходится доверять разработчикам фреймворка, да. Предполагать, что они используют максимально оптимальные алгоритмы и методы. В точности так же, как строитель не отправляет каждый куль цемента на лабораторное исследование, доверяя указанной марке.

Была пару раз ситуация, когда сортировал своими методами.
Из забавного - как-то использовал метод ветвей и границ

> Пригодился ли вам алгоритм сортировки?

Очень хороший вопрос! Дает повод похвастаться изобретением собственного метода сортировки имени моего имени : ) .

Алгоритм описан в статьях «Внешняя сортировка «естественным слиянием» ( http://emery-emerald.narod.ru/Cpp/2E1562.html ) и «Work C++ Algorithm of External Natural Merge Sort with Non-decreasing and Decreasing Ordered Sub Sequences» ( http://www.codeproject.com/Articles/92761/Work-C-Algorithm-of-External-Natural-Merge-Sort-wi )

Преимущество указанного алгоритма в том, что он использует по максимуму существующий частичный порядок данных. И даже в случае абсолютно равномерно распределенной случайной последовательности данных их средняя длина  L упорядоченных подпоследовательностей (УПП) > 2, так как любые две сравнимые величины всегда образуют УПП. Хотя возможен частный случай «зигзагообразной» последовательности данных произвольной длины, средняя длина L УПП которой в точности равна двум. Например, для последовательности нулей и единиц:

{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1, . . .} : L = Lmin = 2

Фактически эта последовательность обладает минимальным порядком для целей нашего алгоритма. Однако нашим преимуществом остается один проход для функции Split, фиксированный объем данных для ее параметров и наличие только двух файловых буферов (с учетом неизменности исходных данных).

Но вернемся к случаю равномерно распределенной случайной последовательности данных. Какова будет средняя длина L (определяемая как отношение суммарной длины последовательности к количеству всех УПП на ней)? Ясно, что в этом случае

L > Lmin = 2

и тем самым мы можем использовать этот дополнительный порядок для более быстрой сортировки. А это можно сказать уже алгоритмическое преимущество.

Задача по вычислению средней длины УПП L для равномерно распределенной случайной последовательности данных не кажется очень сложной, однако в Интернете не удалось найти готовое решение, поэтому пришлось озадачить форум математиков и после совместного обсуждения проблемы (в теме: «Распределение порядка во всех перестановках») мне (под ником Scholium) удалось вычислить эту величину ( http://dxdy.ru/topic25746.html ):

L = 2e – 3 = 2.436563656918 .

Не правда ли интересно? Случайная последовательность и обладает частичным порядком больше минимального! Что уж тут говорить про реальные данные упорядоченность которых всегда выше абсолютно равномерного распределения случайных величин. Вот почему данный алгоритм представляет особый интерес. К тому изобретен он был для практических целей – сортировки больших массивов внешних данных, вроде dbf-файлов.

Думаю, что я еще вернусь к этим исследованиям и разработкам в дальнейшем.

(4) Пузырек не самый быстрый метод ;)

(0)Держи Шейкерную сортировку, на больших объемах работает быстрее пузырьков :)

https://ru.wikipedia.org/wiki/Сортировка_перемешиванием

А вообще, вот тут почитай...
https://ru.wikipedia.org/wiki/Алгоритм_сортировки

(42) Ну и соответственно когда штатное перестает работать, дело все равно кончается велосипедами, чтобы хоть как-то решить задачу. На практике я бы не возводил ничего в абсолют, в том числе и механизмы фреймворков. Главое - решить поставленный вопрос, а уж как - это проблемы программиста. Если решил плохо - авось другие перерешают или сам со временем.

(48) Ну не всегда так.
Если проект большой, а ты на своем участке сделал костыль нештатными методами - при следующем же релизе это вылезет, и все придется переписывать.

Если ты целиком контролируешь проект тогда можно.

(46) Вообще быстрота не единственный и не всегда главный показатель. Есть еще такие вещи как потребляемая память.

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

(48) А как же "использовать только методы, освященные Нуралиевым, и записанные в священных ЖКК и ЖЖК"? :-)

(50) Ага, скорость не важна, можно и подождать день другой :DDD

Вы не попутали мисту с хаброй?

(50) Шейкерная дает не хилый результат на Миллиардах.

И не совсем хороший на 100 ;)

Тут серьезными проектами занимаются, а сортировки и прочие досуги нердов обсуждают там.

(52) если задача разовая - можно за час написать, и пусть хоть два дня считает.
если задача ежедневная для 100 юзверей - то лишняя минута работы алгоритма в день будет ежемесячно обходиться компании в четверть средней зарплаты.

(55) Да бросьте, народ кроме пузырька не чего не знает :)

(54) если эти "милллиарды" влезут в память с произвольным доступом.

(56) Нет нечего постоянней, чем временное :)

(52) Я же говорю не всегда важна.
Кроме скорости есть потребление памяти.

Например выбрал ты алгоритм который работает в два раза быстрее, но потребляет в два раза больше памяти.
На реальной задаче у тебя памяти банально не хватает, комп уходит в подкачку, и в результате твой быстрый алгоритм работает в сто раз медленнее. Хоть и быстрый.

(59) не "временное", а "разовое". там выходят на повестку совсем другие критерии.

(61) Для разового и сортировки не надо :)

(54) Как я помню по Вирту, самая лучшая сортировка - пирамидальная. В отличие от "быстрой" она не может выродиться в O(n*n) при неудачном наборе данных.

(63) Мне трудно говорить про Пирамидку.
Но Шейкерную я писал, в свое время... Сравнивал с пузырьками.

...
Так сказать видел все в воочию :)

+ Все дело было еще во времена Пней :)

(0) Мне однажды продавец в магазине попросили сдачу монетами по порядку выложить.
Если бы не знал методов сортировки, не смог бы.

(66) Это не совсем сортировка - это заполнение массива данными с сортировкой. Хотя, чаще всего, проще сначала заполнить, а потом сортировать.

(67) Все я ушел бухать, жизнь прожита зря...

(68) Когда поймёшь, что бухать - тоже зря - возвращайся, мы тут ещё чего-нить интересного вспомним.