Метод 1. Сортировка выбором
Условно разделить массив А на отсортированную и несортированную части. Сначала весь массив — это несортированная часть.
цикл по i от 1 до N–1 с шагом 1 выполнять
// i – номер первого элемента в несортированной
// части массива
r:= i;
// Найти минимальный элемент в несортированной
// части массива:
цикл по j от i+1 до N с шагом 1 выполнять
если А[j] < A[r] то r:= j;
конец цикла
// Найденный минимальный элемент поменять местами с
// первым элементом несортированной части:
если i r
то Обмен (i, r);
// Он будет последним элементом новой сортированной
// части массива A.
конец цикла
Метод 2. Сортировка простыми вставками
Условно разделить массив A на отсортированную и несортированную части. К сортированной части сначала относится только первый элемент.
цикл по i от 2 до N с шагом 1 выполнять
// i – номер первого элемента в несортированной части
// массива
x:= A[i];
j := i – 1;
// Все элементы из отсортированной части, большие,
// чем x, сдвинуть на одну позицию вправо:
пока j>0 и A[j]>x выполнять
A[j+1] := A[j];
j := j – 1;
конец пока
// Элемент x поставить на свое место по порядку:
A[j+1] := x;
конец цикла
Метод 3(1). Сортировка простыми обменами (метод пузырька)
цикл по i от 2 до N с шагом 1 выполнять
// проход от конца массива к началу:
цикл по j от N до i с шагом -1 выполнять
// если два рядом стоящих элемента нарушают
// порядок по возрастанию, то их поменять местами.
если A[j] < A[j–1] то Обмен(j, j–1);
конец цикла
конец цикла
Метод 3(2). Сортировка простыми обменами (шейкерная сортировка)
Пусть F — логическая переменная, принимающая истинное значение, если во время прохода по массиву были обмены двух рядом стоящих элементов, left – левая граница несортированной части массива, а right – ее правая граница.
left := 1;
right := N;
F := истина;
пока F выполнять
F:= ложь;
i:= left;
//Проход по массиву от начала к концу:
пока i < right выполнять
если A[i] > A[i + 1]
то // переставить два рядом стоящих элемента,
// нарушающие порядок:
начало
Обмен (i, i+1);
F := истина;
конец
i := i + 1;
конец пока
// Сдвинуть правую границу влево на одну позицию:
right := right – 1;
// Если были обмены во время предыдущего прохода,
если F
то // совершить проход по массиву от конца
// к началу:
начало
F := ложь;
i:= right;
пока i > left выполнять
если A[i] < A[i – 1]
то// переставить рядом стоящие элементы,
// нарушающие порядок:
начало
Обмен (i, i–1);
F := истина;
конец
i := i – 1;
конец пока
конец
// Сдвинуть левую границу вправо на одну позицию:
left := left + 1;
конец пока // Цикл повторять до тех пор, пока F не
//останется равной значению ложь.
Метод 4. Сортировка подсчетом
Условно разделить массив A на отсортированную и несортированную части. Пусть i – номер первого элемента в несортированной части массива.
i := 1;
пока i < N выполнять
r:= 1;
// Посчитать количество элементов в массиве, меньших
// i-го элемента и записать это число в переменную r
цикл по j от 1 до N с шагом 1 выполнять
если A[i] > A[j]
то r := r + 1;
конец цикла
если r i // i-й элемент стоит на своем месте,
то // увеличить сортированную часть на 1 элемент
i := i + 1
иначе
начало
// вычислить позицию, куда нужно поставить
// i-й элемент:
пока A[r] = A[i] выполнять
r:= r+1
конец пока
// поменять его местами с тем элементом,
// который в этой позиции находится:
Обмен (r, i)
конец;
конец пока
Язык реализации – С.
Лабораторная работа № 8. Улучшенные сортировки
Задание
Написать программу, которая сортирует массив целых чисел в порядке возрастания с помощью двух методов улучшенной сортировки.
Использовать следующие алгоритмы, описанные в [1, 2]:
быстрая сортировка,
один из алгоритмов по выбору:
сортировка методом Шелла,
пирамидальная сортировка.
Входные данные
Длина массива задается либо в программе константой, либо вводится с клавиатуры. Исходный массив заполняется программой с помощью датчика случайных чисел.
Выходные данные
Нужно выдать на экран элементы исходного массива, а затем с новой строки выдать элементы этого массива после применения к нему алгоритма сортировки
Методы
Ниже будут использоваться обозначения, введенные в описании лабораторной работы № 7.
Метод 1. Сортировка включениями с убывающими приращениями
(метод Шелла)
процедура Вставка(b, h)
// b — номер первого элемента последовательности
// h – величина шага
начало процедуры
// Пусть i – номер первого элемента в несортированной
// части массива.
i := b + h;
пока i N выполнять
x:= A[i];
j := i – h;
пока j b и A[j]>x выполнять
// Все элементы из отсортированной части, большие
// x, сдвинуть на величину шага h вправо,
A[j+h] := A[j];
j := j – h;
конец пока
// Элемент x поставить на свое место по порядку:
A[j+h] := x;
i := i + h;
конец пока
конец процедуры
Основная программа:
// Выбор начального шага:
h := 1;
пока h < N/3 выполнять
h := 3*h + 1;
конец пока
// Сортировка:
пока h 1 выполнять
цикл по i от 1 до h – 1 с шагом 1 выполнять
Вставка (i, h);
h := (h – 1) / 3;
конец цикла
конец пока
Метод 2. Пирамидальная сортировка
В данном методе используется следующая процедура:
процедура Просеивание (i, n)
// i – номер элемента, который нужно просеять
// n – номер последнего элемента массива
начало процедуры
если 2*i <= n
то начало
r := 2*i;
если (r+1 n) и (A[r] < A[r+1])
то r := r + 1;
// i-тый элемент массива ставится на то место,
// где он удовлетворяет свойству пирамиды:
// A[i] max(A[2*i], A[2*i + 1])
если A[i] < A[r]
то начало
Обмен (i, r);
Просеивание (r, n);
конец
конец
конец процедуры
Основная программа:
Шаг 1. Построение пирамиды:
i := N / 2;
пока i 1 выполнять
{ Просеивание (i, N);
i := i – 1;}
Шаг 2. Сортировка на пирамиде:
i := N;
пока i > 1 выполнять
Обмен (1, i);
i := i – 1;
Просеивание (1, i);
конец пока
конец основной программы.
Метод 3. Быстрая сортировка.
процедура Qsort ( left, right)
// left — левая граница сортируемой области
// right – ее правая граница.
начало процедуры
i := left;
j := right;
x := A[(i + j)/2];
// x — пилотируемый элемент, относительно которого
// сортируются все остальные элементы массива:
// в левую часть массива перемещаются все элементы,
// меньшие либо равные x, а в правую — большие
// либо равные x;
пока (i j) выполнять
пока A[i] < x выполнять
i := i + 1;
конец пока
пока A[j] > x выполнять
j := j – 1;
конец пока
если i j
то начало
Обмен (i, j);
i := i + 1;
j := j – 1;
конец
конец пока
// Затем отдельно отсортировать методом быстрой
// сортировки левую и правую части перестроенного
// массива:
если j > left то Qsort(left, j);
если i < right то Qsort(i, right)
конец процедуры
Основная программа:
Qsort(1, n);
конец основной программы
Язык реализации – С.
Лабораторная работа № 9. Сортировка файлов
Задание
Написать программу, которая сортирует файл целых чисел в порядке возрастания.
Использовать один из алгоритмов сортировки файлов слиянием, описанный в [1, 2].
Входные данные
На вход программе подаются имена входного и выходного файлов. Входной файл должен содержать последовательность целых чисел.
Выходные данные
Нужно вывести в выходной файл элементы входного файла, отсортированные по возрастанию.
Метод. Двухпутевое сбалансированное слияние
процедура Слить2в1
( F1, F2, // – входные файлы
F // – выходной файл
n // – длина сливаемых отсортированных
) // цепочек во входных файлах, n > 0
начало процедуры
если не пуст(F1)
то
{ считать(F1, a1);
n1 := 1;
}
иначе n1 := 0;
если не пуст(F2)
то { считать (F2, a2);
n2 := 1
}
иначе n2 := 0;
пока (0 < n1 n) и (0 < n2 n)
выполнять
{ если a1 a2
то {
записать (F, a2);
если ((n2 < n) и не пуст( F2 ))
то { считать (F2, a2);
n2 := n2 + 1;
}
иначе n2 := 0
}
иначе{
записать (F, a1);
если ((n1 < n) и не пуст(F1))
то {
Считать (F1, a1);
n1 := n1 + 1;
}
иначе n1 := 0;
}
}
если n1 = 0
то { записать (F, a2);
пока (n2 < n) и (не пуст(F2)) выполнять
{ считать ( F2, a2);
записать (F, a2);
n2 := n2 +1
}
иначе
{ записать (F, a1);
пока (n1 < n) и (не пуст(F1)) выполнять
{ считать ( F1, a1);
записать (F, a1);
n1:= n1 +1
}
}
процедура Слить2в2
(F1, F2, // – входные файлы
F3, F4 // – выходные файлы
n) // – длина сливаемых отсортированных
// цепочек во входных файлах, n > 0
{ открыть на чтение (F1);
открыть на чтение (F2);
открыть пустой файл на запись (F3);
открыть пустой файл на запись (F4);
пока (не пуст (F1)) или (не пуст (F2)) выполнять
{ Слить (F1, F2, F3, n);
Слить (F1, F2, F4, n);
}
}
Основная программа:
Пусть А — входной файл, B — выходной файл,
F1, F2, F3, F4 — вспомогательные файлы.
n := 0;
пока не пуст(А) выполнять
{ считать (А, a);
записать (F1, a);
n := n + 1;
если не пуст(A)
то { считать (А, a);
записать (F2, a);
n := n + 1;
}
}
k := 1;
пока k < n выполнять
{ слить2в2(F1, F2, F3, F4, k);
k := k * 2;
если k < n
то { слить2в2(F3, F4, F1, F2, k);
k := k * 2;
B := F3
}
иначе B := F1
конец основной программы
Язык реализации – С.
Лабораторная работа № 10. Определение частоты встречаемости символов в файле
Задание
Написать программу, которая подсчитывает частоту встречаемости символов в заданном текстовом файле.
Входные данные
На вход программе подается имя входного текстового файла.
Выходные данные
Нужно вывести в выходной файл или на экран для каждого символа, записанного во входной файл, вещественное число — отношение количества вхождений этого символа в данный файл к длине всего файла.
Метод
Пусть M — линейный массив целых чисел длины 256. Сначала он заполнен нулями.
F — входной файл,
n := 0 — счетчик количества всех символов в файле.
Открыть файл F на чтение.
пока файл F не исчерпался выполнять
{ считать из F очередной символ и записать его в
c,
n := n + 1;
М[c] увеличить на 1.
}
цикл по i от 0 до 255 с шагом 1
если М[i] 0
то выдать строку: символ(i) – значение(M[i]/n);
Язык реализации – Си.
Лабораторная работа № 11. Построение кода Хаффмана
Задание
Написать программу, которая для заданного текстового файла строит код Хаффмана
Входные данные
На вход программе подается текстовый файл.
Выходные данные
Нужно вывести в выходной файл или на экран коды Хаффмана для каждого символа, встречающегося в этом файле.
Метод
Для каждого символа в файле посчитать его частоту встречаемости (лабораторная работа 10).
Построить дерево Хаффмана, используя алгоритм, описанный в [1].
Для хранения вершин дерева предлагается использовать массив T длины 2*N–1, где N — количество кодируемых символов. Элементами этого массива являются записи, состоящие из следующих полей:
символ — кодируемый символ или псевдосимвол,
частота — частота встречаемости данного символа,
код — строка, состоящая из нулей и единиц (код данной вершины дерева
левый,
правый — номера вершин, в результате объединения которых была создана данная вершина
свободный — флаг, обозначающий, была ли использована данная вершина или еще нет
Шаг 0. Записать в массив Т символы в порядке убывания их частот встречаемости. Все вершины дерева пометить как свободные.
К := N; // —текущее количество вершин в дереве
Начальное состояние массива Т для строки “кол около колокола” из [1] представлено в таблице:
№ |
символ |
свободный |
частота |
левый |
правый |
код |
1 |
о |
истина |
|
0 |
0 |
|
2 |
к |
истина |
|
0 |
0 |
|
3 |
л |
истина |
|
0 |
0 |
|
4 |
пробел |
истина |
|
0 |
0 |
|
5 |
а |
истина |
|
0 |
0 |
|
6 |
|
|
|
|
|
|
7 |
|
|
|
|
|
|
8 |
|
|
|
|
|
|
9 |
|
|
|
|
|
|
Шаг 1. Выбрать такие вершины дерева с номерами L и R, что
T[L].свободный = истина И
T[R].свободный = истина
Т[L].частота,
T[R].частота — минимальные из всех свободных вершин.
Создать новую вершину дерева:
K := K + 1;
T[K].свободный := истина;
T[K].частота := T[L].частота + T[R].частота;
T[K].левый := L;
T[K].правый := R;
T[L].свободный := ложь;
T[R].свободный := ложь;
Шаг 2. Если К < 2*N–1 то прейти на Шаг 1
T[К].код:= ””; // — это корень построенного дерева, код его равен пустой строке
Шаг 3.
// конкатенация строк:
T[T[K].левый ] := T[K].код + ”0”;
T[T[K].правый] := T[K].код + ”1”;
K := K – 1;
Шаг 4. Если К > N то перейти на Шаг 3.
В результате для нашего примера получим следующее состояние
массива T:
№ |
символ |
свободный |
частота |
левый |
правый |
код |
1 |
о |
ложь |
|
0 |
0 |
“10” |
2 |
к |
ложь |
|
0 |
0 |
“11” |
3 |
л |
ложь |
|
0 |
0 |
“00” |
4 |
пробел |
ложь |
|
0 |
0 |
“010” |
5 |
а |
ложь |
|
0 |
0 |
“011” |
6 |
|
ложь |
|
4 |
5 |
“01” |
7 |
|
ложь |
|
3 |
6 |
“0” |
8 |
|
ложь |
|
1 |
2 |
“1” |
9 |
|
истина |
|
7 |
8 |
“” |
В результате работы данного алгоритма для каждого элемента массива с номером от 1 до N в поле код будет записана строка, представляющая собой код Хаффмана для соответствующего символа.
Язык реализации – Си.
Лабораторная работа № 12. Архивирование
Задание
Написать программу, которая заданный текстовый файл архивирует методом сжатия по Хаффману.
Входные данные
На вход программе подается текстовый файл и код Хаффмана для этого файла.
Код Хаффмана может быть представлен либо в виде строк, записанных в другом файле, либо в виде дерева Хаффмана (как продолжение лабораторной работы №11).
Выходные данные
Нужно вывести в выходной файл закодированный входной текст.
Метод
Архивный файл состоит из двух частей. В первой части находится информация об исходном файле и таблица кодировки. Во второй части — закодированный текст.
В первой части необходимо указать длину входного файла в байтах и количество различных символов в нем (размер входного алфавита — N).
Таблица кодировки может быть представлена двумя способами.
1) в виде последовательности их N троек <символ, длина кода, код>, где
символ — ASCII код символа входного алфавита (1 байт),
длина кода — количество битов в соответствующем кодовом слове (1 байт),
код — кодовое слово (1 или 2 байта).
2) в виде урезанного представления дерева Хаффмана – 2*N–1 троек <символ, левый, правый>, где
символ — ASCII код символа входного алфавита или 0 для псевдосимвола (1 байт),
левый — номер левого сына в дереве для данной вершины (1 байт),
правый — номер правого сына в дереве для данной вершины (1 байт).
Кодирование основного текста можно представить в виде следующей последовательности действий.
Пусть нам дано дерево Хаффмана, построенное в лабораторной работе №11.
Шаг 0.
b := 0;
i := 0;
Шаг 1. Считать их входного файла в переменную c очередной символ.
Найти такое k, что Т[k].символ = с, 1 k N.
s := T[k].код;
L := длина(s);
j := 1;
пока j L выполнять
{ i := i + 1;
если S[j]=’1’
то setbit(&b, i);//i-му биту в b присвоить 1
если i = 8
то {
записать b в выходной файл;
b := 0;
i := 0;
}
j := j + 1;
}
Шаг 2.
Если входной файл не пуст, то перейти на Шаг2.
если i > 0
то записать b в выходной файл.
Конец.