Маргинальные свойства сортировки массивов методом дихотомической вставки

сортировка быстродействие алгоритм целые числа

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

УДК 681.3.06 Маргинальные свойства сортировки массивов методом дихотомической вставки А.Ф. Деон, Ю.И. Терентьев МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия Выполнен сравнительный анализ маргинальных скоростных свойств сортировки массивов методами последовательной и дихотомической вставки с учетом операций сравнения, сложения, перестановки и запоминания сортируемых элементов в массивах целых чисел. <...> Сортировка массива методом последовательной вставки является не самым быстродействующим способом упорядочивания массивов с произвольными значениями [1], однако, когда массив частично упорядочен, применение этого метода может дать более предпочтительные результаты. <...> Для произвольного исходного массива он позволяет воспользоваться дихотомическим поиском в упорядоченной части массива. <...> Алгоритм возрастающей сортировки методом последовательной вставки полагает, что упорядоченная часть находится в левой части массива, а неупорядоченная — в правой. <...> Пусть начальный элемент a[0] исходного массива a является единственным элементом упорядоченного подмассива в левой части исходного массива. <...> На первом этапе выполняется внешний цикл для правой неупорядоченной части массива. <...> В заголовке цикла for(int j = 1; j < n; j++) до начала итераций настраиваются две операции: 1) установка начального значения int j = 1; 2) начальная проверка условия j < n. <...> Кроме того, на каждой итерации внешнего цикла в заголовке цикла выполняется одна операция на очередную проверку окончания цикла j < n и две операции на увеличение переменной цикла j++: Wn 1,2 = += =1 n j раций: 12 3 1 . <...> 11,1 =+ =W n На втором этапе выполняется проверка на необходимость вставки с помощью инструкции условия if(a[ j–1] < a[ j])continue. <...> На каждой итерации внешнего цикла по индексу j будет выполнено четыре операции на проверку условия a[ j–1] < a[ j]: 2 Маргинальные свойства сортировки массивов методом дихотомической вставки 1 Wn 2 = =44 1 . <...> =1 n j () На третьем этапе происходит поиск <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт