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

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

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

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

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

Структура массива является однородной. То есть, массив может состоять из компонентов типа real. integer или char, или других пользовательских типов данных. [13]

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

Стоит отметить, что в одномерном массиве (векторе) элементы нумеруются с помощью одного индекса. Индекс ячейки массива – не является содержимым. А содержимым являются данные, хранимые в ячейках, а индексы лишь указывают на них. [9]

В памяти ПК элементы массива располагаются последовательно. Каждый индекс массива находится в диапазоне «начальный элемент – конечный элемент).

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

Массив в языке С++ – это сложный тип данных, определяется следующем методом.

<тип данных> переменная[размерность];

Например,

int a[100];

char s[22];

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

Массивы бывают таких видов:[15]

1. Одномерные, в котором каждый элемент получает один индекс (например, а[2]).

2. Многомерные, в котором каждый элемент получает 2 и более индексов (с[1,1,k]).

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

Для работы с двумерными массивами используют обращение а[i][j]. Для инициализации массива используют запись:[1]

int a[100][100].

В памяти ПК двумерный массив представляется точно так же как и одномерный, только он использует два индекса.

2.3. Понятие динамического массива

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

В С ++ существует несколько команд для выделения динамической памяти. Чаще всего используется оператор new, который в общем виде записывается как:

<Тип> * <имя_указателя> = new <тип>;

Например:

1) int * p = new int;

Здесь выделяется место в памяти под целое число и адрес этого участка памяти записывается в переменную-указатель p. Обратиться к этому числу можно будет через указатель на него *p = 2;

2) int * p = new int (5);

Эта команда не только выделит место в памяти под целое число, но и запишет в эту ячейку памяти значение 5. Адрес первой ячейки выделенного участка памяти присваивается переменной-указателе p. Обратиться к числу, на которое указывает p, можно аналогично предыдущему примеру. Например, чтобы увеличить такое число на 2, следует написать: (* p) + = 2;[9]

3) int * p = new int [5];

В этом случае выделяется память под 5 целых чисел, то есть фактически создается так называемый динамический массив из 5-ти элементов. Обратиться к каждому из этих цифр можно по его номеру: p[0] p[1] и т. д. или через указатель *p - то же именно, что p [0]; *(P + 1) - то же самое, что p[1] и т.д.

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

delete <указатель>;

Например:

delete a;

Если оператором new было выделено память под несколько значений одновременно, используется форма команды delete [9]

delete [] <указатель>;

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

Кроме операторов new и delete, существуют функции, которые перешли к С ++ с С, но они используются на практике гораздо реже.

Функция void * malloc (size_t size) (от англ. "Memory allocation" - выделение памяти) делает запрос к ядру операционной системы о выделении участка памяти заданного количества байтов. Единственный аргумент этой функции size - количество байтов, которое нужно выделить. Функция возвращает указатель на начало выделенной памяти. Если для размещения данного количества байтов недостаточно памяти, то функция malloc() возвращает NULL.[3]

Содержание участка остается неизменным, то есть там может остаться "грязь", если аргумент size равен 0, функция возвращает NULL. Например, команда

int * a = (int *) malloc (sizeof (int));

выделяет память под целое число и адрес начала этого участка памяти записывает в указатель а.[2]

Выделение памяти под 10 действительных чисел с помощью этой функции:[3]

float * a = (float *) malloc (sizeof (float) * 10)

Функция

void * calloc (size_t num, size_t size)

выделяет блок памяти "памяти размером num х size (под num элементов по size байтов каждый) и возвращает указатель на выделенный блок. Каждый элемент выделенного блока инициализируется нулевым значением (в отличие от функции malloc). Функция calloc () возвращает NULL, если не хватает памяти для выделения нового блока, или если значение num или size равны 0.[3]

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

Например, вещественный массив 3 × 5 сохраняется в пам "яти следующим образом:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

0-ю строчка

1-я строка

2-я строка

В таком массиве первые пять элементов относятся к первой строке, следующие пять - ко второй и последние пять - к третьему.[7]

Напомним, что a - указатель на начало массива, то есть на элемент a[0][0]. Чтобы обратиться, например, к элементу a[1][3], следует "перепрыгнуть" от начала массива через 5 элементов нулевого строки и 3 элемента первого столбца, то есть написать * (a + 1 * 5 + 3) . В общем случае к элементу a [i] [j] можно обратиться следующим образом: * (a + i * 5 + j). Но этот способ работы с двумерным массивом не слишком удобен, так как в программе при обращении к элементу массива приходится преобразовывать указатель и вычислять индекс элемента.[7]

3.Сортировка массивов

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

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

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

• Сравнение элементов;
• Перестановка;

– Собственно сортирующий алгоритм.

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

Время сортировки считается пропорциональным количеству сравнений и числа перестановки элементов.

3.1.1.Метод пузырька

Идея рассматриваемого метода отражена в его непосредственном названии.

Заметим, что самые легкие элементы массива будут "всплывать" наверх, при этом самые "тяжелые" – тонуть.

Последовательность из N компонентов просматривается от самого первого элемента до конца так, чтобы стоящие рядом объекты менялись местами, если же первый из них будет меньше ("легче") второго (рисунок 12). Таким образом, после указанного просмотра самый "легкий" или «тяжелый» объект "выталкивается" в конец массива.[6]

Рисунок 12 – Пример сортировки пузырьком

Если повторить теперь такой просмотр еще ровно N – 1 раз, то вся заданная последовательность элементов окажется от сортированной.

3.1.2. Сортировка выбором

Один из простейших методов сортировки работает так: находим наименьший объект в массиве и сразу обмениваем его с объектом находящимся первым.

Далее повторяем процесс с второй позиции в файле, а найденный элемент обмениваем с вторым объектом и т.д.

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

Рисунок 13 – Пример сортировки выбором

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

3.1.3.Сортировка вставкой

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

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

Такой процесс реализован на рисунке 14.

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

Рисунок 14 – Пример сортировки вставкой

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

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

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