Файл: Сортировка слиянием без копирования.pdf

ВВЕДЕНИЕ

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

Именно с помощью таких алгоритмов выполняется фундаментальное действие над массивами данных – сортировка.

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

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

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

Кроме этого, все языки программирования (ЯП) нынешнего времени предоставляют в испоьзование встроенные средства по быстрому и досрочному окончанию циклов – операторы перехода, завершения структур циклического типа.

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

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

Целью работы является рассмотрение алгоритма сортировки по убыванию методом вставки.

В соответствии к цели работы поставлены такие основные задания:

– рассмотреть понятие алгоритма и терминологии, которая с ним связана;

– выполнить описание операторов цикла на С++;

– рассмотреть применение массивов в С++, как объекта сортировки;

– рассмотреть основные типы сортировки данных;

– дать характеристику и на практике описать программу для сортировки методом слияния без копирования.

1.Понятие алгоритмов

1.1.Алгоритмы, их свойства

Понятие алгоритма – краеугольный камень многих наук: математики, информатики, физики и других. Отметим, что данное понятие не выражается через какие-то другие термины.

Иными словами, единого какого-то определения для понятия алгоритма вовсе не существует, хотя для его исследования присутствуют разные подходы, что часто могут использоваться для выполнения описания рассматриваемого термина, также в соответствии с данным определенным сектором применимых знаний. [14]

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

В данной четкой последовательности также можно задать инструкции для выполнения разных операций в сформированном разработчиком порядке, правила для их реализации.[5]

Ученые выделяют такие типы основных алгоритмов (рисунок 1): [6]

Рисунок 1 – Классы алгоритмов

Вычислительные алгоритмы – это структуры команд и операций, что являются последовательностями, которые могут обрабатывать простые (числовые) данные (рисунок 2): [13]

Рисунок 2 – Простые типы

Под информационными алгоритмами часто понимаются наборы простых методов, процедур, которые выполняют обработку информации. Фундаментальным примером таких процедур является методика поиска информации. [19]

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

Управляющие типы алгоритмов реализуют самые различные данные, что поступают с внешних подключенных к ним устройствам или они возникают при подключении разных внешних процессов.

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

Любой известный алгоритм обладает основными свойствами (рисунок 3):[13]

Рисунок 3 – Алгоритмические свойства

1. Детерминированность алгоритмов (определенность). Это такое свойство, что может заключаться в задании одинаковых входных параметров для используемого алгоритма, а сам алгоритм будет выполняться полностью одинаково при этом, то есть получаться аналогичный результат при вычислениях. [4]

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

Благодаря такому свойству в применении алгоритмов используется некоторый механический характер информации.[1]

2. Массовость – выражение такого свойства алгоритма, при котором с постоянным использованием алгоритма можно также решать не только одну определенную задачу, а любую из класса стандартных однотипных задач предметной области. [13]

3. Результативность алгоритмов значит, что при выполнении только конкретного алгоритма обязательно будет решена поставленная пользователем задача, либо к сообщениям об указанных исходных ошибочных величинах.

4. Дискретность алгоритма значит, что все алгоритмы используют последовательность этапов – специальные элементарные действия, что непосредственно выполняются и не представляющих какой-то большой сложности.

С помощью рассматриваемого выше свойства алгоритм может быть выполнен с использованием ПК.[1]

5. Конечность алгоритма – рассматриваемая рабочая последовательность специально выполненных действий не может являться неограниченной.

6. Корректность – специальное свойство, что обозначает следующий факт: если алгоритм создан с реализацией описания для какой-то задачи, он должен давать аналогичный правильный результат для абсолютно всех исходных данных. [11]

1.2.Способы описания алгоритмов

Чтобы как-то понять выполнение конкретных алгоритмов их пользователями, они должны быть формализованы по разным определенным критериям.

Все такие методы, которые применяются в этом плане, определяют также квалификацию исполнителей.

