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

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

Разработка - Практика программирования

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

112
Разбор популярных алгоритмов сортировки массивов, реализованных на 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 элементов, иначе состаритесь ждать сортировки:) 

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

112

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

Наименование Файл Версия Размер
СортировкаМассива
.epf 11,25Kb
21.10.13
49
.epf 11,25Kb 49 Скачать

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

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

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



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

10. Ekovichev 626 21.10.13 08:11 Сейчас в теме
Исправил, спасибо за замечание
11. juntatalor 61 21.10.13 14:23 Сейчас в теме
Мне приходилось использовать "свою" сортировку для сортировки дерева значений на управляемой форме. Уж не помню, чем меня не устраивал метод ДанныеФормыДерево -> ДеревоЗначений -> Сортировка -> ДанныеФормыДерево, но быстрая сортировка на клиенте подошла лучше.
12. mikmike 5 22.10.13 06:14 Сейчас в теме
а метод двоичного дерева?
У меня в свое время была курсовая по методам сортировки.
Так метод двоичного дерева на больших массивах сильно быстрей работает
PS 1C тогда и в проекте не существовало. Алгоритм сложный, рекурсивный, но шустрый на больших массивах.
13. Ekovichev 626 22.10.13 06:33 Сейчас в теме
Да метод бинарного дерева интересен, я его посмотрел, начал писать на 1С и что-то не закончил :) Но если будет интересно, можно и его рассмотреть
18. mikmike 5 23.10.13 06:31 Сейчас в теме
(13) теоритически конечно интересно - у меня в свое время заметный выигрыш получался на массивах из сотен и более элементов. 10 чисел быстрее всего упорядочивает самый простой алгоритм.
Но вот на сколько реальна задача? Приведите кто-нибудь пример из жизни, пожалуйста.
14. ediks 329 22.10.13 16:18 Сейчас в теме
15. KAPACEB.AA 22.10.13 21:55 Сейчас в теме
16. KAPACEB.AA 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 626 22.10.13 22:03 Сейчас в теме
(16) Mu_meson, Вы правы, поправил.
20. gruk 3 23.10.13 12:27 Сейчас в теме
А вот на массиве размерностью 100 000 диапазон значений от 0 до 1000, сортировка списком значений показала результат около 2-3 секунд, а быстрая в среднем 6-7 секунд.

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

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

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

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

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

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

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

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

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


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

(Обработку скачал, там этот код есть)
Астиг; 🅵🅾️🆇; Фаршик; Ekovichev; +4 Ответить
45. Астиг 7 25.02.19 15:36 Сейчас в теме
(32) А я смотрю на быструю сортировку, и не понимаю, где же тут обмен элементами то?))
33. JohnConnor 34 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 127 03.02.15 11:16 Сейчас в теме
(36) DoctorRoza,
в какой задаче такое возможно?
Например, в задаче, где в массив запихнута огромная ТЗ ))
38. platon_ 10 21.08.15 16:59 Сейчас в теме
В Алгоритм "Гномья сортировка".
Упущена часть кода в первом условии
Если Массив[i-1]  < Массив[i]
unknownDaemon; +1 Ответить
39. sadiv 19 31.08.16 19:55 Сейчас в теме
Добавил управляемую форму.
Прикрепленные файлы:
СортировкиМассиваУпр.epf
40. mark_oilbass 19.05.18 15:54 Сейчас в теме
Отличная статья! Спасибо автору)
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
.....
Оставьте свое сообщение

См. также

Приватный блокчейн и 1С популярно 5

Статья no Нет файла Бесплатно (free) Практика программирования Блокчейн

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

02.09.2019    1419    mkalimulin    140       

Кодогенерация и метагенерация в 1С 24

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы Разработка

В своем докладе на конференции INFOSTART EVENT 2018 EDUCATION Дмитрий Белозеров рассказал о разработке инструмента, позволяющего программно работать с метаданными 1С и писать скрипты для выполнения тех же действий, которые выполняет разработчик в конфигураторе –  с какими сложностями и нюансами пришлось столкнуться, и что получилось в итоге.

26.08.2019    3922    kirovsbis    28       

Запрос SQL для нахождения самого большого простого числа меньше заданного 6

Статья Программист Нет файла Windows Бесплатно (free) Математика и алгоритмы

Данный запрос MS SQL демонстрирует некоторые возможности MS SQL Server, о которых часто неизвестно большинству программистов 1С. В тексте постараюсь объяснить интерес данного запроса (или скрипта).

16.08.2019    1167    alex_bitti    18       

Интеграция сценарного тестирования в процесс разработки 81

Статья Программист Нет файла Бесплатно (free) Практика программирования Разработка

Разработчик системы «Тестер» Дмитрий Решитко в своем докладе на конференции INFOSTART EVENT 2018 EDUCATION показывает, что процесс тестирования можно очень плотно интегрировать в процесс разработки, что внедрение тестирования – это возможность развития программиста как такового, позволяющая ему упорядочивать ход мыслей и оставаться «в фокусе». Навыки построения процесса кодирования на стыке с тестированием сокращают время на концентрацию, освобождают от страха перед изменениями и улучшают память разработчика.

08.07.2019    4311    grumagargler    7       

Управляй качеством кода 1С с помощью SonarQube 219

Статья Программист Нет файла Россия Бесплатно (free) Практика программирования Разработка

Управляй техническом долгом проектов 1С с помощью SonarQube. В статье рассматривается пример применения SonarQube при разработке.

07.07.2019    15723    olegtymko    191       

Выдержки из книги Чистый код 24

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Недавно я прочитал книгу "Чистый код" Роберта Мартина (Robert Cecil Martin). В ней описываются принципы организации и форматирование исходного кода программы так, чтобы в дальнейшем было легко поддерживать такой код. Эта книга является библией для многих программистов, но вот в среде программистов 1С, к сожалению, не очень распространено чтение подобной фундаментальной литературы. Книга более 400 страниц и так много порой лениво читать, да и времени всегда не хватает. По этому я решил выделить в виде цитирования по разделам самые важные моменты. А также снабдил текст своими примерами кода.

16.05.2019    5490    FreeArcher    82       

Выгрузка документа по условию 5

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Разработка

Что делать, если документы нужно выгружать не все подряд, а по какому-то фильтру: статусу, дате, набору условий... А что если он соответствовал этим условиям, а потом перестал? А если потом опять начал? Такие ситуации заставили попотеть не одного программиста.

25.04.2019    4650    m-rv    2       

Как прикрутить ГУИД к регистру сведений 23

Статья Программист Нет файла v8 Бесплатно (free) Практика программирования Перенос данных из 1C8 в 1C8 Разработка

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

16.04.2019    7161    m-rv    16       

О времени и 1С 206

Статья Программист Нет файла Бесплатно (free) Практика программирования Разработка

Основы и особенности работы со временем в 1С. Как избавиться от боли при работе в разных часовых поясах. Что такое момент времени. И другое.

01.04.2019    14936    YPermitin    57       

Пример создания bridge (http api - tcp) для ККТ "Касса №1" ("К1-Ф") 5

Статья Системный администратор Программист Нет файла Россия Кассовые операции Бесплатно (free) Практика программирования Разработка ККМ

Пример создания bridge (http api - tcp) для ККТ "Касса №1" ("К1-Ф"). Данная статья будет полезна интеграторам, программистам, тем кто работает (интегрирует, разрабатывает) различное ТО либо железки. Версия и релиз технологической платформы не имеет значения.

17.03.2019    2909    dmarenin    0       

Быстрее чем INSERT! BULK-операции и примеры использования 112

Статья Системный администратор Программист Нет файла Бесплатно (free) Производительность и оптимизация (HighLoad) Практика программирования Разработка Внешние источники данных Перенос данных из 1C8 в 1C8

Microsoft SQL Server поддерживает так называемые BULK-операции, используемые для быстрого изменения больших объемов данных в базе. В статье пойдет речь о практических примерах их использования. Все примеры сделаны в контексте платформы 1С (а как иначе).

09.03.2019    9548    YPermitin    38       

Как писать понятные коммиты 67

Статья Программист Нет файла Россия Бесплатно (free) Практика программирования Разработка

Как писать сообщения коммитов так, чтобы потом не было мучительно больно.

06.03.2019    7761    Scorpion4eg    34       

Что такое алгоритм? 5

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Как ответить на этот вопрос и не попасть пальцем в небо.

25.02.2019    2848    mkalimulin    272       

Расширяем свой багаж 2

Статья Программист Нет файла Бесплатно (free) Практика программирования Разработка

Алгоритм решения возможной нетиповой задачи на собеседовании.

29.01.2019    3251    scientes    15       

Криптовалюты, а также иные взгляды на природу денег в терминах 1С 6

Статья no Нет файла Бесплатно (free) Математика и алгоритмы

Это отчасти полемическая статья. Я задумал написать ее как ответ на другую хорошую статью о криптовалютах. Хотелось поспорить с некоторыми утверждениями автора, а ещё больше с некоторыми комментариями. А чтобы текст был более понятным для местной аудитории, я решил использовать, где только возможно, терминологию и практику 1С.

28.01.2019    3543    mkalimulin    89       

Подготовка ребёнка* к ЕГЭ по информатике. Часть четвертая 4

Статья Программист Нет файла Бесплатно (free) Практика программирования Разработка

Решение систем логических уравнений повышенного уровня сложности.

25.01.2019    3013    vasilev2015    0       

Как писать код? Технологии древних цивилизаций, или все новое - это хорошо забытое старое 70

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

23.01.2019    8548    starik-2005    43       

Подготовка ребенка* к ЕГЭ по информатике. Часть вторая 2

