Комбинированный метод быстрой сортировки с методом «пузырька».
В этом методе рекурсивный алгоритм разделения массива быстрой сортировки применяется только для подпоследовательностей массива, длина которых не менее определенного размера m (m<=n). Для сортировки коротких подпоследовательностей используется метод «пузырька».
Линейная вставка
Элементы массива делятся на уже упорядоченную последовательность а0, а1, …, аi-1 и неупорядоченную аi, ai+1, …,an-1. В каждом проходе из неупорядоченной последовательности извлекается элемент аi (в первом проходе i=1) и вставляется в упорядоченную последовательность из i элементов без нарушения упорядоченности в ней. Этот алгоритм повторяется для i=2,3,…,n-1. Алгоритм вставки аi в упорядоченную последовательность из i элементов заключается в продвижении вставляемого элемента в начало последовательности, сравнивая его с аi-1, ai-2 и т.д. Продвижение заканчивается на элементе аj<=ai или при прохождении всей последовательности.
Бинарная вставка.
В этом методе, в отличие от линейной вставки, для отыскания места для вставки элемента ai в упорядоченную последовательность используется алгоритм бинарного поиска, при котором элемент ai сравнивается со средним элементом упорядоченной последовательности, а затем процесс деления пополам продолжается до тех пор, пока не будет найдена точка включения.
Центрированная вставка.
Алгоритм использует дополнительный рабочий массив. В позицию, расположенную в центре рабочего массива помещается элемент а0. Он будет медианой. Слева от медианы надо расположить все элемент, меньшие медианы, а справа – большие или равные. Из сортируемого массива последовательно выбирается элемент, сравнивается с медианой и вставляется без нарушения упорядоченности в левую или правую части массива. Если область памяти, выделенная для одной из частей, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении и значение медианы изменяется. В конце алгоритма упорядоченные элементы должны быть скопированы в исходный массив.
Метод фон Неймана.
Упорядочить пары соседних элементов массива а (а0 и а1, а2 и а3 и т.д.) и перенести их во вспомогательный массив b. Затем взять по две соседние пары из b и, слив их в упорядоченные четверки, снова записать в а; затем каждые две четверки из b слить в упорядоченные восьмерки и переписать в а и т.д. Упорядоченный массив должен оказаться в массиве а.
Внешняя двухфазная сортировка прямым слиянием.
Внешняя сортировка используется для сортировки файлов, размеры которых не позволяют записать их во временные массивы в оперативной памяти. Для сортировки используются три файла: c (исходный файл), a и b (вспомогательные файлы). Элементы исходного файла с попеременно записываются то в а, то в файл b (фаза разделения). Таким образом, в каждом файле создаются одноэлементные последовательности. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b (фаза слияния). Эти двухэлементные последовательности записываются в файл с. Далее двухэлементные последовательности попеременно записываются то в а, то в файл b (фаза разделения). Затем двухэлементные последовательности из файлов a и b сливаются в упорядоченные четверки и записываются в файл с (фаза слияния). Алгоритм разбиения файла с пополам и формирование упорядоченных последовательностей путем слияния пар последовательностей из файлов a и b повторяется до тех пор, пока в файлах a и b не образуется по одной упорядоченной последовательности, которые окончательно сливаются в отсортированный файл с.
В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.
Внешняя однофазная сортировка прямым слиянием.
Для сортировки используются четыре файла: c (исходный файл), a, b и d (вспомогательные файлы). При первом проходе элементы исходного файла с попеременно записываются то в а, то в файл b. Далее формируются двухэлементные упорядоченные последовательности, в которых один элемент берется из а, а другой из b. Эти двухэлементные последовательности попеременно записываются в файлы с и d. Затем сливаются пары двухэлементных последовательностей из файлов c и d в упорядоченные четверки, которые записываются попеременно в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.
В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.
Внешняя сортировка естественным слиянием.
Сортировка, при которой сливаются две самые длинные из возможных упорядоченных последовательностей, называется естественным слиянием. В алгоритме используется исходный файл с и два вспомогательных файла a и b. В алгоритме при первом проходе определяются как можно более длинные упорядоченные последовательности файла с. Далее эти последовательности попеременно записываются в файлы a и b. На каждом следующем проходе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и переносятся в файл с, после чего наступает фаза разделения: последовательности попеременно записываются в файлы a. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.
В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.
Внешняя сортировка сбалансированным слиянием.
В алгоритме используется исходный файл с и три вспомогательных файла a, b, d. В данном алгоритме при первом проходе определяются как можно более длинные упорядоченные участки файла с. Далее эти участки попеременно записываются в файлы a и b. На следующем этапе пары i-х упорядоченных последовательностей файлов a и b (i=1,2,3,…) сливаются в более длинные упорядоченные последовательности и попеременно переносятся в файлы с и d. Затем сливаются пары последовательностей файлов с и d и попеременно переносятся в файлы a и b и т.д. В конце алгоритма единая упорядоченная последовательность должна оказаться в файле с.
В задании реализовать «внутреннюю» версию алгоритма для сортировки массива из n элементов.
Бинарный поиск.
Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Сначала х сравнивается со средним элементом массива. Если совпадение найдено, то возвращается индекс среднего элемента, иначе определяется, в какой половине массива следует выполнять поиск, применяя к ней алгоритм бинарного поиска.
Интерполяционный поиск.
Алгоритм применяется к упорядоченному массиву, в котором надо найти номер элемента с заданным значением x. Если известно, что х находится между элементами al и ar, то номер очередного элемента для сравнения вычисляется по формуле
m=l+(r-l)*(x-al)/(ar-al)
Если совпадение найдено, то возвращается индекс элемента (m), иначе определяется, в какой части массива следует выполнять поиск, применяя к ней алгоритм интерполяционного поиска.
#include <iostream.h>
#include <conio.h>
void sort(int a[], int n)
{
int i,j;
int c;
for(j=1;j<=n-1;j++)
for(i=0;i<n-j;i++)
if(a[i]>a[i+1])
{c=a[i];a[i]=a[i+1];a[i+1]=c;}
}
void main(void)
{
int a[10];
int n;
int i;
cout<<"n? ";
cin>>n;
cout<<"a?";
for(i=0;i<n;i++)
cin>>a[i];
sort(a,n); //вызов функции сортировки
cout<<"a: ";
for(i=0;i<n;i++)
cout<<a[i]<<' ';
getch();
}
Рис. 2. Сортировка массива методом «пузырька»
Пример решения (вариант 13).
Задание: Выполнить сортировку целочисленного массива (поиск в массиве) из n элементов. Алгоритм сортировки (поиска) оформить в виде функции. Метод: Сортировка методом бинарной вставки.
Текст программы:
//Сортировка массива методом бинарной вставки
/*В программе первый элемент рассматривается как упорядоченный массив.
Далее из оставшейся части массива последовательно берутся элементы
И вставляются без нарушения упорядоченности в уже отсортированную часть
Массива. Так как массив отсортирован, то для поиска места элемента
Используется метод бинарного поиска*/
#pragma hdrstop
#pragma argsused
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <iomanip.h>
//Функция сортировки массива методом бинарной вставки
void sort(int a[], int n)
{
//Объявление переменных
int newElement, left, right, middle, i, j;
for (i=1;i<n;i++)
{
//Обрабатываемый на данном этапе элемент
newElement=a[i];
//Границы отсортированной части массива
left=0; right=i-1;
while (left<=right)
{
//Средний элемент в отсортированной части
middle=(left+right)/2;
//Анализ отношения обрабатываемого и среднего элемента
if (a[middle]<=newElement)
left=middle+1;
else
right=middle-1;
}
//Сдвиг элементов вправо и вставка обрабатываемого элемента
//на новое место
for (j=i;j>right+1;j--) a[j]=a[j-1];
a[right+1]=newElement;
}
}
//Основная программа
void main(void)
{
//Объявление переменных