К методам записи алгоритмов можно отнести следующие категории (рисунок 4): [1]

Рисунок 4 – Описание алгоритмических структур

Словесная методология может основываться на обработке последовательности разработки для конкретно определенном и указанном векторе действий с использованием самых разнообразных математических символов.[10]

Блок-схемы алгоритма – специфический метод графического изображения выполняемых процессов для выполнения разных задач некоторой последовательностей составных блоков по их характеристике, что отражают определенную специфику их преобразования. [8]

Внутри блоков описывается часто определенный этап решения задачи с помощью алгоритма.

Рассмотрим некоторые фигуры, которые могут применяться для описания (рисунки 5 – 9):[5]

Рисунок 5 – Блок для решения

Рисунок 6 – Процесс вычисления

Рисунок 7 – Линия процесса

Рисунок 8 – Обозначение процесса

Рисунок 9 – Конец, начало алгоритма

Стоит заметить, что для реализации блок-схем применяются часто MS Visio, Dia и другие приложения.[9]

1.3. Понятие о циклических структурах данных

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

Каждый алгоритмический цикл может содержать в себе следующие элементы:

• инициализация счетчика;
• проверка условий цикла;
• выполнение тела;
• изменения переменной.

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

При использовании такой проверки будет выполнено осуществление выбора: повторять еще раз код цикла для рассматриваемого циклического алгоритма или же выполнить другие действия.[15]

В теории алгоритмов различают часто 2 разновидности таких основных алгоритмов:[12]

• циклы с послеусловием;
• циклы с предусловием (рисунок 11).[1]

В циклах предусловием непосредственно условие может формулироваться и для повторного выполнения, пока его проверка будет истинной (рисунок 10). [3]

Рисунок 10 – Структура циклов с предусловием

Для циклов с постусловием выполняются тело сначала цикла, условия выполнения цикла. Сам же циклический алгоритм с постусловием рассмотрен ниже на рисунке 11:[11]

Рисунок 11 – Структура цикла с постусловием

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

2. Применение массивов в программировании

2.1.Реализация циклических алгоритмов в С++

Как было описано в первом разделе, циклические процессы используются, когда нужно вычислить несколько раз какое-то значение по одним и тем же формулам, но с разными значениями переменных, которые изменяются на указанном отрезке с определенным шагом. Как известно, эта переменная – счетчик цикла.[7]

Для реализации циклического процесса в С++ существуют 3 циклических оператора:

1. Оператор цикла с предусловием while. Его интерфейс:[2]

while (логическое_выражение)

{

Тело цикла

}

Если параметр оператора while принимает значение истина, то будут выполнятся операторы тела циклической части. После этого опять проверяется условие и если логическое выражение имеет значение истина – снова выполняется тело цикла.

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

Пример 1.

l=0;

while(l<=5)

{

a=pow(l,2);

cout<<a<<” “;

l++;

}

Описанный в примере алгоритм будет выполняться пока значение переменной l будет меньше равно 5. В противоположном случае произойдет выход с циклического алгоритма.[8]

1. Оператор цикла с послеусловием do … while имеет следующий синтаксис:

do

{

Тело цикла

}

while (логическое_выражение)

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

Пример 2.

с=1;

do

{

p=pow(c,2);

cout<<p<<” “;

c++;

}

Как видно в двух примерах, перед циклическим оператором нужно указать начальное значение счетчика цикла, а в теле цикла указать шаг приращения переменной цикла.[4]

1. Циклический оператор for использует такой синтаксис:

for (инициализация; условие; приращение)

{

Тело цикла

}

Описанный выше оператор часто используется при реализации вычислений в массивах. В нем инициализируется переменная цикла, потом сразу проверяется условие окончания цикла. Если цикл выполняется, то операторы циклической части проводя вычисления, иначе идет переход к операторам, которые следуют за оператором for.[13]

Пример 3.

for(w=1;w<=15;w++)

{

a=pow(w,2);

cout<<w<<" ";

}