Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 4 )

Вычислительная сложность

Место включения найдено, если.

Интервал поиска в конце должен быть равен 1; это означает, что интервал из i элементов делится пополам раз. Число сравнений равно

.

Минимальное число сравнений требуется, когда элементы расположены в обратном порядке, а максимальное, - если они уже упорядочены.

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

Сортировка включениями с убывающим приращением (Шелла)

является усовершенствованием сортировки простыми вставками.

Рассмотрим ее на примере из восьми элементов.

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

В данном примере из восьми элементов каждая группа содержит ровно 2 элемента.

2. Элементы объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново (2-сортировка).

3. На третьем проходе все элементы сортируются обычной сортировкой, или 1-сортировкой.

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

На каждом шаге сортировки либо участвует сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Каждый проход использует результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой.

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

1, 4, 13, 40, 121, ...

где каждый элемент массива h вычисляется по следующей формуле:

,

всего элементов в массиве h - , и последний элемент массива h – h[k-1]=1, т. е. для массива из 10-ти элементов можно задать следующие данные массива h[]={1,4}.

Вычислительная сложность

Затраты, требуемые для сортировки n элементов, пропорциональны n. Это значительное улучшение, однако, - это не самый лучший алгоритм сортировки.

Сортировка с разделением (быстрая сортировка)

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

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

Принцип сортировки:

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

2. На втором этапе повторяются действия первого этапа для правой и левой частей массива в отдельности.

3. На третьем этапе все повторяется для четырех частей массива и т. д.

Для обработки подсписков используется рекурсия.

Вычислительная сложность

Анализ эффективности возможен только при некоторых допущениях.

Допустим, что число элементов массива.

При первом сканировании производится n-1 сравнений. Создаются два подсписка размером n/2.

На следующей фазе обработка каждого подсписка требует примерно n/2 сравнений и т. д.

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

Общее число сравнений приблизительно равно

n*k = n*log2n

Для списка общего вида вычислительная сложность равна.

Сложность худшего случая (когда центральным является наименьший элемент) равна.

Слияние сортированных последовательностей

Существует два упорядоченных списка - A и В, с длинами соответственно M и N. В процессе слияния необходимо получить упорядоченный список С длины M+N.

Выполняется поэлементное слияние.

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

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

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

Алгоритм слияния сортированных последовательностей:

1. Пока не закончится одна или обе последовательности, выполнять следующее:

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

2. Если одна из последовательностей не обработана до конца, то скопировать этот остаток в выходную последовательность.

Лекция №3

Тема: Поиск. Последовательный поиск. Бинарный поиск

Цель: уметь использовать методы поиска при решении задач

Смысл последовательного поиска состоит в последовательном переборе элементов списка и сравнении элементов со значением ключа:

int search(int a[],int n, int key)
{
for (int i=0;i<n;i++)
  if (a[i]==key) return i;
return -1;
}

Функция в качестве параметров использует массив, количество элементов, значение ключа.

Возвращает индекс соответствующего элемента; при неудачном поиске возвращает -1.

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

Средняя эффективность последовательного поиска составляет O(n).

Бинарный поиск

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

Имеем массив из n элементов.

Индексы в концах списка: low=0, high=n-1.

Алгоритм бинарного поиска:

1. Вычислить индекс серединного элемента массива

mid=(low+high)/2.

2. Сравнить значение в серединном элементе с key.

Если совпадение найдено, возвратить индекс mid для нахождения ключа.

Если a[mid]<key, то проводить повторный поиск в правой половине рассматриваемого списка.

Если a[mid]>key, то проводить повторный поиск в левой половине рассматриваемого списка.

3. Если искомый элемент не находится в списке, то возвратить индикатор сбоя.

Пример:

Дан массив целых чисел А. Найти элемент с заданным ключом 33.

low = 0 high = 8 mid = 4 33>A[mid]

low = 5 high = 8 mid = 6 33>A[mid]

low = 7 high = 8 mid = 7 33=A[mid]

При последовательном поиске требуется 8 сравнений.

При бинарном поиске – только три.

Лекция №4. Файлы. Операции с данными на внешних носителях

Цель: Сортировка данных, организованных в виде файлов.

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

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

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

С логической точки зрения записи располагаются в файле последовательно.

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

Внешняя сортировка

Сортировка данных, организованных в виде файлов, называется внешней сортировкой.

Если файл настолько велик, что не умещается в оперативной памяти, то сортировка - большая проблема. Поскольку все данные нельзя хранить в одном массиве, то для их хранения необходимо использовать временные файлы.

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

использует метод простого слияния, который объединяет два упорядоченных списка в один. Главная идея заключается в том, что организуется файл в виде постепенно увеличивающихся серий (элементов), т. е. последовательностей записей r1?r2?…?rn. Например, последовательность целых чисел, организованная сериями длиной 3:

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

Пусть сортируемые элементы хранятся в файле fC, а файлы fA и fB являются временными и служат для разбиения данных.

Алгоритм сортировки:

fC 5 15 35 30 20 45 35 5 65 75 40 50 60 70 30 40 25 10 45 55

1. Разбить fC пополам, попеременно записывая его элементы то в fA, то в fB. Таким образом в каждом новом файле создается последовательность одноэлементных серий.

2. Сопоставить подсписки. Выбрать один элемент из fA и один элемент из fB, объединить их в серию длиной 2, используя алгоритм простого слияния, и записать в fC. Продолжать, пока все элементы не будут скопированы обратно.

3. Повторить шаг 1, попеременно записывая двухэлементные серии файла fC в файлы fA, fB.

4. Попарно слить все двухэлементные серии файлов fA, fB в четырехэлементные серии файла fC (используя алгоритм слияния упорядоченных последовательностей).

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