Популярные алгоритмы сортировки массивов

Публикация № 204320 18.10.13

Разработка - Математика и алгоритмы

Сортировка Массивы Алгоритмы

Разбор популярных алгоритмов сортировки массивов, реализованных на 1с. + обработка с наглядной реализацией алгоритмов.

В статье  рассмотрены одни из самых популярных алгоритмов сортировки для массивов, применяемых как практически, так и в учебных целях. Сразу хочу оговориться, что все рассмотренные алгоритмы медленнее, чем метод классической сортировки массива через список значений, но тем не менее, заслуживают внимания. Текста получается много, поэтому по каждому алгоритму описываю самое основное. 


1.Алгоритм "Сортировка выбором". 

Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.

Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.

//Сортировка выбором {---
Функция СортировкаВыбором(Знач Массив) 
	
	Мин = 0;
	Для i = 0 По Массив.ВГраница() Цикл		
		Мин = i;                       		
		Для j = i + 1 ПО Массив.ВГраница() Цикл		//Ищем минимальный элемент в массиве	
			Если Массив[j] < Массив[Мин] Тогда
				Мин = j;
			КонецЕсли; 
		КонецЦикла; 
		Если Массив [Мин] = Массив [i] Тогда           //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем.
			Продолжить;
		КонецЕсли;
		
		Смена = Массив[i];                            //Производим замену элементов массива.
		Массив[i] = Массив[Мин];
		Массив[Мин] = Смена;  
		
	КонецЦикла;
	Возврат Массив;	
КонецФункции
 

2.Алгоритм "Сортировка пузырьком". 

Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком"

Алгоритм:
1.  Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент[i+1] происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а  самые тяжелые "тонут" - перемещаются к концу.
2.  Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().

//Сортировка пузырьком {---
Функция СортировкаПузырьком(Знач Массив)
	
	Для i = 0 По Массив.ВГраница() Цикл
		Для j = 0 ПО Массив.Вграница() - i - 1 Цикл
			Если Массив[j] > Массив[j + 1] Тогда
				Замена = Массив[j];
				Массив[j] = Массив[j + 1];
				Массив[j + 1] = Замена;
			КонецЕсли;			
		КонецЦикла;		
	КонецЦикла;	
	Возврат Массив;	
КонецФункции
//---}

3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).

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

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

В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.

//Сортировка перемешивание (Шейкер-Сортировка) {---
Функция СортировкаПеремешиванием(Знач Массив)
	
	Для i = 0 ПО Массив.ВГраница()/2 Цикл
		
		нИтер = 0;
		конИтер = Массив.ВГраница();  		
		Пока нИтер  Массив[нИтер+1] Тогда
				Замена = Массив[нИтер];
				Массив[нИтер] = Массив[нИтер + 1];
				Массив[нИтер + 1] = Замена;				
			КонецЕсли;
			нИтер = нИтер + 1;//Двигаем позицию на шаг вперед
			//Проходим с конца
			Если Массив[конИтер - 1] > Массив[конИтер] Тогда
				Замена = Массив[конИтер - 1];
				Массив[конИтер-1] = Массив[конИтер];
				Массив[конИтер] = Замена;				
			КонецЕсли;
			конИтер = конИтер - 1;//Двигаем позицию на шаг назад  			
		КонецЦикла; 		
	КонецЦикла;	   
	
	Возврат Массив;	
	
КонецФункции
//---}

4. Алгоритм "Гномья сортировка".

Алгоритм так странно назван благодаря голландскому ученому Дику Груну.

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун

Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.

//Гномья сортировка {---   
Функция ГномьяСортировка(Знач Массив)
	
	i = 1;
	j = 2;
	
	Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию   
		
		Если Массив[i-1]  
			i = j;
			j = j + 1;
		Иначе
			Замена = Массив[i];
			Массив[i] = Массив[i - 1];
			Массив[i - 1] = Замена;			
			i = i - 1;
			Если i = 0 Тогда
				i = j;
				j = j + 1;
			КонецЕсли;			
		КонецЕсли;		
	КонецЦикла;	
	
	Возврат Массив;	
КонецФункции
//---}
 

5. Алгоритм "Сортировка вставками".

Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.


//Сортировка вставками {---
Функция СортировкаВставками(Знач Массив)
	
	Для i = 0 По Массив.ВГраница()-1 Цикл			
		Ключ = i + 1;
		Замена = Массив[Ключ];
		j = i + 1;
		Пока j > 0 И Замена < Массив[j - 1] Цикл
			Массив[j] = Массив[j - 1];
			Замена = j - 1;
			Ключ = j - 1; 
			j = j - 1;
		КонецЦикла;	
	
		Массив[Ключ] = Замена;
		
	КонецЦикла;   
	
	Возврат Массив;	
	
