Сайт о телевидении

Для этого мы можем использовать следующую процедуру, которая физически упорядочивает записи файла используя при этом N перестановок:

Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности - одни лучше, другие хуже.

Свойство 6 Оболочечная сортировка никогда не делает более чем N 1.5 сравнений для вышеуказанной последовательности h.

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

В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a 1 £ a 2 £ …£ a m и b 1 £ b 2 £ …£ b n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c 1 £ c 2 £ …£ c m + n .

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

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

Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой

B: 27, 13, 18, 7

A: 27, 16, 13, 11, 18, 25, 7

Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат

B: 27, 13, 18, 7

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

B: 16, 27,’ 18, 25

A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7

B: 16, 27,’ 18, 25

A: 11, 13, 16, 27,’ 7, 18, 25

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

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

Есть очевидное усовершенствование метода. Результат слияния сразу распределяется на две ленты, то есть в процессе участвуют уже 4 ленты. За счет дополнительной памяти число операций перезаписи уменьшается вдвое. Это однофазный четырехленточный метод, называемый также сбалансированным слиянием.

Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log 2 n, а общее число пересылок M пропорцинально n log 2 n.

Метод простого слияния не дает какого-либо выигрыша в тех случаях, когда файл A полностью либо частично отсортирован. Этот недостаток отсутствует в методе естественного слияния.

Назовем серией последовательность элементов a i , a i +1 , …, a j , удовлетворяющих соотношениям a i -1 > a i £ a i +1 £ …£ a j > a j +1 . В частных случаях серия может находиться в начале или конце последовательности.

Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами.

B: 17, 25, 41, ‘6

A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44

C: 9, 11, ‘ 3, 5, 8, 44

A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44

D: 3, 5, 6, 8, 44 C:

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

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

Program SortSlian;

{ 3-ленточная, 2-фазная сортировка естественным слиянием }

{ ключи целые и положительные }

Type elem=record

{ другие поля }

tape=file of elem;

Name: string; { имя исходного файла }

Procedure Vvod(var F: tape);

While K <> -1 do

Write("Введите очередной ключ (конец -1): ");

if K<>-1 then Write(F, S)

Procedure Pech(var F: tape);

While not eof(F) do

Write(S. Key," ")

Procedure CopyElem(var X, Y: tape;

var Buf: elem; var E: boolean);

