Задача выбора. Задан линейный список целых, различных по значению чисел B=, требуется найти элемент, имеющий i-тое наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 поиску элемента с вторым наибольшим значением.
Поставленная задача может быть получена из задачи поиска j-того минимального значения заменой i=n-j+1 и поиском i-того максимального значения. Особый интерес представляет задача выбора при i=a/n, 0
Все варианты задачи выбора легко решаются, если список B полностью отсортирован, тогда просто нужно выбрать i-тый элемент. Однако в результате полной сортировки списка B получается больше информации, чем требуется для решения поставленной задачи.
Количество действий можно уменьшить применяя сортировку выбором только частично до i-того элемента. Это можно сделать, напри мер при помощи функции findi
/* выбор путем частичной сортировки */
int findi(int *s, int n, int i)
{
int c,j,k;
for (k=0; k
Эта функция ищет элемент с индексом i, частично сортируя массив s, и выполняет при этом (n*i) сравнений. Отсюда следует, что функция findi приемлима для решения задачи при малом значении i, и малоэффективна при нахождении медианы.
Для решения задачи выбора i-того наибольшего значения в списке B модифицируем алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B’ и B, такие, что если Ki -B’, то KiK1, и если Ki — B, то Kii наибольшее значение ищется в списке B’; при jАлгоритм выбора на базе быстрой сортировки в общем эффективен, но для улучшения алгоритма необходимо, чтобы разбиение списка на подсписки осуществлялось почти пополам. Следующий алгоритм эффективно решает задачу выбора i-того наибольшего элемента в списке B, деля его на подсписки примерно равной величины.
1. Если N
2. Если N21 разделим список на P=N/7 подсписков по 7 элементов в каждом, кроме последнего в котором mod(N,7) элементов.
3. Определим список W из медиан полученных подсписков (четвертых наибольших значений) и найдем в W его медиану M (рекурсивно при помощи данного алгоритма) т.е. (P/2+1)-й наибольший элемент.
4. С помощью элемента M разобьем список B на два подсписка B’ с j элементами большими или равными M, и B c N-j элементами меньшими M. При ji повторим процедуру поиска сначала, но только в подсписке B’. При j=i искомый элемент найден, равен M и поиск прекращается. При j i будем искать (i-j)-тый наибольший элемент в списке B.
/* алгоритм выбора делением списка почти пополам */
int search (int *b, int n, int i)
{
int findi(int *, int, int);
int t, m, j, p, s, *w;
if (n
if (ji)
{
for (p=0, t=0; p n; t++)
if (b[t]=m)
{ b[p]=b[t]; p++; }
m=search(b, j, i); /* поиск в B */
}
if (j i)
{
for (p=0, t=0; t n; t++)
if (b[t] m) b[p++]=b[t];
m=search(b, n-j, i-j); /* поиск в B */
}
return m;
}
Рекурсивная функция search реализует алгоритм выбора i-того наибольшего значения. Для ее вызова можно использовать следующую программу
#include
#include
main()
{
int search (int *b, int n, int i);
int *b;
int l, i, k, t;
scanf(%d%d,l,i);
printf
(nВыбор %d максимального элемента из %d штук,i,l);
b=(int *)(calloc(100,sizeof(int)));
for (k=0; k
Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28*N сравнений.
Действительно, если N
Лекція
Технологія створення програм
Информатика. Алгоритмы поиска и сортировки: Линейный поиск. Центр онлайн-обучения «Фоксфорд»