КонецФункции
//---}

6. Алгортим "Сортировка слиянием". 

Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя поэлементно значения подмассивов.

 

p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.

  

//Сортировка слиянием {---

Функция СортировкаСлиянием(Знач Массив)
	
	Если Массив.Количество() = 1 Тогда
		Возврат Массив;
	КонецЕсли;
	
	ТочкаРазрыв = Массив.Количество() / 2;
	
	лМассив = Новый Массив;
	прМассив = Новый Массив;
	
	Для Сч = 0 ПО Массив.ВГраница() Цикл
		Если Сч < ТочкаРазрыв Тогда
			лМассив.Добавить(Массив[Сч]);
		Иначе
			прМассив.Добавить(Массив[Сч]);
		КонецЕсли;
	КонецЦикла;
	
	Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив));
	
КонецФункции

Функция Слияние(массив1,массив2)
	
	a = 0;
	b = 0;
	слМассив = Новый Массив;
	
	Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл
		слМассив.Добавить();
	КонецЦикла;
	
	Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл    		
		Если b <  массив2.Количество() И a < массив1.Количество() Тогда			
			Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда
				слМассив[i] =  массив2[b];
				b = b + 1;
			Иначе
				слМассив[i] =  массив1[a];
				a = a + 1;
			КонецЕсли; 			
		Иначе
			Если b < массив2.количество() Тогда
				слМассив[i] = массив2[b];
				b = b + 1;
			Иначе
				слМассив[i] = массив1[a];
				a = a + 1;
			КонецЕсли;			
		КонецЕсли;
				
	КонецЦикла;	
	
	Возврат слМассив;
	
КонецФункции   
//---}
 

7. Алгортим "Сортировка Шелла". 

 Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.

Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)

10,2,3,1,14,5,7,12

2. Шаг = 2 
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12) 

3,1,7,2,10,5,14,12

3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.

 1,2,3,5,7,10,12,14 


//Сортировка Шелла {---
Функция СортировкаШелла(Знач Массив)
	
	Шаг = Цел(Массив.Количество()/2);
	
	Пока Шаг > 0 Цикл
		i = 0;
		Пока i < (Массив.Количество() - Шаг) Цикл
			j = i;
			Пока j >= 0 И Массив[j] > Массив[j + Шаг] Цикл
				Замена = Массив[j];
				Массив[j] = Массив[j + Шаг];
				Массив[j + Шаг] = Замена;
				j = j - 1;
				
				Если ПрименитьОтображениеСортировки Тогда	
					ОтобразитьДиаграммуСортировки(Массив);	
				КонецЕсли;
				
			КонецЦикла;				
			i = i + 1;	
		КонецЦикла;
		Шаг = Цел(Шаг/2);
		
		ОбработкаПрерыванияПользователя();
	КонецЦикла;
	
	Возврат Массив;
	
КонецФункции   
//---}

8. Алгортим "Быстрая сортировка". 

Наиболее популярный и применяемый алгоритм на практике. Является одним из самых эффективных алгоритмов сортировки данных.
Вся суть алгоритма сводится к тому, чтобы разбить сложную задачу на маленькие и решить их по отдельности. Выбирается некая опорная точка и все значения которые меньше перебрасываются влево, все остальные вправо. Далее для каждой полученной части выполняетя тоже самое, до тех пор пока дробить части уже нельзя. В конце мы получаем множество отсортированных частей, которые необходимо просто склеить в 1 целое.  

 //Алгоритм "Быстрая сортировка" { 
Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел)
      
	
    i    = НижнийПредел;
    j    = ВерхнийПредел;
    m    = Массив[Цел((i+j)/2)];
	
	Пока Истина Цикл        
        Пока Массив[i] < m Цикл            
            i    = i + 1;                   
		КонецЦикла;
		
        Пока Массив[j] > m Цикл            
            j    = j - 1;                   
        КонецЦикла; 
        
        Если i > j Тогда                       
            Прервать;                        
        КонецЕсли;
        
	КонецЦикла;
	
    Если НижнийПредел < j Тогда         
        б_Сортировка(Массив,НижнийПредел,j);        
	КонецЕсли; 
	
    Если i < ВерхнийПредел Тогда                      
        б_Сортировка(Массив,i,ВерхнийПредел);        
    КонецЕсли;
    
КонецПроцедуры

Функция БыстраяСортировка(Массив)
	
	НижняяГраница = 0;
	ВерхняяГраница = Массив.ВГраница();	
	б_Сортировка(Массив,НижняяГраница,ВерхняяГраница);
	
	Возврат Массив;
	
КонецФункции
 //---}

