Учебно-методический комплекс дисциплины «Технология программирования» (стр. 5 )

Пример. Задана последовательность чисел: 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее методом «турнира с выбыванием».

Решение. Начинаем формировать дерево с листьев:

1 этап (в результате получили самое большое число 92. Его следует вывести из дерева.)

2 этап

и т. д.

Реализация сортировки вставками. Алгоритм Шелла.

Если первоначальный файл отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок О(n). Если файл отсортирован первоначально в обратном порядке, то данная сортировка имеет общее число сравнений

(n-1) + (n-2) + … + 3 + 2 + 1 = (n-1)*n/2.

Сортировка простыми вставками лучше, чем сортировка «методом пузырька». Чем ближе файл к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками, рассматривая все возможные перестановки во входном массиве, составляет О(n2). Требования на пространство для этой сортировки состоят только из одной временной переменной, например, Y.

Улучшение сортировки простыми вставками достигается использованием вставок в список. При таком подходе используется массив указателей link, по одному указателю на каждый элемент первоначального массива. Данный массив можно представить как некоторый линейный список, на который указывает некоторый внешний указатель first. Для того чтобы вставить k-й элемент, организуется прохождение данного связанного списка до тех пор, пока не будет найдена нужная позиция для X(k) или пока не будет достигнут конец списка. В этот момент X(k) может быть вставлен в этот список просто при помощи настройки указателей списка без какого-либо сдвига элементов в массиве. Это уменьшает время, требуемое для вставки, но не время, необходимое для поиска нужной позиции. Требование на пространство также возникает из-за дополнительного массива link. Среднее число сравнений по прежнему равно О(n2).

Сортировка Шелла (сортировка с убывающим шагом)

В этом методе в первоначальном файле сортируются отдельные подфайлы. Значение k назовем шагом. Например, если k=5, то первым сортируется подфайл, состоящий из элементов X(1), X(6), X(11) … Пять подфайлов каждый содержащий одну пятую элементов первоначального файла, сортируются аналогичным образом:

Subfile1 Þ X(1), X(6), X(11) …

Subfile2 Þ X(2), X(7), X(12) …

Subfile3 Þ X(3), X(8), X(13) …

Subfile4 Þ X(4), X(9), X(14) …

Subfile5 Þ X(5), X(10), X(15) …

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

Пример. Задана последовательность 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее по возрастанию элементов, используя алгоритм Шелла.

Решение.

Первоначальный файл92 86 33

Просмотр 1, шаг 5:92 86 33

 

Просмотр 2, шаг 3:92 86 48

 

Просмотр 3, шаг 192 86 57

Отсортированный файл57 86 92

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

#include "stdafx. h"

#include <math. h>

#include <iostream>

using namespace std;

#include <conio. h>

void shell (int *, int, int);

int main ()

{

int A[40],I, n; /* Инициализация */

cout<<"Enter n= ";

cin>>n;

cout<<"\n Enter array \n";

for(i=0;i<n;i++) cin>>A[i];

shell(A, n,5); //5 - начальный шаг

cout<<"Result:\n";

for(i=0;i<n;i++) cout<<A[i];

_getch();

return 0;

}

void shell (int * A, int n, int k)

{

for (;k>=1;k--) // для каждого убывающего шага

{

for (int i=0;i<k;i++) // в каждом подфайле

{

for (int j=i;j+k<=n;j=j+k) // выполняем сортировку

{

for (int l=j+k;l+k<=n;l=l+k)

{

if(A[j]>A[l])

{

int X=A[j];

A[j]=A[l];

A[l]=X;

}

}

}

}

}

}

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

Слияние является процессом объединения двух и более отсортированных файлов в некоторый третий отсортированный файл [3]. Мы можем использовать такой подход к сортировке файла следующим образом. Разделим файл на n подфайлов размером 1 и будем объединять соседние (необъединенные) пары файлов. Тогда будем иметь примерно n/2 файлов размером 2. Повторяем этот процесс до тех пор, пока не останется только один файл размером n. Рассмотрим сказанное на примере.

Первоначальный файл (7) (3)

 

Просмотр 1 (25, , 86)

 

Просмотр 2 (25, 37, 48, , 33, 86, 92)

 

Просмотр 3 (12, 25, 33, 37, 48, 57, 86, 92)

Поразрядная сортировка

Этот метод основан на свойстве значений действительных чисел в позиционном представлении сортируемых чисел. Для простоты предполагаем, что все числа имеют одинаковое число цифр, что при необходимости выполняется добавлением незначащих нулей. Предположим, что мы выполняем следующие действия над файлом для каждой цифры, начиная с самой младшей цифры и кончая самой старшей цифрой. Берем каждое число в том порядке, в котором оно появляется в файле, и помещаем его в одну из 10 очередей в зависимости от значения цифры, которая в данный момент обрабатывается. Затем восстанавливаем каждую очередь к виду первоначального файла, начиная с очереди чисел с цифрой 0 и кончая очередью чисел с цифрой 9. Когда эти действия будут выполнены для каждой цифры, начиная с самой младшей и кончая самой старшей, данный файл будет отсортирован. Рассмотрим изложенную процедуру на примере.

