Анализ алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим - массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных - θ(n²).

Псевдокод

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:

key := A[i]

j := i - 1

while j > 0 and A[j] > key:

A[j + 1] := A[j]

j := j - 1

A[j + 1] := key

Реализация на С++

void insertionSort(int arr[], int length)

{ int i, j, tmp;

for (i = 1; i < length; i++)

{ j = i;

while (j > 0 && arr[j - 1] > arr[j])

{ tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

j--;

}

}

}

Сортировка слиянием

Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

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

1. Сортируемый массив разбивается на две части примерно одинакового размера;

2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;

3. Два упорядоченных массива половинного размера соединяются в один.

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

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

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

Пример реализации алгоритма сортировки слияния:

// a - сортируемый массив, его левая граница lb, правая граница ub

template<class T>

void mergeSort(T a[], long lb, long ub) {

long split; // индекс, по которому делим массив

if (lb < ub) { // если есть более 1 элемента

split = (lb + ub)/2;

mergeSort(a, lb, split); // сортировать левую половину

mergeSort(a, split+1, last);// сортировать правую половину

merge(a, lb, split, ub); // слить результаты в общий массив

}

}

Ф-ия merge

template<class T>

void merge(T a[], long lb, long split, long ub) {

// Слияние упорядоченных частей массива в буфер temp

// с дальнейшим переносом содержимого temp в a[lb]...a[ub]

// текущая позиция чтения из первой последовательности a[lb]...a[split]

long pos1=lb;

// текущая позиция чтения из второй последовательности a[split+1]...a[ub]

long pos2=split+1;

// текущая позиция записи в temp

long pos3=0;

T *temp = new T[ub-lb+1];

// идет слияние, пока есть хоть один элемент в каждой последовательности

while (pos1 <= split && pos2 <= ub) {

if (a[pos1] < a[pos2])

temp[pos3++] = a[pos1++];

else

temp[pos3++] = a[pos2++];

}

// одна последовательность закончилась -

// копировать остаток другой в конец буфера

while (pos2 <= ub) // пока вторая последовательность непуста

temp[pos3++] = a[pos2++];

while (pos1 <= split) // пока первая последовательность непуста

temp[pos3++] = a[pos1++];

// скопировать буфер temp в a[lb]...a[ub]

for (pos3 = 0; pos3 < ub-lb+1; pos3++)

a[lb+pos3] = temp[pos3];

delete temp[ub-lb+1];

}

28. Организация работы с файлами. Обобщенная технология обработки файловых данных. Типизированные, текстовые и нетипизированные файлы. Объявление и правила использования переменных файловых типов. Вспомогательные операции с файлами.

Файл - именованная область внешней памяти ПЭВМ (жесткого диска, оптического диска, электронного "виртуального" диска), либо логическое устройство - потенциальный источник или приемник информации.

Любой файл имеет три характерных особенности:

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

• Во-вторых, он в основном относится к типизированным файлам (также и к текстовым). Типом компонентов может быть любой тип Турбо-Паскаля, кроме файлов. Иными словами, нельзя создать «файл файлов».

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

Работа с файлами складывается из 4 шагов.

1. размещение в памяти файловой переменной соответствующего типа;

2. Файл открывается. Это означает, что программа "захватывает" заданный по имени файл, сообщает ОС , что далее она будет с ним работать. Данный шаг нужен, чтобы не возникало конфликтов, когда несколько программ одновременно хотят записывать информацию в один и тот же файл. Правда, считывать данные из файла, очевидно, допустимо одновременно множеством программ, поэтому в операции открытия файла обычно уточняется, что файл открывается "на чтение" (считывание информации, которая не меняется) либо "на запись" (данные в файле модифицируются). Операция открытия файла возвращает некий идентификатор (как правило, целое число), которое идентифицирует в программе в дальнейшем нужный открытый файл. Этот идентификатор запоминается в переменной; обычно такая переменная называется файловой переменной.

3. непосредственно обмен информацией Из него данные либо считываются, либо в него записываются.

4. Файл закрывается. После этой операции он снова доступен другим программам для обработки.

Файловый тип или переменную файлового типа можно задать одним из трех способов: < имя > = FILE OF <тип>; < имя > = ТЕХТ; < имя > = FILE; . Здесь < имя > - имя файлового типа или файловой переменной, FILE, OF, TЕХТ - кодовые слова (англ.: файл, из, текст), < тип > - любой тип Турбо-Паскаля, кроме файлов. Пример: Type Man=record Name: string; LastName: string; End; Men=file of Man; Var Staff: Men; Numbers: file of real; Book: Text; A_File: File;

В зависимости от способа объявления можно выделить три вида файлов: • типизированные (задаются предложением FILE OF ...), • текстовые (задаются предложением ТЕХТ), • нетипизированные (задаются предложением FILE).

Следует помнить, что физические файлы на магнитных дисках и переменные файлового типа в программе на Паскале – объекты различные. Переменные файлового типа в Паскале могут соответствовать не только физическим файлам, но и логическим устройствам, связанным с вводом/выводом информации. Например, клавиатуре и экрану соответствуют файлы со стандартными именами Input, Output.

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

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