9. Классическая сортировка массива в 1с. 

Передаем массив в список значений. Сортируем стандартным методом "Сортировать". 

//Сортировка списком значений {---
Функция СортировкаСпискомЗначений(Знач Массив)
	
        мСписокЗнч = Новый СписокЗначений;
        мСписокЗнч.ЗагрузитьЗначения(Массив);
	мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр);	
	Возврат мСписокЗнч.ВыгрузитьЗначения();
КонецФункции
//---}


Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.


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

-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:) 

- Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.

Скачать файлы

Наименование Файл Версия Размер
СортировкаМассива

.epf 11,25Kb
58
.epf 11,25Kb 58 Скачать

Специальные предложения

Вознаграждение за ответ
Показать полностью
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Поручик 4619 19.10.13 01:08 Сейчас в теме
Где бы их ещё применить для 1С. Взял на заметку, может где понадобится.
2. Yashazz 4477 20.10.13 11:02 Сейчас в теме
Всю жизнь полагал, что в 1С применяется или быстрая, или шелловская сортировка. Интересно, что там на самом деле. Автор, делались ли замеры скорости, насколько метод списка значений выигрывает?
3. Ekovichev 790 20.10.13 13:38 Сейчас в теме
Мне думается, что в 1с используется быстрая сортировка. Сравнения делались между сортировкой списком и быстрой сортировкой. Разница в сортировке массива размерностью 10 000 и значениями диапазоном от 0 до 100 при сортировке списком значений и быстрой сортировкой вообще незаметна. А вот на массиве размерностью 100 000 диапазон значений от 0 до 1000, сортировка списком значений показала результат около 2-3 секунд, а быстрая в среднем 6-7 секунд.
4. Поручик 4619 20.10.13 14:51 Сейчас в теме
(0) Вижу исправили. Вчера Был перебор массива в функции СортировкаСпискомЗначений(). Хотел написать, но отвлёкся.

мСписокЗнч = ЗагрузитьЗначения(Массив);
5. Ekovichev 790 20.10.13 15:01 Сейчас в теме
Да, вчера сам перечитал статью и заметил, понял, что не стоит писать по ночам)
6. hame1e00n 522 20.10.13 18:48 Сейчас в теме
Полезная информация, спасибо!
7. EliasShy 48 21.10.13 06:38 Сейчас в теме
Хорошо было бы написать жадность алгоритмов в нотации большого О.
8. Ekovichev 790 21.10.13 06:42 Сейчас в теме
Хорошо, добавлю в статью
9. PowerBoy 3237 21.10.13 07:52 Сейчас в теме
Очепятки:
Если Массив[i-1] - по убыванию
i = j;
j = j + 1;
Иначе



Если ij Тогда
Прервать;
КонецЕсли;

10. Ekovichev 790 21.10.13 08:11 Сейчас в теме
Исправил, спасибо за замечание
11. juntatalor 62 21.10.13 14:23 Сейчас в теме
Мне приходилось использовать "свою" сортировку для сортировки дерева значений на управляемой форме. Уж не помню, чем меня не устраивал метод ДанныеФормыДерево -> ДеревоЗначений -> Сортировка -> ДанныеФормыДерево, но быстрая сортировка на клиенте подошла лучше.
12. mikmike 7 22.10.13 06:14 Сейчас в теме
а метод двоичного дерева?
У меня в свое время была курсовая по методам сортировки.
Так метод двоичного дерева на больших массивах сильно быстрей работает
PS 1C тогда и в проекте не существовало. Алгоритм сложный, рекурсивный, но шустрый на больших массивах.
13. Ekovichev 790 22.10.13 06:33 Сейчас в теме
Да метод бинарного дерева интересен, я его посмотрел, начал писать на 1С и что-то не закончил :) Но если будет интересно, можно и его рассмотреть
18. mikmike 7 23.10.13 06:31 Сейчас в теме
(13) теоритически конечно интересно - у меня в свое время заметный выигрыш получался на массивах из сотен и более элементов. 10 чисел быстрее всего упорядочивает самый простой алгоритм.
Но вот на сколько реальна задача? Приведите кто-нибудь пример из жизни, пожалуйста.
14. ediks 334 22.10.13 16:18 Сейчас в теме
15. KAPACEB.AA 451 22.10.13 21:55 Сейчас в теме
16. KAPACEB.AA 451 22.10.13 21:57 Сейчас в теме
Если не ошибаюсь, в сортировке вставками вместо:


Пока 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;
КонецЦикла;

В таком случае не будет бессмысленного перебора элементов в уже отсортированной части массива.

