Презентация на тему ПОИСК И СОРТИРОВКА МАССИВОВ

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

данных накапливается и хранится в виде файла на магнитном диске. К ней часто приходится обращаться, обновлять, перегруппировывать, осуществлять поиск. Работа с базой может быть организована двумя способами:
1. Вносить изменения и осуществлять поиск можно прямо в файле, при этом временные затраты на обработку данных (поиск, сортировку) значительно возрастают, но нет ограничений на оперативную память.
2. В начале работы вся база (или ее необходимая часть)

оперативной памяти, что значительно сокращает ее время, однако требует

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

ключа может оказаться безрезультатным, хотя этот ключ в массиве

имеется.

массиве структур a[k], k = 0,…, n-1 заключается в

нахождении индекса k, удовлетворяющего условию a[k].kluch = isk. Здесь поле структуры kluch выступает в качестве ключа, isk – искомый ключ. После нахождения значения индекса k обеспечивается доступ ко всем другим полям найденной структуры a[k].
Линейный (последовательный) поиск используется, когда нет никакой дополнительной информации о разыскиваемых данных. Он представляет собой последовательный перебор массива до обнаружения требуемого ключа или до конца, если ключ не обнаружен:
k=0;
while ( k if (k==n) cout<< “элемент не найден”< else cout<<“индекс искомого элемента= “<

шаге вычисляется логическое выражение. Уменьшить затраты на поиск можно

упростив логическое выражение с помощью введения вспомогательного элемента – барьера, который предохраняет от выхода за пределы массива. Для этого в конец массива добавляется элемент с искомым ключом. Количество проверок на каждом шаге уменьшается (проверка одного, а не двух условий), т. к. нет необходимости проверки выхода за пределы массива – элемент с искомым ключом обязательно будет найден до выхода за пределы расширенного массива.
a[n].kluch = isk; k=0;
while ( a[k].kluch != isk ) k++;
if (k==n) cout<<“элемент не найден”;
else cout<<“индекс искомого элемента= “<

упорядочены по возрастанию ключа kluch. Основная идея поиска –

берется «средний» (m-й) элемент массива. Если a[m].kluch < isk, то все элементы массива a[k] с индексами k<=m можно исключить из дальнейшего поиска, в противном случае исключаются элементы с индексами k>m:
i = 0; j = n-1;
while ( i < j )
{
m= ( i+j ) /2;
if ( a[m].kluch < isk ) i=m+1;
else j=m;
}
if ( a[i].kluch == isk )
cout<<“индекс искомого элемента=“< else cout<<“элемент не найден”<

ключа a[m].kluch==isk. На первый взгляд это кажется странным, однако

тестирование показывает, что в среднем выигрыш от уменьшения количества проверок превосходит потери от нескольких «лишних» вычислений до выполнения условия i=j.

приводящий к их упорядоченному расположению относительно ключа. Цель сортировки

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

работы. Мерой эффективности может быть число сравнений ключей с

и число пересылок элементов Р. Эти числа являются функциями С(n), Р(n) от числа сортируемых элементов n. Быстрые (но сложные) алгоритмы сортировки требуют (при n) порядка n*log(n) сравнений, прямые (простые) методы – n2.
Прямые методы коротки, просто программируются. Быстрые, усложненные методы требуют меньшего числа операций, но эти операции обычно сами более сложны, чем операции прямых методов, поэтому для достаточно малых n (n<50) прямые методы работают быстрее. Значительное преимущество быстрых методов начинает проявляться при n >100.

(пузырьковая сортировка).
2) Метод прямого выбора.
3) Сортировка с помощью прямого

(двоичного) включения.
4) Шейкерная сортировка (модификация пузырьковой).
 
Улучшенные методы сортировки:
1) Метод Шелла , усовершенствование метода прямого
включения.
2) Сортировка с помощью дерева, метод HeapSort, Д. Уильямсон.
3) Сортировка с помощью разделения, метод QuickSort, Ч. Хоар. На сегодняшний день это самый эффективный метод сортировки.
Рассмотрим алгоритмы и реализацию некоторых методов.

