Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Организация работы с базами данных Для создания и обработки всевозможных баз данных широко применяются массивы структур. Обычно база данных накапливается и хранится в виде файла на магнитном диске. К ней часто приходится обращаться, обновлять, перегруппировывать, осуществлять
ПОИСК И СОРТИРОВКА МАССИВОВ Организация работы с базами данных 	Для создания и обработки всевозможных баз данных считывается в массив структур и обработка производится в оперативной памяти, что значительно числа, т. к. из-за ошибки округления поиск нужного ключа может оказаться безрезультатным, Поиск в массиве записей	Задача поиска требуемого элемента в массиве структур a[k], k Поиск с барьером. В линейном поиске на каждом шаге вычисляется логическое выражение. Поиск делением пополам (бинарный поиск) используется, когда данные упорядочены по возрастанию ключа В этом алгоритме отсутствует проверка внутри цикла совпадения ключа a[m].kluch==isk. На первый Сортировка массивов	Под сортировкой понимается процесс перегруппировки элементов массива, приводящий к их упорядоченному Методы внутренней сортировки классифицируются по времени их работы. Мерой эффективности может Среди простых методов наиболее популярны:1) Метод прямого обмена (пузырьковая сортировка).2) Метод прямого Метод пузырьковой сортировки   При сортировке методом пузырька сравниваются два соседних Сортировка с явно заданным числом проходовvoid puzsort(double a[], int n){ double w; Сортировка с использованием флажкаvoid puzsort(double a[], int n){  int i,k; Метод прямого выбора 	Сортировка осуществляется путем многократного прохождения по списку элементов. На Метод Шелла 	Метод сортировки Шелла намного эффективнее, чем похожий на него метод void ShellSort(double a[], int n)  {  int k, kol; Полезный совет: перестановка элементов со сложными типами данных (с объемами занимающими десятки-сотни void ShellSortInd(double a[], int n, int nom[])  { int k, kol, Метод Хоара (Hoare) 	Идея метода быстрой сортировки Хоара в следующем. Сначала выбирается void QuickSort(double a[], int low, int high) { int i, j; void QuickSort(double a[], int n){   struct if (i
Слайды презентации

Слайд 2 Организация работы с базами данных
Для создания и обработки

Организация работы с базами данных 	Для создания и обработки всевозможных баз

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

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

Слайд 3 считывается в массив структур и обработка производится в

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

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

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

Слайд 4 числа, т. к. из-за ошибки округления поиск нужного

числа, т. к. из-за ошибки округления поиск нужного ключа может оказаться

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

имеется.

Слайд 5 Поиск в массиве записей
Задача поиска требуемого элемента в

Поиск в массиве записей	Задача поиска требуемого элемента в массиве структур a[k],

массиве структур 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<<“индекс искомого элемента= “<

Слайд 6 Поиск с барьером. В линейном поиске на каждом

Поиск с барьером. В линейном поиске на каждом шаге вычисляется логическое

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

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

Слайд 7 Поиск делением пополам (бинарный поиск) используется, когда данные

Поиск делением пополам (бинарный поиск) используется, когда данные упорядочены по возрастанию

упорядочены по возрастанию ключа 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<<“элемент не найден”<

Слайд 8 В этом алгоритме отсутствует проверка внутри цикла совпадения

В этом алгоритме отсутствует проверка внутри цикла совпадения ключа a[m].kluch==isk. На

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

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


Слайд 9 Сортировка массивов
Под сортировкой понимается процесс перегруппировки элементов массива,

Сортировка массивов	Под сортировкой понимается процесс перегруппировки элементов массива, приводящий к их

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

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




Слайд 10 Методы внутренней сортировки классифицируются по времени их

Методы внутренней сортировки классифицируются по времени их работы. Мерой эффективности

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

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


Слайд 11 Среди простых методов наиболее популярны:
1) Метод прямого обмена

Среди простых методов наиболее популярны:1) Метод прямого обмена (пузырьковая сортировка).2) Метод

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

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

Слайд 12 Метод пузырьковой сортировки
При сортировке методом

Метод пузырьковой сортировки  При сортировке методом пузырька сравниваются два соседних

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

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


Слайд 13 Сортировка с явно заданным числом проходов
void puzsort(double a[],

Сортировка с явно заданным числом проходовvoid puzsort(double a[], int n){ double w; for (int i=1; i

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;
}
}

Слайд 14 Сортировка с использованием флажка
void puzsort(double a[], int n)
{

Сортировка с использованием флажкаvoid puzsort(double a[], int n){ int i,k;

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)

Слайд 15 Метод прямого выбора
Сортировка осуществляется путем многократного прохождения

Метод прямого выбора 	Сортировка осуществляется путем многократного прохождения по списку элементов.

по списку элементов. На каждом (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;
}
}


Слайд 16 Метод Шелла
Метод сортировки Шелла намного эффективнее, чем

Метод Шелла 	Метод сортировки Шелла намного эффективнее, чем похожий на него

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

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


Слайд 17 void ShellSort(double a[], int n)
{

void ShellSort(double a[], int n) { int k, kol; double w;

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);
}

Слайд 18 Полезный совет: перестановка элементов со сложными типами данных

Полезный совет: перестановка элементов со сложными типами данных (с объемами занимающими

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

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

Слайд 19 void ShellSortInd(double a[], int n, int nom[])

void ShellSortInd(double a[], int n, int nom[]) { int k, kol,

{ 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);
}

Слайд 20 Метод Хоара (Hoare)
Идея метода быстрой сортировки Хоара

Метод Хоара (Hoare) 	Идея метода быстрой сортировки Хоара в следующем. Сначала

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

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

Слайд 21 void QuickSort(double a[], int low, int high)
{

void QuickSort(double a[], int low, int high) { int i, 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 }

Слайд 22 void QuickSort(double a[], int n)
{ struct

void QuickSort(double a[], int n){  struct   { int

{ 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--;


  • Имя файла: poisk-i-sortirovka-massivov.pptx
  • Количество просмотров: 94
  • Количество скачиваний: 0