Пруфлинк
17. Ekovichev 790 22.10.13 22:03 Сейчас в теме
(16) Mu_meson, Вы правы, поправил.
19. пользователь 23.10.13 11:13
Сообщение было скрыто модератором.
...
20. gruk 4 23.10.13 12:27 Сейчас в теме
А вот на массиве размерностью 100 000 диапазон значений от 0 до 1000, сортировка списком значений показала результат около 2-3 секунд, а быстрая в среднем 6-7 секунд.

ИМХО: Дак наверное и не получится "сортировку списком значений" обогнать. Это же функция платформы, а любые самописные алгоритмы требуют время на интерпритацию команд.

Вот еще надо проверить, сколько памяти массив и список отъедают, и может в жизни и пригодиться для обработки очень больших массивов.

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

Но все равно плюсую, познавательно.
21. Ekovichev 790 23.10.13 12:30 Сейчас в теме
(20) gruk, Сделаю, хорошая идея. Насчет времени все ясно, только как замерить потребляемые ресурсы?
24. gruk 4 24.10.13 04:27 Сейчас в теме
(21) Я имел ввиду оценить ресурсы приблизительно. Допустим "Сортировка вставками" потребляет мало, т.к. не нужен доп. массив и используется всего 4 переменных. (Кстати, если сделать процедуру и работать не со Знач массив, а со ссылкой, то ресурсов потребуется в 2 раза меньше.) Экономия ресурсов - 5. А "Сортировка слиянием" создает новые массивы. Экономия - 3.
Почему я заговорил про ресурсы, пишу програмку, там использую 2-х мерные большие массивы. Комп слабоват. Сортирую через таблицы значений и память подъедает заметно, винда начинает использовать файл подкачки и падает производительность.

Замер памяти я делал так: запускал 1с, консоль программиста, писал код, смотрел потребляемую память через дисп.задач, запускал код(в конце выводил предупреждение, чтоб массив не уничтожился), опять смотрел память.
Результаты с 100 000 элементов от 0 до 65535 такие: Массив ~800 Кб, СписокЗначений ~9,5 Мб, ТаблицаЗначений с одной колонкой ~5,8 Мб. Еще заметил что после массива память освобождается почти сразу, а после списка или таблицы нет (но если запустить второй раз, увеличение потребления памяти уже намного меньше)
25. gruk 4 24.10.13 04:37 Сейчас в теме
(21) насчет времени все просто.

Scr = Новый COMОбъект("MSScriptControl.ScriptControl"); 
Scr.Language = "javascript"; 

ВремяНачалаВыполнения = Scr.Eval("new Date().getTime()");

   //выполнить код

ВремяКонцаВыполнения = Scr.Eval("new Date().getTime()");
ВремяВыполнения = ВремяКонцаВыполнения - ВремяНачалаВыполнения; //время в милисекундах
Показать


Откуда взял, не помню, да простит меня автор.
user1795406; +1 Ответить
22. DAnry 8 23.10.13 13:06 Сейчас в теме
Спасибо. Достаточно полный анализ по узкой теме. Однозначно +
23. Evil Beaver 7824 23.10.13 14:54 Сейчас в теме
Еще бы неплохо написать, какой именно алгоритм скрывается за 1С-овским "СортироватьПоЗначению()". Сейчас уже не найду, но вроде бы где-то проскакивало в сети, что там qsort, т.е. быстрая сортировка.
26. Ekovichev 790 24.10.13 06:42 Сейчас в теме
Как будет время проведу тест и в таблице опубликую. Замер времени вы взяли отсюда http://infostart.ru/public/71130/ :)
27. CagoBHuK 32 25.10.13 14:20 Сейчас в теме
Однозначный плюс за труд.
29. Ekovichev 790 25.10.13 15:10 Сейчас в теме
(28) kasper076, Я тоже сегодня на хабре прочел, заинтересовался:)
30. mikhailovaew 127 28.11.13 12:47 Сейчас в теме
эх, где тут ildarovich, он бы еще каждый алгоритм оптимизировал с ускорением работы в 5 раз )
31. saver77 34 06.03.14 15:29 Сейчас в теме
Спасибо за проделанную работу. Имею два предложения по быстрой сортировке:
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,ВерхнийПредел);        
    КонецЕсли;
    
КонецПроцедуры
Показать
Артано; 🅵🅾️🆇; Ekovichev; +3 Ответить
32. tarasenkov 339 20.06.14 12:46 Сейчас в теме
В коде процедуры быстрой сортировки забыли важную часть:
       Если i <= j Тогда               
            Замена       = Массив[i];
            Массив[i]    = Массив[j];
            Массив[j]    = Замена;
            i            = i + 1;
            j            = j - 1;            
        КонецЕсли;

