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

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

Например,

inta[5] = {9, 33, -23, 8, 1}; // а [0] = 9, а [1] = 33, а [2] = - 23, а [3] = 8, а [4] = 1;

floatb[10] = {1.5, -3.8, 10}; // B [0] = 1.5, b [1] = - 3.8, b [2] = 10, b [3] = ... = b [9] = 0;

Все операции с массивами выполняются с помощью операторов цикла. Например, ввод информации в массив:

for (inti = 0; i<n; i ++)

cin>> a [i];

Вывод информации из массива:

for (int i = 0; i<n; i ++)

cout<<a [i] << "";

Для многих структур данных изображения в виде одномерного массива является неприемлемым. Например, результаты матчей футбольного чемпионата удобнее подавать в виде квадратной таблицы. Для хранения таких структур данных применяют многомерные массивы, среди которых наиболее широко используются двумерные массивы (матрицы).[6]

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

Многомерный массив объявляется в программе следующим образом:

<тип><имя_массива> [<размерность1>] [<размерность2>] ... [<размерностьN>];

Количество элементов массива равна произведению количества элементов по каждому индексу. Например,

int a [3][4];

объявлено двумерный массив из 3-х строк и 4-х колонок (12-ти элементов) целого типа:[5]

a [0] [0] a [0] [1], a [0] [2], a [0] [3],

a [1] [0], a [1] [1], a [1] [2], a [1] [3],

a [2] [0], a [2] [1], a [2] [2], a [2] [3];

Приведем еще несколько примеров объявления массивов:

float Mas1 [5] [5]; // Матрица 5х5 = 25 элементов вещественного типа.

char Mas2 [10] [3]; // Двумерный массив с 10х3 = 30 элементов символьного типа

double Mas3 [4] [5] [4]; // Трехмерный массив с 4х5х4 = 80 элементов вещественного типа

При объявлении массива можно присваивать начальные значения его элементов, причем необязательно всех, например:[7]

1) int w [3] [3] = {{2, 3, 4}, {3, 4, 8}, {1, 0, 9}};

2) float C [4] [3] = {1.1, 2, 3, 3.4, 0.5, 6.8, 9.7, 0.9};

В первом примере объявлено и инициализирован массив целых чисел w[3][3]. Элементам массива присвоено значение из списка: w[0][0] = 2, w[0][1] = 3, w[0][2] = 4, w[1][0] = 3 и т.д.

Во втором разделе описаны практические приемы использования циклических операторов языка программирования С++, а именно:[3]

---

–оператор for;

• оператор while;
• оператор do…while.

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

3.Алгоритмы сортировки данных

3.1. Описание популярных алгоритмов сортировки

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

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

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

Внешний цикл контролирует общее количество срабатываний для внутреннего цикла.[13]

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

Рассмотрим блок-схему алгоритма сортировок пузырьком.

Рисунок 6 – Блок-схема алгоритма сортировки пузырьком

Сортировка слиянием — алгоритм сортировки, что упорядочиваетмассивы в определённом порядке. Сортировка слиянием — хороший пример применения принципа «разделяй и властвуй». [11]

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

Для решения задачи этапы выглядят так:[7]

1. Сортируемые массивы разбиваются на две части одинакового размера;
2. Каждая из частей сортируется отдельно;
3. Два упорядоченных массива половинного размера соединяются.

1.1. — 2.1. Рекурсивное разбиение задачи происходит до тех пор, пока размер не достигнет единицы.

3.1. Соединение двух массивов в один.

Основную идею слияния отсортированных массивов можно объяснить на примере. Если мы имеем 2 уже отсортированных по подмассива. Тогда:

3.2. Слияние 2 подмассивов в третий массив.

На каждом шаге берём меньший из 2 первых элементов подмассивов, записываем его в окончательный массив. Счётчики номеров элементов окончательного массива и подмассива увеличиваем на 1.[9]

---

3.3. «Прицепление» остатка.

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

Рассмотрим блок-схему алгоритма сортировок слиянием.

Рисунок 7 – Блок-схема алгоритма сортировки слиянием

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

3.2.Сортировка массива с помощью слияния без копирования

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

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

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

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

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

---

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

Рекурсивная программа предусматривает сортировку файла Ь, а результат сортировки помещается в файл а. Следовательно, рекурсивные вызовы сформулированы таким образом, что их результаты остаются в файле Ь, и мы применяем программу 2.1 для слияния файлов, помещенных в b с файлом из а, а их результаты остаются в файле а. Таким образом, все перемещения данных выполняются в процессе слияния.

Листинг алгоритма приведен ниже:

template<classItem>

void mergeAB(Item c[], Item a[], int N, Item b[], int M ) {

for (int i = 0, j = 0, k = 0; k < N+M; k++) {

if (i == N) { c[k] = b[j++]; continue; }

if (j == M) { c[k] = a[i++]; continue; }

c[k] = (a[i] < b[j]) ? a[i++] : b[j++];

}

}

template <class Item>

void mergesortABr(Item a[], Item b[], int l, int r) {

if (r-l <= 10) { insertion(a, l, r); return; }

int m = (l+r)/2;

mergesortABr(b, a, l, m);

mergesortABr(b, a, m+1, r);

mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);

}

Результат программы показан ниже:

Рисунок 8 – Результат сортировки

В третьем разделе детально рассмотрены самые популярные методы сортировки элементов массива: метод пузырька и метод слияния (с копированием и без него); приведены блок-схемы указанных алгоритмов, а также и программная реализация на языке программирования С++.

ЗАКЛЮЧЕНИЕ

Наиболее распространенным языком программирования в течение нескольких последних десятилетий, вне всякого сомнения, является язык С++, на основе которого "выросли" многие современные языки программирования и программные среды.

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

Программировать на С ++ можно как для Windows, так и для Unix, причем для каждой из операционных систем существует значительное количество средств разработки: от компиляторов до мощных интерактивных сред, как, например, Borland С ++ Builder, MicrosoftVisual C ++ или VisualStudio .NET.

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

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

– электронные магазины (сортировка товаров по стоимости и другим критериям;

---