Вход на сайт

Научные направления

Поделиться:

Статьи из раздела: ПРИМЕНЕНИЕ НЕЙРОННЫХ СЕТЕЙ В МОБИЛЬНОМ ПРИЛОЖЕНИИ ДЛЯ ДИАГНОСТИКИ АРТРИТА КИСТЕЙ РУК

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

Статья опубликована в №68 (апрель) 2019
Разделы: Информационные технологии
Размещена 26.04.2019. Последняя правка: 26.04.2019.
Просмотров - 2201

ИССЛЕДОВАНИЕ И КЛАССИФИКАЦИЯ МЕТОДА СОРТИРОВКИ РАСЧЕСКОЙ

Акимова Елена Владимировна

Доцент, к.э.н.

Санкт-Петербургский горный университет

Доцент

Ряскова К.А., студентка 1 курса Санкт-Петербургского горного университета

Аннотация:

в статье рассмотрен метод сортировки расческой, ее классифицирование, анализ и исполнения программы, с использованием языка программирования Visual Basic. Описано выполнение и преимущества неустойчивой сортировки расческой, приведены примеры тестирования программы на различных данных.

Abstract:

The article describes the method of sorting the comb, its classification, analysis and execution of the program using the internal programming language Visual Basic. The implementation and advantages of unstable sorting by a comb are described, examples of program testing on various data are given.

Ключевые слова:

метод сортировки; сортировка расческой; Visual Basic; листинг программы

Keywords:

sorting method; comb sort; visual basic; program listing

УДК 004.424.5

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

Актуальность. Не смотря на широкое распространение специализированных пакетов, в отдельных отраслях промышленности в Российской Федерации, большую популярность имеют универсальные программные средства, такие как, например, программы пакета MS Officce. В том числе, например, в нефтегазовой сфере остаётся популярным использование MS Excel. Однако не все задачи можно решить стандартными средствами MS Excel, в связи с чем пользователи могут создавать собственные библиотеки макросов, используя встроенный язык VBA. В связи с этим разработка и анализ алгоритмов являтся актуальной и востребованной задачей.
Цели, задачи и методы. Среди множества алгоритмов определенный интерес представляют алгоритмы сортировки и поиска, т.к. использование стандартных средств не всегда удобно. В данной работе рассмотрен метод сортировки расческой и его реализация в среде VBA.
Научная новизна состоит в подходе к реализации метода средствами VBA.
Сортировка расчёской (англ. comb sort) — это достаточно упрощённый алгоритм сортировки, первоначально спроектированный Влодзимежом Добосевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991 г. Сортировка расчёской доводит до совершенства сортировку пузырьком, и соперничает с методами, подобными быстрой сортировке. В сортировке пузырьком, если сравниваются 2 компонента, промежуток (расстояние друг от друга) равен 1. Главная концепция сортировки расчёской в том, что данный промежуток способен быть значительно больше.

Главная идея «расчёски» в том, для того чтобы первоначально брать довольно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива ограничивать это расстояние вплоть до наименьшего. Подобным способом, как бы причёсывая массив, со временем разглаживая на всё наиболее аккуратные пряди.

Начальный разрыв между сравниваемыми элементами правильнее взять с учётом специальной величины, называемой фактором уменьшения, наилучшее значение которой равно приблизительно 1,247.

Сперва расстояние между компонентами равно размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). Потом, пройдя массив с этим шагом, следует поделить шаг на фактор уменьшения и пройти по списку снова.

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

Оптимальное значение фактора уменьшения:
1/(1-e^-`phi`)=1,247...

Где – e основание натурального логарифма, а `phi` – золотое сечение.

Худшее время: O(n²)

Лучшее время: O(n log n)

Листинг программы, реализующей метод сортировки расческой:

Private Sub CombSort()
Dim i As Integer, j As Integer, Temp As Integer
Dim gap As Single
Dim swapped As Boolean
Dim a() As Variant

n = Int(InputBox("Размер массива:", "Колличество элементов", 2))
ReDim a(1 To n)
For i = 1 To n
    Max = 100
    Min = -100
    a(i) = Int((Max - Min + 1) * Rnd() + Min)
Next

Cells(1, 1).Resize(1, n) = a
gap = n - 1
Const Shrink = 1.3
Do
    gap = Int(gap / Shrink)
    For j = 1 To n - gap
        If a(j) > a(j + gap) Then
            Temp = a(j)
            a(j) = a(j + gap)
            a(j + gap) = Temp
        End If
    Next j
Loop Until Not swapped And gap = 1

Cells(2, 1).Resize(1, n) = a
End Sub

Пользователь вводит размер массива и устанавливает минимальный (min) и максимальный (max) пределы для случайного числового ряда. Затем, этот массив выводится на лист в Microsoft Excel.

Фактор уменьшения шага (Shrink) принимаем за 1.3, и выводим первое значение нашего расстояния (Gap), равное длине массива, деленной на фактор уменьшения, и округленного до ближайшего целого. Затем после каждой итерации растояние снова делится на фактор, округляется, и так пока оно не станет равным 1.

Работу начинает сам цикл сортировки, начиная с 1 до n-го элемента. Происходит сравнение значения второго элемента (i=1) с (1+Gap), если a(j) < a(j+Gap), то значение первого элемента остается в памяти как наименьшее и элементы 1 и 2 поменяются местами.

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

Результаты тестирования метода сортировки расческой на различных данных:

Количество элементов: 20

Промежуток: [-20;20]

Тип данных: Integer

Время менее 0,001 секунды

Таблица 1 – Время работы сортировки расческой.

Количество элементов	Элементы выбраны на промежутке	Тип данных	Время (с)
500	[-500;500]	integer	0,005
2000	[-500;500]	integer	0,013
10000	[-500;500]	integer	0,092

Таблица 2 – Оценка сложности работы алгоритма.

Название метода

Временная сложность

Требуемое количество памяти

В лучшем

В среднем

В худшем

Сортировка расческой

О(n²)

O(n logn)

О(1)

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

Сортировка расческой (Comb sort) относится к алгоритмам неустойчивой сортировки и имеет сложность . Следовательно, можно сделать вывод, что сортировка расческой быстрая и эффективная

Сортировка расческой имеет следующие преимущества: простой код, стабильная сортировка; требуется меньше памяти и времени; основана на сравнении. И имеет следующие недостаток: При сортировке по одному полю данных, состоящих из нескольких полей, не сохраняется взаимное расположение равных элементов.

Библиографический список:

1. Кнут Д.Э. Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с.
2. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — №8. — С. 50-53.
3. Васильев В. С. Алгоритм. Свойства алгоритма [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/578 (дата обращения 05.04.219).
4. M V Ilinykh, M N Nazarova, E V Akimova, A G Palaev, Assessment of technical condition of underwater transitions of main pipelines in real, IOP: Earth and Environmental Science (EES). 2018

Комментарии пользователей:

Оставить комментарий

E-mail: sci@sci-article.ru
©2013-2023 Электронный периодический научный журнал SCI-ARTICLE.RU
Любое использование размещённых на сайте журнала статей и материалов возможно только с обязательной активной ссылкой на сайт журнала «SCI-ARTICLE.RU».

▲
Вверх

E-mail:
Пароль:
Запомнить
	Регистрация/ Забыли пароль?