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

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

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

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

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

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

114

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

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

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

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

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



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

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

(Обработку скачал, там этот код есть)
Астиг; 🅵🅾️🆇; Фаршик; Ekovichev; +4 Ответить
45. Астиг 10 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 128 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С популярно 6

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

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

02.09.2019    2081    mkalimulin    140       

Онлайн-интенсив "Бизнес-процессы для подготовки к экзамену 1С:Специалист по платформе" 12 декабря 2019 г. Промо

На интенсиве будут рассмотрены все теоретические вопросы, связанные с устройством механизма бизнес-процессов – это необходимо для успешной сдачи экзамена 1С:Специалист по платформе. Также, в качестве практического примера, будет решена задача, аналогичная экзаменационной.

777 рублей

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

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

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

26.08.2019    4849    kirovsbis    28       

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

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

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

16.08.2019    1713    alex_bitti    18       

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

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

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

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

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

08.07.2019    5186    grumagargler    7       

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

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

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

07.07.2019    20230    olegtymko    201       

Вакансия Автор новостных обзоров на тему 1С и бухучета, По совместительству Промо

Редакция Infostart.ru будет рада сотрудничеству с 1С-специалистом, умеющим и любящим излагать свои мысли в письменной форме. Если вы работали в IT-изданиях или имеете опыт ведения технологического блога/канала/группы, если сможете сделать обзор обработок из каталога infostart.ru/public/all/, то у вас большое преимущество.

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

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

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

16.05.2019    6317    FreeArcher    82       

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

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

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

25.04.2019    7571    m-rv    2       

Новый раздел на Инфостарте - Electronic Software Distribution Промо

Инфостарт напоминает: на нашем сайте можно купить не только ПО, связанное с 1С. В нашем арсенале – ESD-лицензии на ПО от ведущих вендоров: Microsoft, Kaspersky, ESET, Dr.Web, Аскон и другие.

  • Низкие цены, без скрытых платежей и наценок
  • Оперативная отгрузка
  • Возможность оплаты с личного счета (кешбек, обмен стартмани на рубли и т.п.)
  • Покупки идут в накопления для получения скидочных карт лояльности Silver (5%) и Gold (10%)

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

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

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

16.04.2019    10077    m-rv    16       

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

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

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

01.04.2019    18775    YPermitin    60       

Программы для исполнения 54-ФЗ Промо

С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.

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

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

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

17.03.2019    3548    dmarenin    0       

Перенос данных БП 3.0 => УТ 11 / КА 2 / ERP 2 (ЕРП) (перенос остатков, документов и справочной информации из "1С:Бухгалтерия предприятия 8", ред.3.0). Обновлено до БП 3.0.73.х, УТ 11.4.10.х, КА 2.4.10.х., ERP 2.4.10.х! Промо

Переносятся документы за выбранный период, справочная информация и остатки по счетам бух. учета в программу УТ 11 / КА 2 / ЕРП 2 (ERP). Переносятся все возможные виды операций ввода остатков на нужную дату. Есть отбор по периоду переноса документов и фильтр по организации, доступен выбор даты ввода остатков. Если нужно переносить что-то дополнительно, то обычно бесплатно добавляем это в перенос . Смотрите видеодемонстрацию со звуком - советами по переносу и рекомендациями настройки программ.

29700 руб.

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

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

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

09.03.2019    12002    YPermitin    38       

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

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

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

06.03.2019    8606    Scorpion4eg    35       

Онлайн-курс "Технология выполнения проектов ERP-класса – процессный подход". Третий поток. Курс проходит с 21 января по 18 марта 2020 года. Промо

Курс разработан Внедренческим центром «Раздолье». Курс предназначен для подготовки аналитиков, архитекторов и руководителей проектов автоматизации процессов управления с использованием комплексных ИТ-систем (1С:ERP, 1С:УХ, 1С:КА, 1С:УТ). В основе курса лежит методика применения процессного подхода.

9000 рублей

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

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

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

25.02.2019    3541    mkalimulin    274       

С 2020 года сервис «Продление поддержки конфигурации 1С:УПП» подорожает вдвое Промо

Успейте продлить поддержку УПП до повышения цен! Фирма «1С» предупредила об изменении цен на сервис «Продление поддержки конфигурации "1С:Управление производственным предприятием"». С 1 января 2020 года сервис подорожает в два раза.

Очный семинар по регулярному менеджменту Александра Фридмана "Вы или Хаос", 12 декабря 2019 г. , Санкт-Петербург Промо

Семинар по регулярному менеджменту от Александра Фридмана для собственников, первых лиц и топов. Технология управленческого планирования, комплексного управления временем и другими ресурсами, выполнением поручений, делами, информацией, контактами (встречи-звонки-почта).

от 11000 до 29000 рублей

Перенос данных КА 1.1 => ERP 2 (ЕРП) (обработка переноса документов, остатков и справочной информации из "1С:Комплексная автоматизация, ред. 1.1" в "1С:ERP Управление предприятием, ред 2"). Обновлен до КА 1.1.115.х и ERP 2.4.10.х Промо

Обработка позволяет переносить из КА 1.1 в ERP 2 документы за выбранный период и остатки. Типовая обработка от фирмы 1С документы не переносит. Также исправлены ошибки типовой обработки. При выходе новых релизов обновление высылается бесплатно в течение года. Разработка будет полезна фирмам-франчайзи, которые периодически выполняют такой перенос данных для заказчиков. Вы можете один раз приобрести обработку переноса, и потом бесплатно получать обновления в случае выхода новых релизов конфигураций 1С.

29700 руб.

Перенос данных КА 1.1 / УПП 1.3 => БП 3.0 (перенос остатков, документов и справочников из "1С:Комплексная автоматизация 1.1" / УПП 1.3 в "1С:Бухгалтерия 3.0"). Обновлен до версий КА 1.1.115.х, УПП 1.3.127.х! Промо

Разработка позволяет перенести остатки по всем счетам бух.учета в программу "1С:Бухгалтерия предприятия 8", ред. 3.0 на выбранную дату начала ведения учета. Также переносятся документы за период и вся необходимая справочная информация. Правила оперативно обновляю при выходе новых релизов. Рассылка обновлений правил бесплатно в течение 12 месяцев. Есть видеодемонстрация проведения переноса данных. Конфигурации при использовании обмена остаются полностью типовыми. Перенос данных возможен в Бухгалтерию 3.0 версии ПРОФ, КОРП или базовую.

24700 руб.

1С:Предприятие через Интернет. 1С:Fresh Промо

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