Первоначальный файл92 86 33

Очереди, организованные по МЗЦ (младшей значащей цифре)

Очереди	Начало	Конец
0	–
1	–
2	12	92
3	33
4	–
5	25
6	86
7	57	37
8	48
9	–

После первого просмотра: 1237 48

Очереди, организованные по СЗЦ (старшей значащей цифре)

Очереди	Начало	Конец
0	–
1	12
2	25
3	33	37
4	48
5	57
6	–
7	–
8	86
9	92

Отсортированный файл 1286 92

Временные затраты на метод поразрядной сортировки зависят от числа цифр (m) и числа элементов в файле (n). Для того, чтобы сэкономить значительный объем работы при обработке очередей, рекомендуется использовать связанное распределение данных на основе указателей.

2.4. Поиск данных

Введение в поиск данных

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

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

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

Алгоритмом поиска является такой алгоритм, который, воспринимая некоторый аргумент a, пытается локализовать некоторую запись, ключ которой равен а. Данный алгоритм может возвратить всю данную запись или чаще всего может возвратить некоторый указатель на эту запись. Успешный поиск называется извлечением. В противном случае алгоритм может возвратить некоторую специальную «пустую запись» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или установке во флаге некоторого конкретного значения, которое указывает, что данная запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с этим аргументом в качестве ключа. Алгоритм, который выполняет эту функцию, называется алгоритмом поиска и вставки [3].

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

Последовательный поиск

Простейшей формой поиска является последовательный поиск. Этот поиск применяется к таблице, которая организована или как массив, или как связанный список [3].

Предположим, что k есть некоторый массив из n ключей, а r — некоторый массив записей, такой, что k(i) является ключом для r(i). Предположим также, что key является некоторым аргументом поиска. Мы хотим установить в переменную search наименьшее целое число i, такое что k(i) = key, если такое i существует, и 0 в противном случае. Алгоритм выполнения этих действий следующий:

search=0;

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

{

if(key = = k[i]) search = i;

}

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

if( search = = 0)

{

n++; // увеличиваем размер таблицы

k[n] = key // вставляем новый ключ и запись

r[n]= rec;

search = n;

}

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

// key — искомый ключ записи

…

flag=false;

qq=q; // q — указатель на начало списка

i=0; // n — число элементов в списке

while( (flag==false) && (i<=n))

{

i++;

if (qq->key==key)

{

q1=q; // q1 — указатель на искомый элемент

cout<<”Запись найдена\n”;

flag=true;

}

else

{

q2=qq; // q2 – указатель, ссылающийся. ся на qq

qq=qq->next;

}

// вставка элемента zapis с заданным ключом key в начало списка

if (flag==false)

{

item *kon=new kon(next, key, nam); // kon - указатель на ячейку

kon->next=q;

kon->key=key;

kon->nam=zapis;

q=kon;

}

// удаление элемента с ключом key из списка

else

{

q2.next=q1.next;

delete q1;

}

}

…

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

Поиск в упорядоченной таблице

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

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

Для увеличения эффективности поиска в отсортированном файле существует другой метод, но он приводит к увеличению требуемого пространства. Этот метод называется индексно-последовательным методом поиска. В дополнение к отсортированному файлу заводится некоторая вспомогательная таблица, называемая индексом. Каждый ее элемент состоит из ключа kindex и указателя на запись в файле, соответствующую этому ключу pindex. Элементы в таблице index должны быть отсортированы по этому ключу также как и элементы в файле. Рассмотрим пример такого построения [3].

Рис. 2.4.1. Индексно-последовательный файл

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

Пусть kindex будет массивом ключей в индексе, и пусть pindex будет массивом указателей внутри индекса на записи в файле. Пусть данный файл представлен в виде массива, n — размер файла, nindex — размер таблицы индекса; тогда алгоритм может быть представлен следующим фрагментом программы:

// key – искомый ключ записи

…

search=0;

i=1;

while ((i<=nindex) && (kindex[i]<=key)) i:=i+1;

// установить lowlim на наименьшую возм. позиц. в таблице

if (i==1) lowlim=1;

else lowlim=pindex[i-1];

//установить hillim на наиб. возм. позиц. в таблице

if (i==nindex+1) hillim=n; // последний элемент

else hillim=pindex[i];

// поиск в таблице от позиции lowlim по дозиции hilim

for (j= lowlim;j<= hillim;j++)

{

if (k[j]==key )

{

search:=j; cout<<”Элемент найден. Его номер =”<< j;

return;

}

}

…

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

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

Рис. 2.4.2. Использование вторичного индекса

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