- •Сортировк а и поиск
- •Сортировка
- •Последовательный
- •Бинарный поиск
- •ПРОВЕРКА
- •Двоичный поиск в упорядоченном
- •Классификация сортировок
- •Классификация сортировок
- •Способ выбора элементов
- •1.Обменная сортировка
- •Программа методом
- •1.2. Шейкер-сортировка
- •►void Swap(int *B, int i) //функция обмена
- •Сортировка выбором
- •4. Сортировка выбором
- •Оценка
- •5. Сортировка
- •5.1 ПРОСТАЯ ВСТАВКА
- •►void InsertSort(int A[], int
- •Анализ
- •5.2.Метод Шелла (сортировка
- •►void Shell(int A[], int n)
- •2. Сортировка разделением
- •►// m[] - массив чисел; sm - индекс 1-ого
- •►int GetHoarBorder(int m[], int sm, int em)
- •оценки
- •Сортировка подсчетом
- •Оценка
- •4.3. КВАДРАТИЧНАЯ ВЫБОРКА
- •Оценка
- •A 6. Сортировка слиянием
- •6.1. ОДНОКРАТНОЕ СЛИЯНИЕ
- •Анализ
- •6.2. ПРОСТОЕ СЛИЯНИЕ
- •6.3. ЦИКЛИЧЕСКОЕ СЛИЯНИЕ
- •Пример Циклическое двухпутевое
- •7. Распределяющая
- •PАСПРЕДЕЛЕНИЕ
- •СБОРКА
- •►Для сортировки N T-цифровых чисел, необходимо (N*T) действий
- •8. Пирамидальная
- •Фаза 1: построение пирамиды
- •Для последовательности 06 42 12 55 94 18 44
- •Фаза 2: сортировка
- •Анализ
- •Алгоритм
- •Самые эффективные методы сортировки:
Сортировк а и поиск
Сортировка
►процесс упорядочения набора элементов в возрастающем или убывающем порядке
►КЛЮЧ -- часть элемента данных,
которая используется для его
идентификации и поиска среди множества других таких элементов
Последовательный
поиск
►наилучшем случае сложность алгоритма последовательного поиска равна O(1)
►в наихудшем случае сложность алгоритма последовательного поиска равна О(n)
►Ср. - обнаруживается после n / 2 |
||||
сравнений |
|
|
||
1 |
5 |
6 |
7 |
12 |
4 6 |
7 |
89 |
1 |
|
Бинарный поиск
►для поиска элемента в упорядоченном массиве и основан на повторяющемся делении частей массива пополам
2 5 7 12 14 33 55 73 99
►n=2k
►В наихудшем случае алгоритм выполнит k разбиений и, следовательно, k сравнений где k = log2n
O(log2n) для любого значения n
ПРОВЕРКА
УПОРЯДОЧНЕННОСТИ
МАССИВА
int is_sorted(int a[], int n)
{ for (int i=0; i<n-1; i++)
if (a[i]>a[i+1])
return 0;
} return 1;
Двоичный поиск в упорядоченном |
|
int |
массиве |
binary(int c[], int n, int val) |
|
{ |
int a,b,m; |
for(a=0,b=n-1; a <= b;)
{
m = (a + b)/2; if(c[m] == val)
return(m);
if (c[m] > val) b = m-1;
else |
a = m+1; |
} |
|
return(-1); |
} // log2n |
Классификация сортировок
по размещению элементов: ►внешняя -в файле данных ►внутренняя -в памяти
методы, не требующие резерва памяти;
методы, требующие резерва памяти
1)метод выборки, "пузырька", вставки,
Шелла.
2)метод квадратичной выборки, метод слияния
Классификация сортировок
►По виду структур данных
Сортировка массивов Массивов указателей
Списков
Объектов др. структур
Способ выбора элементов
►Обменная ►Разделением ►Подсчетом ►Выбором
►Вставками
►Пирамидальная ►Распределяющая ►Слиянием
1.Обменная сортировка
1.1.Метод “пузырька”
в худшем случае
(n – 1) +(n – 2) + ..+ 1 = n (n – 1) / 2 ≈ n2 / 2 (n-1)+(n-2)+..+1 =n(n-1)/2 сравнений и n(n-1)/2 перестановок + присваивания
общееколичество основных операций
2n( n – l)= 2n2 – 2n
►Среднее число сравнений и перестановок имеетпорядок n 2.
O(n2) не требует памяти
2 |
1 |
4 |
5 |
3 |
1 |
|
6 |
1 |
2 |
4 |
5 |
1 |
3 |
2 |
6 |
1 |
4 |
5 |
|
1 |
|
3 |
6 |
1 |
4 |
2 |
9 |
1 |
4 |
3 |
9 |
1 |
2 |
||
1 |
4 |
3 |
9 |
1 |
2 |
||
1 |
1 |
3 |
9 |
4 |
2 |
||
|
1 |
3 |
|
9 |
3 |
7 |
|
5 |
|
9 |
3 |
7 |
9 |
5 |
7 |
3 |
||
|
5 |
|
5 |
3 |
7 |
6 |
5 |
7 |
3 |
5 |
|
5 |
6 |
5 |
3 |
7 |
|
5 |
7 |
6 |
3 |
5 |
|
5 |
|
6 |