Содержание
1. Понятие сортировки
2. Методы сортировки
a. Внутренние сортировки
i. Сортировка слиянием
ii. Пирамидальная сортировка
iii. Метод Хоара
b. Внешние сортировки
i. Прямым слиянием
ii. Естественное слияние
iii. Сбалансированное многопутевое слияние
3. Список использованной литературы
4.
I. Понятие сортировки
Сортировка - перестановка элементов в подмножестве данных по какому-либо критерию. Чаще всего в качестве критерия используется некоторое числовое поле, называемое ключевым.
Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве при обработке данных.
Все алгоритмы сортировки делятся на:
· алгоритмы внутренней сортировки (сортировка массивов);
· алгоритмы внешней сортировки (сортировка файлов).
Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат. (Примечание: В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки).
Внутренняя сортировка – это алгоритм сортировки, который в процессе упорядочивания данных использует только оперативную память (ОЗУ) компьютера.
Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных использует внешнюю память, как правило, жесткие диски. Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память. Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ.
|
|
Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных использует внешнюю память, как правило, жесткие диски.
Метод «Разделяй и властвуй» (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
II. Методы сортировки
A. Внутренние сортировки
I. Сортировка слиянием
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определённом порядке.
Для решения задачи сортировки эти три этапа выглядят так:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
3.1. Соединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по неубыванию подмассива. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1.
3.3. «Прицепление» остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
|
|
Реализация на С++ (сортировка по возрастанию):
const int nmax = 1000;
void Merge(int* arr, int begin, int end)
{
int i = begin, t = 0, mid = begin + (end - begin) / 2, j = mid + 1, d[nmax];
while (i <= mid && j <= end) {
//запись в массив d
if (arr[i] <= arr[j]) {
d[t] = arr[i]; i++;
}
else {
d[t] = arr[j]; j++;
}
t++;
}
//перенос оставшихся элементов в массив d
while (i <= mid) {
d[t] = arr[i]; i++; t++;
}
//перенос оставшихся элементов в массив d
while (j <= end) {
d[t] = arr[j]; j++; t++;
}
//перенос элементов обратно в массив arr
for (i = 0; i < t; i++)
arr[begin + i] = d[i];
}
void MergeSort(int *arr, int left, int right)
{
int temp;
if (left<right)
//Если осталось 2 элемента сравниваем их и если необходимо меняем местами
if (right - left == 1) {
if (arr[right]<arr[left]) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
else {
MergeSort(arr, left, left + (right - left) / 2);
MergeSort(arr, left + (right - left) / 2 + 1, right);
Merge(arr, left, right);
}
}
ii. Пирамидальная сортировка
Пирамидальная сортировка (Heapsort, сортировка кучей) подходит для работы с полными бинарными деревьями в массиве. В ней используется структура данных, называемая кучей. Пирамида (сортирующее дерево, двоичная куча) – это двоичное дерево с упорядоченными листьями, в корне которого расположен максимальный или минимальный элемент. Пирамидой (кучей) называется двоичное дерево такое, что
|
|
a[i] ≤ a[2i+1];
a[i] ≤ a[2i+2].
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов. Алгоритм основан на одном из свойств кучи — в голове (или вершине) кучи находится самый (максимальный) элемент. Просеивание – это построение новой пирамиды посредством спуска вниз элемента из вершины дерева в соответствии с ключом сортировки
Алгоритм
1. Построим из требуемого массива кучу
2. Меняем местами первый и последний элемент в куче
3. Уменьшаем размер рассматриваемой кучи на 1
4. Вызвать процедуру нормализации кучи в корне кучи
5. Вернуться в шаг 2 и продолжать выполнять алгоритм, пока куча имеет больше одного элемента
Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды.
2 этап Сортировка на построенной пирамиде.
Реализация на С++ (сортировка по возрастанию):
// Функция "просеивания" через кучу - формирование кучи
void siftDown(int *numbers, int root, int bottom)
{
int maxChild; // индекс максимального потомка
int done = 0; // флаг того, что куча сформирована
// Пока не дошли до последнего ряда
while ((root * 2+1 <= bottom) && (!done))
{
if (root * 2+1 == bottom) // если мы в последнем ряду,
maxChild = root * 2; // запоминаем левый потомок
// иначе запоминаем больший потомок из двух
else if (numbers[root * 2+1] > numbers[root * 2 + 2])
maxChild = root * 2+1;
else
maxChild = root * 2 + 2;
// если элемент вершины меньше максимального потомка
if (numbers[root] < numbers[maxChild])
{
int temp = numbers[root]; // меняем их местами
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else // иначе
done = 1; // пирамида сформирована
}
}
// Функция сортировки на куче
void heapSort(int *numbers, int array_size)
{
// Формируем нижний ряд пирамиды
for (int i = (array_size / 2) - 1; i >= 0; i--)
siftDown(numbers, i, array_size);
// Просеиваем через пирамиду остальные элементы
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i - 1);
}
}
Iii. Метод Хоара
Сортировка Хоара – это одна из разновидностей быстрых сортировок, основанная на упорядочивании подмножеств массива относительно опорных элементов.
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n\log n) обменов при упорядочении n элементов.
На входе массив a[0]...a[N] и опорный элемент x, по которому будет производиться разделение.
1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= x. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= x.
3. 
Далее, если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i,j по тем же правилам...
4. Повторяем шаг 3, пока i <= j.
Реализация на С++:
void qs(int* s_arr, int first, int last)
{
//i - первый элемент, j - последний, x - средний
int i = first, j = last, x = s_arr[(first + last) / 2];
do {
//доходим до элемента который больше х
while (s_arr[i] < x) i++;
//доходим до элемента который меньше х
while (s_arr[j] > x) j--;
if (i <= j) {
//меняем местами
if (s_arr[i] > s_arr[j])
swap(s_arr[i], s_arr[j]);
i++;
j--;
}
} while (i <= j);
//рекурсивно сортируем каждую часть
if (i < last)
qs(s_arr, i, last);
if (first < j)
qs(s_arr, first, j);
}
B. Внешние сортировки
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу. Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены). В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла. Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну. Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.
I. Прямым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.
В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2k.
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл (рис. 43.1).
После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.
Признаками конца сортировки простым слиянием являются следующие условия:
· длина серии не меньше количества элементов в файле (определяется после фазы слияния);
· количество серий равно 1 (определяется на фазе слияния).
· при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Реализаия в файле sort.h
#pragma once
#include <fstream>
#include <iostream>
#include <string>
using std::fstream;
using std::string;
using std::ios;
using std::cout;
using std::endl;
template<class T>
class DOSort{
fstream file, file1, file2;
//Имя файла
string fileName;
//Кол-во
int amountObj;
//Длина серии
int srLen;
public:
//Конструкторы
DOSort(): amountObj(0), srLen(0), fileName("") {}
DOSort(string fName) {reset(fName);}
///////////////////////////////////
//Назначить новый файл(сброс)
void reset(string fName);
//Выполнить сортировку (точка входа)
void run();
private:
//Подсчёт значений
void countObj();
//Разделение на файлы
void splitFile();
//Объединение в файл
void mergeFiles();
///////////////////////////////////
//Базовая сортировка в mergeFiles()
void basicSort(T &obj1, T &obj2);
///////////////////////////////////
//Ошибка
void error() {exit(0);}
//Закрытие файлов
void closeFiles();
//Удаление временных файлов
void removeTmpFiles();
};
///////////////////////////////////
// Реализация
///////////////////////////////////
template<class T>
void DOSort<T>::reset(string fName)
{
fileName = fName;
amountObj = 0;
srLen = 1;
}
///////////////////////////////////
template<class T>
void DOSort<T>::run()
{
//Счёт объектов в файле
countObj();
//Выполнять пока длина серии меньше кол-во объектов
while(srLen < amountObj){
//Разделение на 2 файла
splitFile();
//Объединение в файл
mergeFiles();
//Увеличение длины серии
srLen*=2;
}
//Удаление временных файлов
removeTmpFiles();
}
///////////////////////////////////
template<class T>
void DOSort<T>::countObj()
{
//Для перебора элементов
T temp;
//Открытие файла
file.open(fileName, ios::in);
if (!file.is_open())
error();
//Подсчёт элементов
while(!file.eof()){
file >> temp;
amountObj++;
}
//Закрытие исх файла
file.close();
}
///////////////////////////////////
template<class T>
void DOSort<T>::splitFile()
{
//Открытие файлов
file.open(fileName, ios::in);
file1.open(fileName + ".part1", ios::out);
file2.open(fileName + ".part2", ios::out);
//Проверка на открытие файлов
if (!file ||!file1 ||!file2)
error();
//Объект для копирования
T obj;
//Пока не конец файла
while(!file.eof()){
//Файл 1
for(int i = 0; i < srLen &&!file.eof(); i++){
file >> obj;
if (file)
file1 << obj << " ";
}
//Файл 2
for(int i = 0; i < srLen &&!file.eof(); i++){
file >> obj;
if (file)
file2 << obj << " ";
}
}
//Закрытие файлов
closeFiles();
}
///////////////////////////////////
template<class T>
void DOSort<T>::mergeFiles()
{
//Открытие файлов
file.open(fileName, ios::out);
file1.open(fileName + ".part1", ios::in);
file2.open(fileName + ".part2", ios::in);
//Проверка на открытие файлов
if (!file ||!file1 ||!file2)
error();
//tmp объекты
T obj1, obj2;
//1-ое извлечение
file1 >> obj1;
file2 >> obj2;
//Пока не конец файла
while(!file1.eof() &&!file2.eof())
basicSort(obj1, obj2);
//Копирование остатков file1 в file
while(!file1.eof()){
file << obj1 << " ";
file1 >> obj1;
}
//Копирование остатков file2 в file
while(!file2.eof()){
file << obj2 << " ";
file2 >> obj2;
}
//Закрытие файлов
closeFiles();
}
///////////////////////////////////
template<class T>
void DOSort<T>::basicSort(T &obj1, T &obj2)
{
int i = 0, j = 0;
//Распределение
while(i < srLen && j < srLen &&!file1.eof() &&!file2.eof()){
if (obj1 < obj2){
file << obj1 << " ";
file1 >> obj1;
i++;
}else{
file << obj2 << " ";
file2 >> obj2;
j++;
}
}
//Доп. копирование остатков fil1 в file
while (i < srLen &&!file1.eof()){
file << obj1 << " ";
file1 >> obj1;
i++;
}
//Доп. копирование остатков file2 в file
while (j < srLen &&!file2.eof()){
file << obj2 << " ";
file2 >> obj2;
j++;
}
}
///////////////////////////////////
template<class T>
void DOSort<T>::closeFiles()
{
file.close();
file1.close();
file2.close();
}
///////////////////////////////////
template<class T>
void DOSort<T>::removeTmpFiles()
{
remove(string(fileName + ".part1").c_str());
remove(string(fileName + ".part2").c_str());
}