(Обработку скачал, там этот код есть)
user1286487; AlexDiablo; Астиг; 🅵🅾️🆇; Фаршик; Ekovichev; +6 Ответить
45. Астиг 18 25.02.19 15:36 Сейчас в теме
(32) А я смотрю на быструю сортировку, и не понимаю, где же тут обмен элементами то?))
33. JohnConnor 61 22.12.14 07:43 Сейчас в теме
однозначна нужная вещь, для изучения алгоритмов
34. Sasha25 26.12.14 11:24 Сейчас в теме
Ну прямо таки даже и не знаю что и сказать. Наверное конечно фундаментальными знаниями нужно владеть
35. pakill 43 20.01.15 03:30 Сейчас в теме
Когда-то, еще до нашей эры (ДОС, Паскаль) придумал метод сортировки: "разноской по значению" и для сравнения написал маленькую демо-програмку.
Прикрепленные файлы:
SORTDEMO.EXE
SORTDEMO.PAS
SORTSHOW.PAS
DoctorRoza; +1 Ответить
36. DoctorRoza 03.02.15 11:11 Сейчас в теме
Отмечусь, может пригодится! Хотя .. обрабатывать в 1С Массив(), да еще и большим количеством элементов .. в какой задаче такое возможно? :)
37. AlexO 132 03.02.15 11:16 Сейчас в теме
(36) DoctorRoza,
в какой задаче такое возможно?
Например, в задаче, где в массив запихнута огромная ТЗ ))
38. platon_ 10 21.08.15 16:59 Сейчас в теме
В Алгоритм "Гномья сортировка".
Упущена часть кода в первом условии
Если Массив[i-1]  < Массив[i]
unknownDaemon; +1 Ответить
39. sadiv 21 31.08.16 19:55 Сейчас в теме
Добавил управляемую форму.
Прикрепленные файлы:
СортировкиМассиваУпр.epf
40. mark_oilbass 19.05.18 15:54 Сейчас в теме
Отличная статья! Спасибо автору)
41. пользователь 22.06.18 17:17
Сообщение было скрыто модератором.
...
42. 1Cnik) 22.06.18 17:42 Сейчас в теме
У вас в алгоритме вставками вроде как ошибка, проверьте на маленьких массивах, в теле цикла
Пока 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] = Замена;
				
	КонецЦикла;
Показать
43. 1Cnik) 24.06.18 18:08 Сейчас в теме
Так же в быстрой сортировке в теле
Если 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 Тогда                       
            Прервать;                        
        КонецЕсли;
Показать
44. vlakur1 04.11.18 10:31 Сейчас в теме
.Алгоритм "Сортировка выбором" можно добавить -1 во внешний цикл

Для i = 0 По Массив.ВГраница() Цикл -1
.....
46. user1355753 07.07.21 21:31 Сейчас в теме
Пример работы с массивом документов.
В списке выделили несколько накладных и хотите их распечатать по дате (масив содержит ссылки на РН)
если в массиве происходит хоть одна перестановка, то после окончания перебора,
перебор стартует еще раз. Перестановок не было - цикл заканчиваеться.

&НаСервере
Процедура ПечатьСписком(ТабДок,ТабДок_счета, ПараметрКоманды)
	
кол_док = ПараметрКоманды.количество();	
не_сортирован=Истина;	
пока не_сортирован цикл
	тд=0; не_сортирован=ложь;
	
пока тд<кол_док-2 цикл
если ПараметрКоманды[тд].дата>ПараметрКоманды[тд+1].дата тогда
темп_док = ПараметрКоманды[тд+1]; 	
ПараметрКоманды[тд+1] = ПараметрКоманды[тд];
ПараметрКоманды[тд] = темп_док;
не_сортирован = Истина;
КонецЕсли;
тд = тд+1;
КонецЦикла;

КонецЦикла;  // массив отсортирован

	Документы.РНОпт_БН.ПечатьСписком(ТабДок,ТабДок_счета,ПараметрКоманды);
КонецПроцедуры
Показать
47. TyurinArt 72 28.09.22 18:00 Сейчас в теме
Начал изучать алгоритмы, предлагаю быструю сортировку математика Хоара через рекурсию без замены:

Функция б_Сортировка(Массив)
	
	Если Массив.вграница() = -1 Тогда
		Возврат Массив;
	КонецЕсли;	
		
    сред = Массив[Цел(Массив.ВГраница()/2)];
	
	мин = Новый Массив();

	макс = Новый Массив();
	
	отсортированный = Новый Массив();	
	
	Для Каждого н из Массив цикл
		
		Если н < сред Тогда 
			мин.Добавить(н);
		ИначеЕсли н > сред Тогда
			макс.Добавить(н);
		Иначе
			отсортированный.Добавить(н);
		КонецЕсли;
		
	КонецЦикла;
	
	Возврат ОбъеденитьМассивы(ОбъеденитьМассивы(б_Сортировка(мин), отсортированный), б_Сортировка(макс));	