пузырька сравниваются два соседних элемента. Если предыдущий элемент больше

последующего, то выполняется перестановка этих элементов. Сортировка осуществляется путем многократного прохождения по списку элементов. В общем случае для сортировки n элементов требуется n–1 проход по массиву. Чтобы исключить ненужные проходы, если массив уже был полностью или частично отсортирован, нужно использовать не оператор цикла с заданным количеством повторений for, а оператор while с флажком p. Оба варианта пузырьковой сортировки приведены ниже:

int n)
{ double w;
for (int i=1; i

i++) Номер прохода
for (int k=0; k if ( a[k]>a[k+1] )
{ w=a[k];
a[k]=a[k+1];
a[k+1]=w;
}
}

int i,k; double w;

bool p;
i=1; Номер прохода
do
{ p=false; Флажок
for (k=0; k if (a[k]>a[k+1])
{ w=a[k];
a[k]=a[k+1];
a[k+1]=w;
p=true; Была перестановка
}
i++;
} while (p);
} Сортировка прекращается, если на каком-то проходе не было перестановок ( p=false)

по списку элементов. На каждом (k-ом) проходе находится номер

минимального элемента начиная с k-го, который затем переставляется с k-м элементом. Сортировка методом прямого выбора имеет вид:
void PramSort(double a[], int n)
{ int k, i, m; double w;
for (k=0; k { m=k;
for (i=k+1; i if ( a[i] w=a[m]; a[m]=a[k]; a[k]=w;
}
}

похожий на него метод пузырька. Здесь также сравниваются два

элемента, но не соседние, а разделенные интервалом kol. Начальное значение kol равно половине количества элементов. В процессе сортировки значение kol уменьшается в два раза на каждом проходе, пока не начнет выполняться сравнение соседних элементов, как и в методе пузырька, т.е. сначала сравниваются отдаленные, а затем все более близкорасположенные элементы. Сортировка методом Шелла имеет вид:
 

int k, kol; double w; bool

p;
kol=n/2; Начальный интервал
do
{ do
{ p=false;
for (k=0; k < n-kol; k++)
if ( a[k]>a[k+kol] )
{ w=a[k];
a[k]=a[k+kol];
a[k+kol]=w;
p=true;
}
} while (p);
kol=kol/2; Новый интервал
} while (kol>0);
}

(с объемами занимающими десятки-сотни байтов) занимает значительно больше времени

чем перестановка 4-х байтовых значений. Поэтому рекомендуется вместо перестановки самих данных переставлять их номера (индексы). Такой прием используется практически во всех коммерческих приложениях. В этом случае метод сортировки Шелла с перестановкой индексов имеет вид:

{ int k, kol, w; bool p;

for ( k=0; k kol=n/2; Начальный интервал
do {
do {
p=false;
for ( k=0; k if (a[nom[k]]>a[nom[k+kol]] )
{
w=nom[k];
nom[k]=nom[k+kol];
nom[k+kol]=w;
p=true;
}
} while (p);
kol=kol/2; Новый интервал
} while ( kol>0);
}

в следующем. Сначала выбирается так называемое опорное значение op,

в качестве которого может быть использовано значение какого-либо внутреннего элемента. Массив просматривается слева-направо до тех пор, пока не будет обнаружен элемент a[i]>op. Затем массив просматривается справа-налево, пока не будет обнаружен элемент a[j]

int i, j; Рекурсивный метод Хоара

double op,w;
op=a[(low+high)/2]; Опорный элемент
Перенос элементов, меньших опорного, влево, а больших - право
i=low; j=high;
do {
while ((i<=high) && (a[i] while ((j>=low) && (a[j] >op)) j--;
if (i<=j) { w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--;
}
} while (i if (j>low) QuickSort(a,low,j);
if (i }

{ int l;

int r;
} w[50];
int i, j, left, right, op, s=0; double t;
w[s].l=0; w[s].r=n-1;
while (s!=-1)
{ left=w[s].l;
right=w[s].r;
s--;
while (left { i=left;
j=right;
op=a[(left+right)/2];
while (i<=j)
{ while(a[i] while(a[j]>op) j--;