Данный метод впервые упоминается в работе Э.Х. Фрэнда, хотя он и не заявил о ней как о своей собственной разработке.
При упорядочении таблицы этим методом необходима память для хранения исходной таблицы, а также дополнительно должна быть выделена память под счетчик для каждого элемента таблицы.
В этом алгоритме элементы не перемещаются. Он подобен сортировке таблицы адресов, поскольку таблица счетчиков определяет конечное положение элементов.
Просмотр таблицы начинается с первой записи. Ее ключ сравнивается с ключами последующих записей. При этом счетчик большего из сравниваемых ключей увеличивается на 1. При втором просмотре таблицы первый ключ уже не рассматривается, второй ключ сравнивается со всеми последующими. Результаты сравнений фиксируются в счетчиках. Для таблицы, содержащей N элементов, этот процесс повторяется N-1 раз.
После выполнения всех просмотров счетчик каждого элемента указывает, какое количество ключей таблицы меньше ключа этого элемента. Эти счетчики используются затем в качестве индексов элементов результирующей таблицы. Поместив записи в результирующую таблицу в соответствии со значениями их счетчиков, получим упорядоченную таблицу. Другими словами, если известно, что некоторый ключ превышает ровно 27 других, то после сортировки соответствующий элемент должен занять 28-е место.
/* array - сортируемая таблица (массив) */
/* count - таблица счетчиков (массив) */
/* size - количество эллементов */
void sort(int *array, int *count, int size)
{
register int i, j;
for(i = 0; i < size; i++)
count[i] = 0;
for(i = 0; i < size - 1; i++)
{
for(j = i + 1; j < size; j++)
{
if(array[i] < array[j])
count[j]++;
else
count[i]++;
}
}
return;
}
Сортировка Шелла
Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].
1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1],a[9]),..., (a[7], a[15]).
2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]),..., (a[3], a[7], a[11], a[15]).
В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.
3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).
4. В конце сортируем вставками все элементы
void Shella(int *a,int n)
{
int h, i, t;
int k; // пpизнак пеpестановки
h=n / 2; // начальное значение интеpвала
while (h>0)
{ // цикл с yменьшением интеpвала до 1
// пyзыpьковая соpтиpовка с интеpвалом h
k=1;
while (k)
{
// цикл, пока есть пеpестановки
k=0;
for (i=0; i< n-h;i++)
{ //сpавнение эл-тов на интеpвале h }
if (a[i]>a[i+h])
{
t=a[i]; a[i]=a[i+h]; a[i+h]=t;
k=1; // пpизнак пеpестановки
}
}
}
h=h / 2; //{ yменьшение интеpвала } } }
Бинарный поиск.
Поиск элемента массива, ускоренного в сравнении споследовательным просмотром. Он известен как метод дихотомии или метод половинного деления. Как обычно, за скорость взимается плата: массив должен быть упорядочен. Сам по себе этап предварительного упорядочения, или сортировки, обходится недешево, во всяком случае – дороже однократного линейного поиска.
1. Определяем середину интервала поиска.
2. Сравниваем образец с элементом, расположенным посередине. Если образец оказался больше, то областью дальнейшего поиска становится правая половина; в противном случае - левая половина интервала, но в любом случае индексный интервал уменьшается вдвое. (Если осуществить еще одну проверку, то можно установить и совпадение, после чего дальнейшие шаги не обязательны.)
3. Если остался интервал единичной длины, то переходим к заключительному шагу 4, в противном случае - к шагу 1.
4. Либо единственный элемент интервала совпадает с образцом, либо - искомого элемента в массиве нет.
int BinarySearch(int a[],i, j, int x)
{
int, middle;
while (i <= j)
{
middle = (i + j)/2;
if (x == a[middle])
return middle;
else
if (x > a[middle])
i = middle + 1;
else
j = middle - 1;
}
return -1;
}
Сортировка Слияниями
#include <stdio.h>
#include <stdlib.h>
void merge(int a[], int lb, int split, int ub)
{
int pos1=lb;
int pos2=split+1;
int pos3=0;
int *temp =(int*)malloc((ub-lb+1)*sizeof(int));
while (pos1<=split && pos2<=ub)
{
if (a[pos1]<a[pos2])
temp[pos3++]=a[pos1++];
else
temp[pos3++]=a[pos2++];
}
while (pos2<=ub)
temp[pos3++]=a[pos2++];
while (pos1<=split)
temp[pos3++]=a[pos1++];
for (pos3=0; pos3<ub-lb+1; pos3++)
a[lb+pos3]=temp[pos3];
free(temp);
}
void mergsort(int a[], int lb, int ub)
{
int split;
if (lb<ub)
{
split = (lb + ub)/2;
mergsort(a, lb, split);
mergsort(a, split+1, ub);
merge(a, lb, split, ub);
}
}
void main()
{
int c[5];
for (int i=0;i<5; i++)
scanf("%d", &c[i]);
mergsort(c, 0, 4);
for (int i=0;i<5; i++)
printf("%d ", c[i]);
}