КонецФункции


Функция ОбъеденитьМассивы(Приемник, Источник)
	
	Для Каждого н Из Источник Цикл 	
		Приемник.добавить(н);
	КонецЦикла;
	
	Возврат Приемник;
	
КонецФункции
Показать
Оставьте свое сообщение

См. также

Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    1164    gzharkoj    11    

15

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    2924    fishca    12    

32

Установка отбора по списку значений при открытии формы выбора справочника из реквизита обработки

Математика и алгоритмы Платформа 1С v8.3 Конфигурации 1cv8 Россия Бесплатно (free)

Описан алгоритм установки отбора по списку значений при открытии формы выбора справочника. Параметром отбора является список значений передаваемый из одной формы обработки в другую форму этой же обработки. Тестировано под платформу 8.3.18

11.12.2021    5785    prog1c_vl    4    

3

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    4918    dusha0020    8    

62

Работа с 1С:Аналитика Промо

Онлайн-курс предусматривает изучение возможностей системы “1С:Аналитика”, которая работает как составная часть платформы “1С:Предприятие” и обеспечивает оперативный просмотр и анализ необходимых данных.

4500 рублей

Распределенные алгоритмы РИБ 1С

Математика и алгоритмы Обмен между базами 1C Платформа 1С v8.3 Бесплатно (free)

Небольшое исследование на тему применимости классических распределённых алгоритмов репликации и синхронизации данных между узлами обмена РИБ 1С.

02.07.2021    2017    zhichkin    1    

8

Параллельная обработка очереди сообщений

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Описание алгоритма обработки очереди последовательных сообщений регистрации изменений записей регистра сведений. Алгоритм может быть применим к любым объектам метаданных. Алгоритм основан на обработке объектов по их ключам.

15.06.2021    4027    zhichkin    11    

22

Чем воспользоваться для распознавания котиков в 1С?

Математика и алгоритмы Языки и среды Платформа 1С v8.3 Бесплатно (free)

На митапе по инструментам для расширения возможностей 1С выступил Олег Филиппов. Он сравнил подходы Native API, COM, Docker и Serverless, и рассказал, как упростить использование в 1С алгоритмов, реализованных на других языках, с помощью облачной технологии «Функция как сервис».

12.04.2021    4649    comol    10    

29

Эффективные приемы разработки

Математика и алгоритмы Рефакторинг и качество кода СКД Платформа 1С v8.3 Бесплатно (free)

На Infostart Meetup Ekaterinburg.Online выступил Сергей Наумов – руководитель центра аналитики и консалтинга WiseAdvice. Сергей поделился с коллегами приемами разработки, которые помогут избежать потенциальных проблем при реализации сложных проектов.

07.04.2021    5082    SergeyN    13    

39

1СПАРК РИСКИ. Сервис оценки благонадежности контрагентов. Промо

СПАРК помогает предотвратить мошенничество со стороны компаний и предпринимателей, благодаря актуальным сведениям о компаниях и системе выявления факторов риска.Сервис позволяет управлять налоговыми рисками и комплексно оценивать благонадежность контрагентов.

Рекурсия для начинающих

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Рассмотрен подход к пониманию рекурсий. Приведены примеры из реальной практики.

10.02.2021    10082    szv    5    

13

Самый быстрый FizzBuzz на 1С

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Давайте попробуем найти самое быстрое решение задачи "BuzzFizz" на 1С.

03.02.2021    1872    Donrad    23    

11

Программное создание корректировочного счета-фактуры выданного в УПП 1.3

Математика и алгоритмы Механизмы типовых конфигураций Запросы Платформа 1С v8.3 1С:Управление производственным предприятием Россия Бухгалтерский учет НДС Бесплатно (free)

Данный функционал можно использовать, например, в процессе оформления возвратов от поставщика (корректировка реализации по согласованию сторон) при автоматическом создании корректировок реализации по документам поставщика, он позволяет массово создать корректировочные счета-фактуры в УПП 1.3. При создании документа из первичного счета-фактуры выданного в новый корректировочный счет-фактуру выданный копируются значения свойств.

17.12.2020    1158    ksnik    0    

2

Параллельные вычисления расчета факториала числа N

Математика и алгоритмы Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Распараллеливание алгоритма с помощью фоновых заданий (асинхронные вычисления)

29.06.2020    5380    RustIG    18    

25

Программы для исполнения 488-ФЗ: Маркировка товаров Промо

