Популярные алгоритмы сортировки массивов
Комментарии
В избранное
Подписаться на ответы
Сортировка:
Древо развёрнутое
Свернуть все
Мне думается, что в 1с используется быстрая сортировка. Сравнения делались между сортировкой списком и быстрой сортировкой. Разница в сортировке массива размерностью 10 000 и значениями диапазоном от 0 до 100 при сортировке списком значений и быстрой сортировкой вообще незаметна. А вот на массиве размерностью 100 000 диапазон значений от 0 до 1000, сортировка списком значений показала результат около 2-3 секунд, а быстрая в среднем 6-7 секунд.
Мне приходилось использовать "свою" сортировку для сортировки дерева значений на управляемой форме. Уж не помню, чем меня не устраивал метод ДанныеФормыДерево -> ДеревоЗначений -> Сортировка -> ДанныеФормыДерево, но быстрая сортировка на клиенте подошла лучше.
а метод двоичного дерева?
У меня в свое время была курсовая по методам сортировки.
Так метод двоичного дерева на больших массивах сильно быстрей работает
PS 1C тогда и в проекте не существовало. Алгоритм сложный, рекурсивный, но шустрый на больших массивах.
У меня в свое время была курсовая по методам сортировки.
Так метод двоичного дерева на больших массивах сильно быстрей работает
PS 1C тогда и в проекте не существовало. Алгоритм сложный, рекурсивный, но шустрый на больших массивах.
(13) теоритически конечно интересно - у меня в свое время заметный выигрыш получался на массивах из сотен и более элементов. 10 чисел быстрее всего упорядочивает самый простой алгоритм.
Но вот на сколько реальна задача? Приведите кто-нибудь пример из жизни, пожалуйста.
Но вот на сколько реальна задача? Приведите кто-нибудь пример из жизни, пожалуйста.
Если не ошибаюсь, в сортировке вставками вместо:
Пока j > 0 Цикл
Если Замена < Массив[j - 1] Тогда
Массив[j] = Массив[j - 1];
Замена = j - 1;
Ключ = j - 1;
КонецЕсли;
j = j - 1;
КонецЦикла;
в идеале должно быть так:
Пока j > 0 И Замена < Массив[j - 1] Цикл
Массив[j] = Массив[j - 1];
Замена = j - 1;
Ключ = j - 1;
j = j - 1;
КонецЦикла;
В таком случае не будет бессмысленного перебора элементов в уже отсортированной части массива.
Пока j > 0 Цикл
Если Замена < Массив[j - 1] Тогда
Массив[j] = Массив[j - 1];
Замена = j - 1;
Ключ = j - 1;
КонецЕсли;
j = j - 1;
КонецЦикла;
в идеале должно быть так:
Пока j > 0 И Замена < Массив[j - 1] Цикл
Массив[j] = Массив[j - 1];
Замена = j - 1;
Ключ = j - 1;
j = j - 1;
КонецЦикла;
В таком случае не будет бессмысленного перебора элементов в уже отсортированной части массива.
А вот на массиве размерностью 100 000 диапазон значений от 0 до 1000, сортировка списком значений показала результат около 2-3 секунд, а быстрая в среднем 6-7 секунд.
ИМХО: Дак наверное и не получится "сортировку списком значений" обогнать. Это же функция платформы, а любые самописные алгоритмы требуют время на интерпритацию команд.
Вот еще надо проверить, сколько памяти массив и список отъедают, и может в жизни и пригодиться для обработки очень больших массивов.
Думал, что в конце статьи увижу табличку с замером производительности алгоритмов и потребляемыми ресурсами :(
Но все равно плюсую, познавательно.
(21) Я имел ввиду оценить ресурсы приблизительно. Допустим "Сортировка вставками" потребляет мало, т.к. не нужен доп. массив и используется всего 4 переменных. (Кстати, если сделать процедуру и работать не со Знач массив, а со ссылкой, то ресурсов потребуется в 2 раза меньше.) Экономия ресурсов - 5. А "Сортировка слиянием" создает новые массивы. Экономия - 3.
Почему я заговорил про ресурсы, пишу програмку, там использую 2-х мерные большие массивы. Комп слабоват. Сортирую через таблицы значений и память подъедает заметно, винда начинает использовать файл подкачки и падает производительность.
Замер памяти я делал так: запускал 1с, консоль программиста, писал код, смотрел потребляемую память через дисп.задач, запускал код(в конце выводил предупреждение, чтоб массив не уничтожился), опять смотрел память.
Результаты с 100 000 элементов от 0 до 65535 такие: Массив ~800 Кб, СписокЗначений ~9,5 Мб, ТаблицаЗначений с одной колонкой ~5,8 Мб. Еще заметил что после массива память освобождается почти сразу, а после списка или таблицы нет (но если запустить второй раз, увеличение потребления памяти уже намного меньше)
Почему я заговорил про ресурсы, пишу програмку, там использую 2-х мерные большие массивы. Комп слабоват. Сортирую через таблицы значений и память подъедает заметно, винда начинает использовать файл подкачки и падает производительность.
Замер памяти я делал так: запускал 1с, консоль программиста, писал код, смотрел потребляемую память через дисп.задач, запускал код(в конце выводил предупреждение, чтоб массив не уничтожился), опять смотрел память.
Результаты с 100 000 элементов от 0 до 65535 такие: Массив ~800 Кб, СписокЗначений ~9,5 Мб, ТаблицаЗначений с одной колонкой ~5,8 Мб. Еще заметил что после массива память освобождается почти сразу, а после списка или таблицы нет (но если запустить второй раз, увеличение потребления памяти уже намного меньше)
(21) насчет времени все просто.
Откуда взял, не помню, да простит меня автор.
Scr = Новый COMОбъект("MSScriptControl.ScriptControl");
Scr.Language = "javascript";
ВремяНачалаВыполнения = Scr.Eval("new Date().getTime()");
//выполнить код
ВремяКонцаВыполнения = Scr.Eval("new Date().getTime()");
ВремяВыполнения = ВремяКонцаВыполнения - ВремяНачалаВыполнения; //время в милисекундах ПоказатьОткуда взял, не помню, да простит меня автор.
Спасибо за проделанную работу. Имею два предложения по быстрой сортировке:
1. Для наглядности вызов ОтобразитьДиаграммуСортировки лучше разместить в цикле, тогда нагляднее будет.
2. Полагаю, так красивее, если условие выхода из цикла перенести из оператора Если в оператор Пока.
В итоге код процедуры будет такой
1. Для наглядности вызов ОтобразитьДиаграммуСортировки лучше разместить в цикле, тогда нагляднее будет.
2. Полагаю, так красивее, если условие выхода из цикла перенести из оператора Если в оператор Пока.
В итоге код процедуры будет такой
Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел)
i = НижнийПредел;
j = ВерхнийПредел;
m = Массив[Цел((i+j)/2)];
//Пока Истина Цикл
Пока i<=j Цикл
Пока Массив[i] < m Цикл
i = i + 1;
КонецЦикла;
Пока Массив[j] > m Цикл
j = j - 1;
КонецЦикла;
Если i<=j Тогда
Замена = Массив[i];
Массив[i] = Массив[j];
Массив[j] = Замена;
i = i + 1;
j = j - 1;
Если ПрименитьОтображениеСортировки Тогда
ОтобразитьДиаграммуСортировки(Массив);
КонецЕсли;
КонецЕсли;
//Если i>j Тогда
// Прервать;
//КонецЕсли;
КонецЦикла;
Если НижнийПредел < j Тогда
б_Сортировка(Массив,НижнийПредел,j);
КонецЕсли;
Если i < ВерхнийПредел Тогда
б_Сортировка(Массив,i,ВерхнийПредел);
КонецЕсли;
КонецПроцедуры
Показать
В коде процедуры быстрой сортировки забыли важную часть:
(Обработку скачал, там этот код есть)
Если i <= j Тогда
Замена = Массив[i];
Массив[i] = Массив[j];
Массив[j] = Замена;
i = i + 1;
j = j - 1;
КонецЕсли;(Обработку скачал, там этот код есть)
Когда-то, еще до нашей эры (ДОС, Паскаль) придумал метод сортировки: "разноской по значению" и для сравнения написал маленькую демо-програмку.
Прикрепленные файлы:
SORTDEMO.EXE
SORTDEMO.PAS
SORTSHOW.PAS
У вас в алгоритме вставками вроде как ошибка, проверьте на маленьких массивах, в теле цикла
Когда замена примет значение 0, то ниже в значение массива просто подставиться 0
Переделал алгоритм на более логичный, убрал ненужные переменные
Пока j > 0 И Замена < Массив[j - 1] Цикл
Массив[j] = Массив[j - 1];
Замена = j - 1;
Ключ = j - 1;
j = j - 1;
КонецЦикла; Когда замена примет значение 0, то ниже в значение массива просто подставиться 0
Переделал алгоритм на более логичный, убрал ненужные переменные
Для i = 1 По Массив.ВГраница() Цикл
Замена = Массив[i];
j = i;
Пока j > 0 И Массив[j - 1] > Замена Цикл
Массив[j] = Массив[j - 1];
j = j - 1;
КонецЦикла;
Массив[j] = Замена;
КонецЦикла;
Показать
Так же в быстрой сортировке в теле
Когда i = j, то элемент массива просто заменит сам себя. Это глупо по логике, можно добавить условие для красоты.
Если i<=j Тогда
Замена = Массив[i];
Массив[i] = Массив[j];
Массив[j] = Замена;
i = i + 1;
j = j - 1;
КонецЕсли;
Если i>j Тогда
Прервать;
КонецЕсли;
ПоказатьКогда i = j, то элемент массива просто заменит сам себя. Это глупо по логике, можно добавить условие для красоты.
Если i<=j Тогда
Если М[i] = М[j] Тогда
i = i + 1;
j = j - 1;
Иначе
Замена = М[i];
М[i] = М[j];
М[j] = Замена;
i = i + 1;
j = j - 1;
КонецЕсли;
КонецЕсли;
Если i>j Тогда
Прервать;
КонецЕсли;
Показать
Пример работы с массивом документов.
В списке выделили несколько накладных и хотите их распечатать по дате (масив содержит ссылки на РН)
если в массиве происходит хоть одна перестановка, то после окончания перебора,
перебор стартует еще раз. Перестановок не было - цикл заканчиваеться.
В списке выделили несколько накладных и хотите их распечатать по дате (масив содержит ссылки на РН)
если в массиве происходит хоть одна перестановка, то после окончания перебора,
перебор стартует еще раз. Перестановок не было - цикл заканчиваеться.
&НаСервере
Процедура ПечатьСписком(ТабДок,ТабДок_счета, ПараметрКоманды)
кол_док = ПараметрКоманды.количество();
не_сортирован=Истина;
пока не_сортирован цикл
тд=0; не_сортирован=ложь;
пока тд<кол_док-2 цикл
если ПараметрКоманды[тд].дата>ПараметрКоманды[тд+1].дата тогда
темп_док = ПараметрКоманды[тд+1];
ПараметрКоманды[тд+1] = ПараметрКоманды[тд];
ПараметрКоманды[тд] = темп_док;
не_сортирован = Истина;
КонецЕсли;
тд = тд+1;
КонецЦикла;
КонецЦикла; // массив отсортирован
Документы.РНОпт_БН.ПечатьСписком(ТабДок,ТабДок_счета,ПараметрКоманды);
КонецПроцедуры
Показать
Начал изучать алгоритмы, предлагаю быструю сортировку математика Хоара через рекурсию без замены:
Функция б_Сортировка(Массив)
Если Массив.вграница() = -1 Тогда
Возврат Массив;
КонецЕсли;
сред = Массив[Цел(Массив.ВГраница()/2)];
мин = Новый Массив();
макс = Новый Массив();
отсортированный = Новый Массив();
Для Каждого н из Массив цикл
Если н < сред Тогда
мин.Добавить(н);
ИначеЕсли н > сред Тогда
макс.Добавить(н);
Иначе
отсортированный.Добавить(н);
КонецЕсли;
КонецЦикла;
Возврат ОбъеденитьМассивы(ОбъеденитьМассивы(б_Сортировка(мин), отсортированный), б_Сортировка(макс));
КонецФункции
Функция ОбъеденитьМассивы(Приемник, Источник)
Для Каждого н Из Источник Цикл
Приемник.добавить(н);
КонецЦикла;
Возврат Приемник;
КонецФункции
Показать
Дали задачу с сортировкой массива на собеседовании.
Позднее получилось следующее (похоже на гномью сортировку):
Индекс = 1;
Пока Индекс < Массив.Количество() Цикл
Если Массив[Индекс - 1] < Массив[Индекс] Тогда
Индекс = Индекс + 1;
Иначе
Замена = Массив[Индекс];
Массив[Индекс] = Массив[Индекс - 1];
Массив[Индекс - 1] = Замена;
Индекс = Индекс - 1;
Если Индекс = 0 Тогда
Индекс = Индекс + 2;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Позднее получилось следующее (похоже на гномью сортировку):
Индекс = 1;
Пока Индекс < Массив.Количество() Цикл
Если Массив[Индекс - 1] < Массив[Индекс] Тогда
Индекс = Индекс + 1;
Иначе
Замена = Массив[Индекс];
Массив[Индекс] = Массив[Индекс - 1];
Массив[Индекс - 1] = Замена;
Индекс = Индекс - 1;
Если Индекс = 0 Тогда
Индекс = Индекс + 2;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Вакансии
Ведущий разработчик 1С / Team lead отдела разработки 1С
Москва
зарплата от 300 000 руб. до 300 000 руб.
Полный день
Москва
зарплата от 300 000 руб. до 300 000 руб.
Полный день
Аналитик-архитектор 1С ЕРП (управленческого учета)
Москва
зарплата от 300 000 руб. до 300 000 руб.
Полный день
Москва
зарплата от 300 000 руб. до 300 000 руб.
Полный день