{ копирование элемента и считывание следующего

{ в Buf с проверкой конца серии (E=True) }

if not Eof(X) then Read(X, Buf)

else Buf.Key:=-1; { барьер: достигнут конец файла }

E:=(Buf.Key

Procedure CopySer(var X, Y: tape; var Buf: elem);

{ копирование серии из X в Y }

{в начале Buf-первый элемент текущей серии на X }

{в конце Buf-первый элемент следующей или –1 (конец X) }

if Buf.Key>0 then { файл X не считан }

CopyElem(X, Y, Buf, E)

Until E { E=True в конце серии }

Procedure Raspred;

{ распределение A ---> B и C }

Read(A, S); { первый элемент из A }

Rewrite(B); Rewrite(C);

CopySer(A, B, S); {S-первый элемент следующей серии }

if S.Key>0 then { файл A скопирован не весь }

CopySer(A, C, S)

Until S.Key<0

Procedure Slian;

{ слияние B и C--->A }

E1, E2: boolean;

Procedure SlianSer;

{ слияние серий из B и C ---> A }

{ S и T - первые элементы серий }

{ S.Key<0-весь файл B считан, T.Key<0-файл C считан }

E1:=False; E2:=False;

if (S.Key>0) and ((S.Key

{ файл B не считан и текущий элемент B меньше, чем в C либо файл C полностью считан }

CopyElem(B, A, S, E1);

if E1 then { достигнут конец серии на B }

CopySer(C, A, T)

CopyElem(C, A, T, E2);

if E2 then { достигнут конец серии на C }

CopySer(B, A, S)

Begin { начало Slian }

if not (Eof(B) or Eof(C)) then

begin { оба файла не пусты }

L:=0; { счетчик числа серий }

While (S.Key>0) or (T.Key>0) do

Begin { начало основной программы }

Write("Введите имя файла для записи элементов: ");

Assign(A, Name);

Assign(B, "Rab1");

Assign(C, "Rab2");

L:=0; { L - число серий после слияния - параметр }

WriteLn("Файл A: "); Pech(A);

Raspred; { фаза распределения }

WriteLn("Файл B: "); Pech(B);

WriteLn("Файл C: "); Pech(C);

ReadLn; { пауза }

Slian { фаза слияния }

Until L<=1; { L=0, если исходный файл отсортирован }

WriteLn("Файл A в конце: ");

Close(B); Erase(B); { удаление рабочих файлов }

Close(C); Erase(C);

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

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

На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент.

Пусть при соединении лент B и C на ленту A серии на B заканчиваются раньше. Тогда лента B объявляется выходной, а лента A становится входной. Процесс продолжается до нового повторения ситуации, когда серии на одной из входных лент заканчиваются. Многофазная сортировка возможна и при многопутевом слиянии. Например, при использовании в сортировке k лент можно постоянно иметь одну выходную ленту. При исчерпании серий на одной из k-1 входных лент эта лента становится выходной вместо предыдущей выходной ленты.

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

МЕТОДЫ СОРТИРОВКИ

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

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

Пример. Отсортировать элементы одномерного массива целых чисел по возрастанию.

На рисунке 1 приведена последовательность перестановки элементов.

Рисунок 1. Сортировка методом «пузырька»

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

На рисунке 2 приведена блок-схема рассмотренного алгоритма.

Рисунок 2. Блок-схема алгоритма сортировки методом «пузырька»

Переменная m введена для возможности обмена значениями между двумя переменными, k отвечает за шаги сортировки.

Программа на языке С++ по данному алгоритму будет выглядеть следующим образом.

Рисунок 3. Программа сортировки элементов массива методом «пузырька»

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

Более эффективным является метод прямого выбора

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

Затем эта процедура повторяется, но поиск минимального (максимального) значения происходит уже со второй позиции и т.д. Схема этого алгоритм представлена на рисунке 4.

сортировка значение программный обеспечение

Рисунок 4. Сортировка методом прямого выбора

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

// сортируем элементы массива по возрастанию

int temp;//переменная для временного хранения при обмене значениями

int i;//переменная управления циклом (номер элемента массива)

int k;//переменная управления циклом (номер шага сортировки)

int nmin;//номер минимального значения

for (к=0; i < к 1; i++)

// ищем номер минимального элемента среди значений list [ i … n -1]

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

if (list[i] < list[ nmin ]) nmin = i;

//меняем местами list[ nmin ] и list[ k ]

temp = list[ nmin ];

list[ nmin ]= list[ k ];

list[ k ] = temp;

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

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

Введение.

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

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

1. Задачи сортировки.

1.1.Общие положения.

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

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

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

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

Считаем, что тип элемента определен как INTEGER .

Constn=???; //здесь указывается нужная длина массива

Var A: array of integer;

Выбор INTEGER до некоторой степени произволен. Можно было взять и

другой тип, на котором определяется общее отношение порядка.

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

1.2. Постановка задачи сортировки массивов.

Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес. Мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть C – число необходимых сравнений ключей и M – число пересылок (перестановок) элементов. Эти числа суть функции от n – числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n*logn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n2 сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:

1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

2. Программы этих методов легко понимать, и они коротки.

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

Методы сортировки “ на том же месте “ можно разбить в соответствии с определяющими их принципами на три основные категории:

· Сортировки с помощью включения (byinsertion).

· Сортировки с помощью выделения (byselection).

· Сортировка с помощью обменов (byexchange).

Теперь мы исследуем эти принципы и сравним их. Все программы оперируют массивом а.

Constn=<длина массива>

a: array ofinteger;

2. Методы сортировки массивов.

2.1. Простые методы сортировки массивов.

2.1.1. Сортировка с помощью прямого включения.

Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а

ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.

I,J,N,X:INTEGER;

A:ARRAY OF INTEGER;

WRITELN(‘Введите длину массива’);

WRITELN(‘Введитемассив’);

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO

WHILE X

WRITELN("Результат:");