1 января 2019 года вступил в силу ФЗ от 25.12.2018 № 488-ФЗ о единой информационной системе маркировки товаров с использованием контрольных (идентификационных) знаков, который позволяет проследить движение товара от производителя до конечного потребителя. Инфостарт предлагает подборку программ, связанных с применением 488-ФЗ и маркировкой товаров.

Treemapping — способ визуализации данных древовидной структуры. Карта-схема дерева

Математика и алгоритмы Работа с интерфейсом Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Предлагается ознакомиться с редким способом графического представления иерархических данных. Приводится алгоритм формирования и пример реализации.

18.02.2020    8279    randomus    20    

75

Сравнение адресов: случай из практики

Математика и алгоритмы Универсальные функции Платформа 1С v8.3 Россия Бесплатно (free)

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

04.01.2020    5203    AnatolPopov    7    

22

[После]Новогодние задачи

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Совсем немного времени осталось до того момента, когда отзвучат куранты, шампанское будет выпито, мандарины съедены, и даже оливье закончится. Возникнет вопрос: чем бы занять неожиданно появившееся свободное время?

30.12.2019    3988    Alxby    23    

9

30 задач. Странных и не очень

Математика и алгоритмы Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

30 задач на знание языка программирования 1С и некоторого поведения платформы. Маленьких. Странных и не очень.

02.12.2019    38469    Infostart    63    

160

Видеокурс-практикум: как подготовить и написать ТЗ, ЗНР, ЧТЗ. Промо

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

3 500 рублей