Статья Программист Нет файла Бесплатно (free) Практика программирования

Примеры на Паскале. Если сам родитель* - поддержи ! Если сам водила - посигналь !

19.01.2019    3243    vasilev2015    0       

Подготовка к ЕГЭ сына - школьника (по информатике) 9

Статья Программист Нет файла Бесплатно (free) Практика программирования

Примеры на Паскале. Если сам отец - поддержи ! Если сам водила - посигналь !

17.01.2019    3754    vasilev2015    50       

Многоязычное программирование: создание систем с использованием нескольких языков 17

Статья Программист Нет файла Россия Бесплатно (free) Математика и алгоритмы

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

09.01.2019    5514    kalyaka    33       

Размышления о хороших практиках, навеянные одной статьей 12

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Прочитал статью "Ректальное программирование: основы для практикующих 1С-программистов". Статья очень хорошая и своевременная. Но у меня возникло некоторое сомнение. А достаточно ли автор любит и понимает предмет, о котором пишет? Насколько богат его опыт ректального программирования и занимался ли он им вообще? Как человек обладающий многолетним опытом РП, я решил представить вам необходимые дополнения к статье.

21.12.2018    4372    mkalimulin    61       

Ректальное программирование: основы для практикующих 1С-программистов 291

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Одной из самых популярных и зарекомендовавших себя методологий программирования в 1С является так называемое ректальное программирование. Редкий проект внедрения и сопровождения учётных систем на платформе 1С обходится без его использования. Зачастую без знания данной методологии программистам даже бывает сложно найти работу в сфере 1С, потому что работодатели, особенно фирмы-франчайзи, в основном отдают предпочтение классическим, зарекомендовавшим себя методикам, а не новомодным заграничным веяниям.

19.12.2018    30237    for_sale    340       

Быстрая отладка экранных форм документов и справочников 19

Статья Программист Нет файла Бесплатно (free) Практика программирования

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

18.12.2018    4542    milkers    19       

1С + asterisk (автоматический обзвон) часть 1 38

Статья Системный администратор Программист Нет файла Россия Бесплатно (free) Практика программирования WEB Телефония, SIP

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

29.11.2018    7140    dmarenin    9       

Развитие 1С программиста 50

Статья Программист Нет файла Бесплатно (free) Практика программирования Личная эффективность

Делюсь своим опытом и видением развития 1С программиста.

17.10.2018    13344    pashamak    62       

Вспомогательные инструкции в коде 1С 104

Статья Программист Нет файла v8 1cv8.cf Бесплатно (free) Практика программирования

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

15.10.2018    20202    tormozit    100       

Записки про metadata.js 53

Статья Программист Нет файла Бесплатно (free) Практика программирования

Отличительные особенности разработки на metadata.js

31.07.2018    9037    1c-intelligence    59       

Учебный курс. Повышение качества разработки. Ошибки программы 96

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы Рефакторинг и качество кода

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекции № 3,4,5. Эти лекции посвящены ошибкам программ, их классификации и способам исправления

10.07.2018    15657    Артано    90       

Автоматизируй это! 148

Статья Системный администратор Программист Нет файла Бесплатно (free) Практика программирования

Здравствуйте. Меня зовут Виталий Онянов. Я работаю в компании ФТО. Мы занимаемся внедрением и поддержкой ERP-систем, в том числе и на 1С. Сегодня я хотел бы поделиться нашим опытом автоматизации своих задач и рассказать о том, какие регламентные задания мы настраиваем на серверах наших клиентов. Возможно, кому-то покажется, что это совсем простые и очевидные вещи, но я в своей работе периодически вижу разработчиков, которые делают какие-то задачи руками изо дня в день, и мне бы хотелось донести до них мысль о том, что многие из этих задач можно и нужно автоматизировать.

02.07.2018    16010    Tavalik    12       

Как сделать запрос на изменение данных 75

Статья Программист Нет файла v8 v8::Запросы 1cv8.cf Бесплатно (free) Практика программирования

В статье приведены особенности внутренней архитектуры и примеры работы с расширением языка запросов 1С.

01.06.2018    21013    m-rv    21       

Що там у них в Java 19

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

Развенчание мифа о тяжёлой жизни не 1С программистов на примере создания веб сервиса редактирования таблички с использованием framework spring в Java.

24.05.2018    9132    van_za    62       

Учебный курс. Повышение качества разработки. Вводная лекция, часть 2 49

Статья Программист Нет файла Бесплатно (free) Практика программирования Математика и алгоритмы

Учебный курс по теории и практике программирования. Бесплатно. В виде структурированного текста. Лекция №2. Эта лекция посвящена абстракциям, их свойствами и практическому применению в рамках классических парадигм программирования.

24.05.2018    10623    Артано    36       

Учебный курс. Повышение качества разработки. Вводная лекция 116

Статья Программист Нет файла Бесплатно (free) Математика и алгоритмы

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

10.05.2018    15501    Артано    51