Иерархия без "В ИЕРАРХИИ"

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Говорится о том, как эффективно представлять иерархию в СУБД, как получать и использовать эти представления при решении задач в запросной технике. Уточняются и дополняются запросы из статьи "Уровни, глубина, прародители, циклы и аналоги запросом" [https://infostart.ru/public/160707/].

22.08.2019    18998    ildarovich    24    

181

Побитовые операции "на пальцах"

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Простой пример для понимания того, как это работает.

02.08.2019    5139    nbeliaev    16    

8

Обработчики событий при записи объектов. Зачем и что за чем?

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Программисту, имеющему немного опыта на платформе 1С 8.3, бывает сложно разобраться: ПередЗаписью, ПриЗаписи, ПослеЗаписи, на сервере, на клиенте, в модуле формы, в модуле объекта.... Эта шпаргалка была создана в процессе обучения и реального опыта с целью разложить всё по полочкам, чтобы было четкое понимание в каком случае какой обработчик нужно использовать и в какой последовательности они запускаются при записи и проведении документов. Данная статья будет полезна в большей степени начинающим разработчикам. Но и опытным позволит освежить информацию, упорядочить её.

25.07.2019    188360    AlbinaAAA    50    

722

FizzBuzz на 1С. Чем короче, тем веселее. Варианты принимаются...

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Мне было скучно, я не мог себя заставить написать ничего полезного. И читал статью на Хабре. Потом я читал комментарии, а потом... нет я не ушел смотреть котиков на ютюбе. Я решил сделать несколько решений задачки FizzBuzz на 1С, с целью "чем короче, тем лучше". Прошу сильно не пинать, это просто развлечение для вечера.

24.07.2019    6631    vandalsvq    19    

11

Что делает "В ИЕРАРХИИ" в запросе?

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Описание действий платформы 1С при использовании конструкции "В ИЕРАРХИИ" в запросах.

16.07.2019    71162    Infostart    34    

128

Готовые переносы данных из различных конфигураций 1C Промо

Рекомендуем готовые решения для переноса данных из различных конфигураций 1C. C техподдержкой от разработчиков и гарантией от Инфостарт.

Создание отчетов с помощью СКД - основные понятия и элементы

Математика и алгоритмы Платформа 1С v8.3 Система компоновки данных Бесплатно (free)

Основные принципы работы СКД. Понятия схемы компоновки и макета компоновки. Описание основных элементов схемы компоновки: наборы данных, поля, вычисляемые поля, ресурсы, параметры.

25.06.2019    99411    ids79    32    

331

Реализуем Стек, Очередь и Приоритетную очередь в 1С

Математика и алгоритмы Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 Россия Бесплатно (free)

В статье рассматриваются способы реализации таких абстрактных структур данных, как стек, очередь и приоритетная очередь, используя готовые типы данных 1С. Выявляются "узкие" места, сложные моменты в реализации и сравнивается скорость работы.

24.06.2019    19217    RonX01    69    

88

Организация хранения промежуточных данных

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Организация хранения промежуточных данных в процедуре сверки.

29.05.2019    5041    scientes    1    

3

Вычисление 200 тысяч знаков числа pi

Математика и алгоритмы Платформа 1С v8.3 Россия Бесплатно (free)

В статье рассматриваются возможности платформы выполнять сверхточные вычисления без использования сложных алгоритмов и внешних компонент на примере вычисления числа pi.

28.05.2019    10989    Oleg_nsk    97    

79

Парсер таблиц по шаблону. Автоматическая корректировка парсера. Представление таблиц в виде графа.

Математика и алгоритмы Работа с интерфейсом Универсальные функции Корректировка данных Платформа 1С v8.3 Конфигурации 1cv8 Россия Бесплатно (free)

Возникла такая задача: нужно нарисовать в макете шаблон таблицы, где расписано какая ячейка за что отвечает, загрузить таблицу из html и сравнить, подходит ли она под шаблон. Если да, то загрузить информацию по правилу из шаблона. Проблема в том, что в html таблица может приходить с ошибками, то есть какие то ячейки совмещены, хотя не должны. Поэтому нужно сделать так, что бы программа понимала, что таблицы похожи и где конкретно ошибки. Соответсвенно, поделил задачу на 3 этапа. 1 - это представление таблицы в виде графа, 2 - сравнение графов, 3 - забор информации. В данной статье пойдет описание пункта 1.

25.04.2019    4657    trim89    5    

24

Распознавание и загрузка документов в 1С Промо

Универсальная программа-обработка для распознавания любых сканов или фото первичных документов в 1С (счета-фактуры, УПД, ТТН, акты и тд). Точность распознания до 98%.

от 11 рублей

Нечёткий поиск. Bitap алгоритм, модификация от Wu-Manber

Математика и алгоритмы Платформа 1С v8.3 Россия Бесплатно (free)

Временами нужен нечёткий поиск в тексте, но не всегда можно использовать внешние компоненты. Данный алгоритм прост, достаточно быстр.

01.04.2019    5789    trim89    10    

48

Решение системы линейных уравнений

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Пример использования объекта Расчет систем линейных уравнений.

25.03.2019    10971    scientes    12    

49

Обсуждение двух задач на пересечение отрезков

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Ищем общее в частностях, или задача о пересечении отрезков.

15.03.2019    7568    scientes    16    

24

Многопоточное восстановление последовательностей

HighLoad оптимизация Математика и алгоритмы Универсальные функции Платформа 1С v8.3 Бесплатно (free)

Универсальный алгоритм многопоточного фонового восстановления любой последовательности.

05.12.2018    17062    _ASZ_    33    

52

Возврат (loop) в Алгоритмах визирования. Бит Финанс

Бюджетирование и планирование Математика и алгоритмы Платформа 1С v8.3 Конфигурации 1cv8 Финансовые услуги, инвестиции Россия Бюджетный учет Бесплатно (free)

В статье рассматривается минимальная доработка конфигурации БИТ Финанс, с сохранением поддержки, для расширения функционала Визирования: Возрат к предидущим точкам алгоритмов. Полезно будет для программистов и специалистов, занимающихся внедрением БИТ Финанс.

07.08.2018    8597    gladky    2    

11

Подборка программ для взаимодействия с ЕГАИС Промо

ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.

Извлечение текстов модулей из внешней обработки 1С

Математика и алгоритмы Платформа 1С v8.3 Россия Бесплатно (free)

Лень в очередной раз сподвигла меня на доработку существующего инструментария. В публикации опишу свой опыт парсинга бинарного файла с данными обычной формы (выгруженного с помощью функционала платформы 1С "Выгрузить в файлы").

28.04.2018    17234    zenechka    6    

28

Преобразование запросов

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Использование математических методов для языка запросов.

15.03.2018    12962    vasilev2015    24    

17

"Взлом" теста "1С:Профессионал" методом машинного обучения

Математика и алгоритмы Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Нейронные сети – не единственная модель, реализующая принципы машинного обучения. Есть еще байесовская модель, которая математически строже и определеннее, поскольку построена на надежном фундаменте теории вероятностей. Применению байесовского вывода к решению интересной теоретической задачи и посвящена данная статья. Слово "взлом" в заголовке использовано для привлечения внимания. Речь идет исключительно о математическом методе, показанном на примере знакомой всем задачи. 

12.03.2018    23080    ildarovich    44    

95

Yep - простая flat-file CMS на OneScript

OneScript Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

В статье рассмотрено создание простейшей flat-file CMS, на основе каркасной конфигурации для web-приложений OneScript, в среде 1С:Предприятие.

1 стартмани

02.03.2018    16712    blackhole321    33    

43

Минимализмы 3

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Очередная серия "минимализмов" [http://infostart.ru/public/306536/, https://infostart.ru/public/460935/]. Также, как и в предыдущих статьях, здесь приведена подборка коротких оригинальных авторских решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

19.02.2018    53716    ildarovich    47    

422