Аркадна игра "гольф" с элементами трехмерной поверхности на языке Borland C++

1.1.1 Методы организации и хранения линейных списков

Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.

Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (см. рис.1).

Например, F1=<2,3,1>,F2=<7,7,7,2,1,12>, F3=<>. Длина списков F1, F2, F3 равна соответственно 3,6,0.

При работе со списками на практике чаще всего приходится выполнять следующие операции:

найти элемент с заданным свойством;

определить первый элемент в линейном списке;

вставить дополнительный элемент до или после указанного узла;

исключить определенный элемент из списка;

упорядочить узлы линейного списка в определенном порядке.

В реальных языках программирования нет какой-либо структуры данных для представления линейного списка так, чтобы все указанные операции над ним выполнялись в одинаковой степени эффективно. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти.

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. Рассмотрим простейшие варианты этих методов для списка с целыми значениями F=<7,10>.

При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d [100] ; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d [0] =7; d [1] =10; l=2;

Полученный список хранится в памяти согласно схеме на рис.2.

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

Описание структуры и указателя в этом случае может имееть вид:

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рис.3.

Рис.2. Связное хранение линейного списка.

1.1.2 Операции со списками при последовательном хранении

При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.

Пусть имеется линейный список с целыми значениями и для его хранения используется массив d (с числом элементов 100), а количество элементов в списке указывается переменной l. Реализация указанных ранее операций над списком представляется следующими фрагментами программ которые используют объявления:

float d [100] ;

int i,j,l;

1) печать значения первого элемента (узла)

if (i<0 || i>l) printf("\n нет элемента");

else printf("d [%d] =%f ", i,d [i]);

2) удаление элемента, следующего за i-тым узлом

if (i>=l) printf("\n нет следующего ");

l--;

for (j=i+1; j<="1" if узла i-того соседей обоих печать 3) d [j] ="d [j+1] ; ">=l) printf("\n нет соседа");

else printf("\n%d%d",d [i-1],d [i+1]);

4) добавление нового элемента new за i-тым узлом

if (i==l || i>l) printf("\n нельзя добавить");

else

{ for (j=l; j>i+1; j--) d [j+1] =d [j] ;

d [i+1] =new; l++;

}

5) частичное упорядочение списка с элементами К1, К2,..., Кl в

список K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, чтобы K1'= K1.

{ int t=1;

float aux;

for (i=2; i<=l; i++) if (d [i] =2; j--) d [j] =d [j-1] ;

t++;

d [i] =aux;

}

}

Схема движения индексов i,j,t и значения aux=d [i] при выполнении приведенного фрагмента программы приведена на рис.4.

Рис.4. Движение индексов при выполнении операций над списком в последовательном хранении.

Количество действий Q, требуемых для выполнения приведенных операций над списком, определяется соотношениями: для операций 1 и 2 - Q=1; для операций 3,4 - Q=l; для операции 5 - Q=l*l.

Заметим, что вообще операцию 5 можно выполнить при количестве действий порядка l, а операции 3 и 4 для включения и исключения элементов в конце списка, часто встречающиеся при работе со стеками, - при количестве действий 1.

Более сложная организация операций требуется при размещении в массиве d нескольких списков, или при размещении списка без привязки его начала к первому элементу массива.

1.1.3 Операции со списками при связном хранении

При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание:

typedef struct nd

{ float val;

struct nd * n; } ND;

int i,j;

ND * dl, * r, * p;

Для реализации операций могут использоваться следующие фрагменты программ:

1) печать значения i-го элемента

r=dl; j=1;

while(r! =NULL && j++n;

if (r==NULL) printf("\n нет узла%d ", i);

else printf("\n элемент%d равен%f ", i,r->val);

2) печать обоих соседей узла(элемента), определяемого указателем p (см. рис.5)

Рис.5. Схема выбора соседних элементов.

if((r=p->n) ==NULL) printf("\n нет соседа справа");

else printf("\n сосед справа%f", r->val);

if(dl==p) printf("\n нет соседа слева");

else { r=dl;

while(r->n! =p) r=r->n;

printf("\n левый сосед%f", r->val);

}

3) удаление элемента, следующего за узлом, на который указывает р (см. рис.6)

Рис.6. Схема удаления элемента из списка.

if ((r=p->n) ==NULL) printf("\n нет следующего");

p->n=r->n; free(r->n);

4) вставка нового узла со значением new за элементом, определенным указателем р (см. рис.7)

Рис.7. Схема вставки элемента в список.

r=malloc(1,sizeof(ND));

r->n=p->n; r->val=new; p->n=r;

5) частичное упорядочение списка в последовательность значений, s+t+1=l, так что K1'=K1; после упорядочения указатель v указывает на элемент K1' (см. рис. 8)

Рис.8. Схема частичного упорядочения списка.

ND *v;

float k1;

k1=dl->val;

r=dl;

while(r->n! =NULL)

{ v=r->n;

if (v->valn=v->n;

v->n=dl;

dl=v;

}

else r=v;

}

Количество действий, требуемых для выполнения указанных операций над списком в связанном хранении, оценивается соотношениями: для операций 1 и 2 - Q=l; для операций 3 и 4 - Q=1; для операции 5 - Q=l.

1.1.4 Организация двусвязных списков

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).

В программе двусвязный список можно реализовать с помощью описаний:

typedef struct ndd

{ float val; /* значение элемента */

struct ndd * n; /* указатель на следующий элемент */

struct ndd * m; /* указатель на предыдующий элемент */

} NDD;

NDD * dl, * p, * r;

Графическая интерпретация метода связанного хранения списка F=<2,5,7,1> как списка с двумя связями приведена на рис.9.

Рис.9. Схема хранения двусвязного списка.

Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:

r=malloc(NDD);

r->val=new;

r->n=p->n;

(p->n) - >m=r;

p->=r;

Удаление элемента, следующего за узлом, на который указывает p

p->n=r;

p->n=(p->n) - >n;

((p->n) - >n) - >m=p;

free(r);

Связанное хранение линейного списка называется циклическим списком, если его последний указывает на первый элемент, а указатель dl - на последний элемент списка.

Схема циклического хранение списка F=<2,5,7,1> приведена на рис.10.

Рис.10. Схема циклического хранения списка.

При решении конкретных задач могут возникать разные виды связанного хранения.

Пусть на входе задана последовательность целых чисел B1,B2,...,Bn из интервала от 1 до 9999, и пусть Fi (1<I по возрастанию. Составить процедуру для формирования Fn в связанном хранении и возвращения указателя на его начало.

При решении задачи в каждый момент времени имеем упорядоченный список Fi и при вводе элемента Bi+1 вставляем его в нужное место списка Fi, получая упорядоченный список Fi+1. Здесь возможны три варианта: в списке нет элементов; число вставляется в начало списка; число вставляется в конец списка. Чтобы унифицировать все возможные варианты, начальный список организуем как связанный список из двух элементов <0,1000>.

Рассмотрим программу решения поставленной задачи, в которой указатели dl, r, p, v имеют следующее значение: dl указывает начало списка; p, v - два соседних узла; r фиксирует узел, содержащий очередное введенное значение in.

#include

#include

typedef struct str1

{ float val;

struct str1 *n; } ND;

main()

{ ND *arrange(void);

ND *p;

p=arrange();

while(p! =NULL)

{

printf("\n%f ",p->val);

p=p->n;

}

}

ND *arrange() /* формирование упорядоченного списка */

{ ND *dl, *r, *p, *v;

float in=1;

char *is;

dl=malloc(sizeof(ND));

dl->val=0; /* первый элемент */

dl->n=r=malloc(sizeof(ND));

r->val=10000; r->n=NULL; /* последний элемент */

while(1)

{

scanf("%s", is);

if(* is=='q') break;

in=atof(is);

r=malloc(sizeof(ND));

r->val=in;

p=dl;

v=p->n;

while(v->valn;

}

r->n=v;

p->n=r;

}

return(dl);

}

1.1.5 Стеки и очереди

В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью.

Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=<>.

Допустимыми операциями над стеком являются:

проверка стека на пустоту S=<>,

добавление нового элемента Sn+1 в конец стека - преобразование < S1,...,Sn> в < S1,...,Sn+1>;

изъятие последнего элемента из стека - преобразование < S1,...,Sn-1,Sn> в < S1,...,Sn-1>;

доступ к его последнему элементу Sn, если стек не пуст.

Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху.

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

Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов.

Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.

Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией.

Например, выражение

(6+8) *5-6/2

в польской инверсной записи имеет вид

6 8 + 5 * 6 2/-

Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид

S = <>; <6>; <6,8>; <14>; <14,5>; <70>;

<70,6>; <70,6,2>; <70,3>; <67>.

Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m [i] >0 означает неотрицательное число, а значения m [i] <0 операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа 1, 2, 3,4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l.

float eval (float *m, int l) { int p,n, i; float stack [50],c;

for(i=0; i < l; i++) if ((n=m [i]) <0) { c="st [p--] ; " switch(n) { case 1: stack [p] +="c; " break; case 2: stack [p] -="c; " break; case 3: stack [p] *="c; " break; case 4: stack [p] /="c; " } } else stack [++p] ="n; " return(stack [p]); }

Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1. " то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.

#include

typedef struct st /* объявление типа STACK */

{ char ch;

struct st *ps; } STACK;

main()

{ STACK *p,*q;

char a;

p=NULL;

do /* заполнение стека */

{ a=getch();

q=malloc(sizeof(STR1));

q->ps=p; p=q;

q->ch=a;

} while(a! ='. ');

do /* печать стека */

{ p=q->ps; free(q); q=p;

printf("%c",p->ch);

} while(p->ps! =NULL);

}

1.1.6 Сжатое и индексное хранение линейных списков

При хранении больших объемов информации в форме линейных списков нежелательно хранить элементы с одинаковым значением, поэтому используют различные методы сжатия списков.

Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B'= получается из B заменой каждого элемента Ki на пару Ki'=(i,Ki). Пусть далее B"= - подсписок B', получающийся вычеркиванием всех пар Ki=(i,V). Сжатым хранением В является метод хранения В", в котором элементы со значением V умалчиваются. Различают последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.22,23.

Рис.12. Связное сжатое хранение списка.

Достоинство сжатого хранения списка при большом числе элементов со значением V заключается в возможности уменьшения объема памяти для его хранения.

Поиск i-го элемента в связанном сжатом хранении осуществляется методом полного просмотра, при последовательном хранении - методом бинарного поиска.

Преимущества и недостатки последовательного сжатого и связанного сжатого хранений аналогичны преимуществам и недостаткам последовательного и связанного хранений.

Рассмотрим следующую задачу. На входе заданы две последовательности целых чисел M=, N=, причем 92% элементов последовательности М равны нулю. Составить программу для вычисления суммы произведений Mi * Ni, i=1,2,...,10000.

Предположим, что список М хранится последовательно сжато в массиве структур m с объявлением:

struct

{ int nm;

float val; } m [10000] ;

Для определения конца списка добавим еще один элемент с порядковым номером m [j]. nm=10001, который называется стоппером (stopper) и располагается за последним элементом сжатого хранения списка в массиве m.

Программа для нахождения искомой суммы имеет вид:

# include

main()

{ int i,j=0;

float inp,sum=0;

struct /* объявление массива */

{ int nm; /* структур */

float val; } m [10000] ;

for(i=0; i<10000; i++) /* чтение списка M */ { scanf("%f",&inp); if (inp! ="0)" { m [j]. nm="i; " m [j++]. val="inp; " } } m [j]. nm="10001; " /* stopper */ for(i="0,j=0; " i<10000; i++) { scanf("%f",&inp); /* чтение списка N */ if(i="=m [j]. nm)" /* вычисление суммы */ sum+="m [j++]. val*inp; " } printf("сумма произведений Mi*Ni равна%f",sum); }

Индексное хранение используется для уменьшения времени поиска нужного элемента в списке и заключается в следующем. Исходный список B = разбивается на несколько подсписков В1, В2,..., Вm таким образом, что каждый элемент списка В попадает только в один из подсписков, и дополнительно используется индексный список с М элементами, указывающими на начало списков В1, В2,..., Вm.

Считается, что список хранится индексно с помощью подсписков B1,B2,...,Bm и индексного спискa X =, где ADGj - адрес начала подсписка Bj, j=1,M.

При индексном хранении элемент К подсписка Bj имеет индекс j. Для получения индексного хранения исходный список В часто преобразуется в список В' путем включения в каждый узел еще и его порядкового номера в исходном списке В, а в j-ый элемент индексного списка Х, кроме ADGj, может включаться некоторая дополнительная информация о подсписке Bj. Разбиение списка В на подсписки осуществляется так, чтобы все элементы В, обладающие определенным свойством Рj, попадали в один подсписок Bj.

Достоинством индексного хранения является то, что для нахождения элемента К с заданным свойством Pj достаточно просмотреть только элементы подсписка Bj; его начало находится по индексному списку Х, так как для любого К, принадлежащего Bi, при i не равном j свойство Pj не выполняется.

В разбиении В часто используется индексная функция G(K), вычисляющая по элементу К его индекс j, т.е. G(K) =j. Функция G обычно зависит от позиции К, обозначаемой поз. K, в подсписке В или от значения определенной части компоненты К - ее ключа.

Рассмотрим список B= с элементами

К1=(17,Y), K2=(23,H), K3=(60, I), K4=(90,S), K5=(66,T),

K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).

Если для разбиения этого списка на подсписки в качестве индексной функции взять Ga(K) =1+(поз. K-1) /3, то список разделится на три подсписка:

B1a=<(17,Y),(23,H),(60, I) >,

B2a=<(90,S),(66,T),(77,T) >,

B3a=<(50,U),(88,W),(30,S) >.

Добавляя всюду еще и начальную позицию элемента в списке, получаем:

B1a'=<(1,17,Y),(2,23,H),(3,60, I) >,

B2a'=<(4,90,S),(5,66,T),(6,77,T) >,

B3a'=<(7,50,U),(8,88,W),(9,30,S) >.

Если в качестве индексной функции выбрать другую функцию Gb(K) =1+(поз. K-1)%3, то получим списки:

B1b"=<(1,17,Y),(4,90,S),(7,50,U) >,

B2b"=<(2,23,H),(5,66,T),(8,88,U) >,

B3b"=<(3,60, I),(6,77,T),(9,30,S) >.

Теперь для нахождения узла K6 достаточно просмотреть только одну из трех последовательностей (списков). При использовании функции Ga(K) это список B2a', а при функции Gb(K) список B3b".

Для индексной функции Gc(K) =1+K1/100, где K1 - первая компонента элемента К, находим:

B1=<(17,Y),(23,H),(60, I),(90,S) >,

B2=<(66,T),(77,T) >,

B3=<(50,U),(88,W) >,

B4=<(30,S) >.

Чтобы найти здесь узел К с первым компонентом-ключом К1=77, достаточно просмотреть список B2.

При реализации индексного хранения применяется методика А для хранения индексного списка Х (функция Ga(X)) и методика C для хранения подсписков B1,B2,...,Bm (функция Gc(Bi)), т.е. используется, так называемое, A-C индексное хранение.

В практике часто используется последовательно-связанное индексное хранение. Так как обычно длина списка индексов известна, то его удобно хранить последовательно, обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B1,B2,...,Bm хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ для организации, так называемых, индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен как последовательно, так и при помощи ключа.

Последовательно-связанное индексное хранение для приведенного примера изображено на рис.24, где X=.

Рис.13. Последовательно-связанное индексное хранение списка.

Рассмотрим еще одну задачу. На входе задана последовательность целых положительных чисел, заканчивающаяся нулем. Составить процедуру для ввода этой последовательности и организации ее последовательно-связанного индексного хранения таким образом, чтобы числа, совпадающие в двух последних цифрах, помещались в один подсписок.

Выберем в качестве индексной функции G(K) =K%100+1, а в качестве индексного списка Х - массив из 100 элементов. Следующая функция решает поставленную задачу:

#include

#include

typedef struct nd

{ float val;

struct nd *n; } ND;

int index (ND *x [100])

{ ND *p;

int i,j=0;

float inp;

for (i=0; i<100; i++) x [i] ="NULL; " scanf("%d",&inp); while (inp! ="0)" { j++; p="malloc(sizeof(ND)); " i="inp%100+1; " p->val=inp;

p->n=x [i] ;

x [i] =p;

scanf("%d",&inp);

}

return j;

}

Возвращаемым значением функции index будет число обработанных элементов списка.

Для индексного списка также может использоваться индексное хранение. Пусть, например, имеется список B= с элементами

K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214, I), K5 =(146,C),

K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).

Требуется разделить его на семь подсписков, т.е. X= таким образом, чтобы в каждый список B1,B2,...,B7 попадали элементы, совпадающие в первой компоненте первыми двумя цифрами. Список Х, в свою очередь, будем индексировать списком индексов Y=, чтобы в каждый список Y1,Y2,Y3 попадали элементы из X, у которых в первой компоненте совпадают первые цифры. Если списки B1,B2,...,B7 хранить связанно, а списки индексов X,Y индексно, то такой способ хранения списка B называется связанно-связанным связанным индексным хранением. Графическое изображение этого хранения приведено на рис.14.

Рис.14. Связанно-связанное связанное индексное хранение списка.

1.1.7 Сортировка и слияние списков

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

1.1.7.1 Пузырьковая сортировка

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=, в котором для любого 1<=i<=n элемент K'(i) <="K'(i+1). "

При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.

Пример:

B=<20,-5,10,8,7>, исходный список;

B1=<-5,10,8,7, 20>, первый просмотр;

B2=<-5,8,7,10, 20>, второй просмотр;

B3=<-5,7,8,10, 20>, третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.

Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.

/* сортировка пузырьковым методом */

float * bubble(float * a, int m, int n)

{

char is=1;

int i;

float c;

while(is)

{ is=0;

for (i=m+1; i<=n; i++) if (a [i] < a [i-1]) { c="a [i] ; " a [i] ="a [i-1] ; " a [i-1] ="c; " is="1; " } } return(a); }

Пузырьковая сортировка выполняется при количестве действий Q=(n-m) *(n-m) и не требует дополнительной памяти.

1.1.7.2 Сортировка вставкой

Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.

Например, для начального списка B=<20,-5,10,8,7> имеем:

B=<20,-5,10,8,7> B'=<>

B=<-5,10,8,7> B'=<20>

B=<10,8,7> B'=<-5, 20>

B=<8,7> B'=<-5,10, 20>

B=<7> B'=<-5,8,10, 20>

B=<> B'=<-5,7,8,10, 20>

Функция insert реализует сортировку вставкой.

/* сортировка методом вставки */

float *insert(float *s, int m, int n)

{

int i,j,k;

float aux;

for (i=m+1; i<=n; i++) { aux="s [i] ; " for (k="m; " k<="i" && s [k] =k; j--) s [j+1] =s [j] ;

s [k] =aux;

}

return(a);

}

Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.26).

При сортировке вставкой требуется Q=(n-m) *(n-m) сравнений и не требуется дополнительной памяти.

Рис.15. Схема движения индексов при сортировке вставкой.

1.1.7.3 Сортировка посредством выбора

Упорядоченный список В' получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В', который первоначально должен быть пустым.

Например:

B=<20,10,8,-5,7>, B'=<>

B=<20,10,8,7>, B'=<-5>

B=<20,10,8>, B'=<-5,7>

B=<20,10>, B'=<-5,7,8>

B=<20>, B'=<-5,7,8,10>

B=<>, B'=<-5,7,8,10, 20>.

Функция select упорядочивает массив s сортировкой посредством выбора.

/* сортировка методом выбора */

double *select(double *s, int m, int n)

{

int i,j;

double c;

for (i=m; is [j])

{ c=s [i] ;

s [i] =s [j] ;

s [j] =c;

}

return(s);

}

Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s (см. рис.27). При сортировке посредством выбора требуется Q=(n-m) *(n-m) действий и не требуется дополнительной памяти.

Рис.16. Схема движения индексов при сортировке выбором.

Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М подсписков В1, В2,..., Вm, где М равно квадратному корню из N, и в каждом В1 находится минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный элемент Gj в списке, и выбранный элемент Gj заменяется новым наименьшим из списка Bj. Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка G.

1.1.7.4 Слияние списков

Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17, 19,23,25,38,39,47,60> из 9 элементов.

Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С.

Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up (см. рис.28).

/* слияние списков */

double *merge(double *s, int low, int up, int l)

{

double *b,*c,v;

int i,j,k;

b=calloc(l,sizeof(double));

c=calloc(up+1-l,sizeof(double));

for(i=low; is [up-1])?

(s [low+l-1] +1): (s [up-1] +1)));

i=(j=0);

k=low;

while(b [i] <V||C [J] < } (s); return k++; s [k] ="b [i++] ; " else if(b [i]

Рис.17. Схема движения индексов при слиянии списков.

1.1.7.5 Сортировка списков путем слияния

Для получения упорядоченного списка B' последовательность значений В= разделяют на N списков В1=, B2=,...,Bn=, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2,...,Bm заменяется на М/2 (или (М+1) /2) упорядоченных списков, B(2i-1) - oго и B(2i) - ого (2i<=M) и добавлением Вm при нечетном М. Проход повторяется до тех пор пока не получится одна последовательность длины N.

Приведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.

Пример:

9/7/18/3/52/4/6/8/5/13/42/30/35/26;

7,9/3,18/4/52/6/8/54/13/30/42/26/35;

3,7,9,18/4,6,8,52/5,13,30,42/26,35;

3,4,6,7,8,9,18,52/5,13,26,30,35,42;

3,4,5,6,7,8,9,13,18,26,30,35,42,52.

Количество действий, требуемое для сортировки слиянием, равно Q=N*log2(N), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.

Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.

/* сортировка слиянием */

double *smerge (double *s, int m, int n)

{ int l,low,up;

double *merge (double *, int, int, int);

l=1;

while(l<=(n-m)) { low="m; " up="m-1; " while (l+up < n) { up="(low+2*l-1" < n)? (low+2*l-1): n; merge (s,low,up,l); low="up-1; " } l*="2; " } return(a); }

Для сортировки массива путем слияния удобно использовать рекурсию. Составим рекурсивную функцию srecmg для сортировки массива либо его части. При каждом вызове сортируемый массив делится на две равных части, каждая из которых сортируется отдельно, а затем происходит их слияние, как это показано на рис.29.

Рис.18. Схема сортировки слиянием.

/* рекурсивная сортировка слиянием 1/2 */

double *srecmg (double *a, int m, int n)

{ double * merge (double *, int, int, int);

double * smerge (double *, int, int);

int i;

if (n>m)

{ i=(n+m) /2;

srecmg(a,m, i);

srecmg(a, i+1,n);

merge(a,m,n,(n-m) /2+1);

}

return (a);

}

1.1.7.6 Быстрая и распределяющая сортировки

Быстрая сортировка состоит в том, что список В= реорганизуется в список B',,B", где В' - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B',,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B' и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками <и>.

Пример:

9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26

7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26

3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26

<3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52>

3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52

3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52

Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B' и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N) /2 шагов.

Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.

/* быстрая сортировка */

double * quick(double *s, int low, int hi)

{ double cnt,aux;

int i,j;

if (hi>low)

{ i=low;

j=hi;

cnt=s [i] ;

while(i < j)

{ if (s [i+1] <=cnt) { s [i] ="s [i+1] ; " s [i+1] ="cnt; " i++; } else { if (s [j] <="cnt)" { aux="s [j] ; " s [j] ="s [i+1] ; " s [i+1] ="aux; " } j--; } } quick(s,low, i-1); quick(s, i+1,hi); } return(s); }

Здесь используются два индекса i и j, проходящие части массива навстречу друг другу (см. рис.30). При этом i всегда фиксирует разделяющий элемент cnt=s [low], слева от которого находятся числа, не большие cnt, а справа от i - числа, большие cnt. Возможны три случая: при s [i+1] <=cnt; при s [i+1] >cnt и s [j] <=cnt; при s [i+1] >cnt и s [j] >cnt. По окончании работы i=j, и cnt=s [i] устанавливается на своем месте.

Рис.19. Схема быстрой сортировки.

Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции quick (неявный стек).

Оценка среднего количества действий, необходимых для выполнения быстрой сортировки списка из N различных чисел, получена как оценка отношения числа различных возможных последовательностей из N различных чисел, равного N!, и общего количества действий C(N), необходимых для выполнения быстрой сортировки всех различных последовательностей. Доказано, что C(N) /N! <2*N*ln(N).

Распределяющая сортировка. Предположим, что элементы линейного списка В есть Т-разрядные положительные десятичные числа D(j,n) - j-я справа цифра в десятичном числе n>=0, т.е. D(j,n) =floor(n/m)%10, где m=10^(j-1). Пусть В0, В1,..., В9 - вспомогательные списки (карманы), вначале пустые.

Для реализации распределяющей сортировки выполняется процедура, состоящая из двух процессов, называемых распределение и сборка для j=1,2,...,T.

PАСПРЕДЕЛЕНИЕ заключается в том, что элемент Кi (i=1,N) из В добавляется как последний в список Bm, где m=D(j,Ki), и таким образом получаем десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m.

СБОРКА объединяет списки В0, В1,..., В9 в этом же порядке, образуя один список В.

Рассмотрим реализацию распределяющей сортировки при Т=2 для списка: B=<09,07,18,03,52,04,06,08,05,13,42,30,35,26>.

РАСПРЕДЕЛЕНИЕ-1:

B0=<30>, B1=<>, B2=<52,42>, B3=<03,13>, B4=<04>,

B5=<05,35>, B6=<06,26>,B7=<07>, B8=<18,08>, B9=<09>.

СБОРКА-1:

B=<30,52,42,03,13,04,05,35,06,26,07,18,08,09>

РАСПРЕДЕЛЕНИЕ-2:

B0=<03,04,05,06,07,08,09>, B1=<13,18>, B2=<26>,

B3=<30,35>, B4=<42>, B5=<52>, B6=<>,B7=<>,B8=<>, B9=<>.

СБОРКА-2:

B=<03,04,05,06,07,08,09,13,18,26,30,35,42,52>.

Количество действий, необходимых для сортировки N T-цифровых чисел, определяется как Q(N*T). Недостатком этого метода является необходимость использования дополнительной памяти под карманы.

Однако можно исходный список представить как связанный и сортировку организовать так, чтобы для карманов В0, В1,..., В9 не использовать дополнительной памяти, элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману.

В представленной ниже программе функция pocket реализует распределяющую сортировку связанного линейного списка (указатель q), в котором содержатся Т-разрядные десятичные положительные числа, без использования дополнительной памяти; в функции a [i], b [i] указывают соответственно на первый и на последний элементы кармана Bi.

/* вызов распределяющeй сортировки списка */

#include

#include

typedef struct str

{ long val;

struct str *n; } SP1;

main()

{ int i;

SP1 *q=malloc(sizeof(SP1)),*r;

SP1 *pocket(SP1 *, int);

long a [14] ={ 0,7,18,3,52,4,6,8,5,13,42,30,35,26 };

q->n=NULL;

q->val=a [0] ;

r=q;

printf("%d",a [0]);

for(i=1; i<14; i++) /* формирование списка */ { r->n=malloc(sizeof(SP1));

r->val=a [i] ;

(r->n) - >n=NULL;

r=r->n;

printf("%d",a [i]);

}

r=pocket(q,2);

printf("\n"); /* печать результатов */

while (r! =NULL)

{ printf("%d",r->val);

r=r->n;

}

}

/* распределяющая сортировка списка */

SP1 *pocket(SP1 *q, int t)

{ int i,j,k,m=1;

SP1 *r, *gg, *a [10], *b [10] ;

gg=q;

for(j=1; j<=t; j++) { for(i="0; i<=9; i++)" a [i] ="(b [i] =NULL); " while(q! ="NULL)" { k="((int) (q-">val/m))%(int) 10;

r=b [k] ;

if (a [k] ==NULL) a [k] =q;

else r->n=q;

r=b [k] =q;

q=q->n;

r->n=NULL;

}

for(i=0; i<=9; i++) if (a [i] ! ="NULL)" break; q="a [i] ; " r="b [i] ; " for(k="i+1; k<=9; k++)" if(a [k] ! ="NULL)" { r->n=a [k] ;

r=b [k] ;

}

m=m*10;

}

return (gg);

}

На рис.31 показана схема включения очередного элемента списка в К-й карман.

Рис. 20. Схема включения очередного элемента списка в карман.

Разновидностью распределяющей сортировки является битовая сортировка. В ней элементы списка интерпретируются как двоичные числа, и D(j,n) обозначает j-ю справа двоичную цифру числа n. При этой сортировке в процессе РАСПРЕДЕЛЕНИЕ требуются только два вспомогательных кармана В0 и В1; их можно разместить в одном массиве, двигая списки В0 и В1 навстречу друг другу и отмечая точку встречи. Для осуществления СБОРКИ нужно за списком В0 написать инвертированный список В1.

Так как выделение j-го бита требует только операций сдвига, то битовая сортировка хорошо подходит для внешней сортировки на магнитных лентах и дисках.

Разновидностью битовой сортировки является бинарная сортировка. Здесь из всех элементов списка B= выделяются его минимальный и максимальный элементы и находится их среднее арифметическое m=(MIN+MAX) /2. Список В разбивается на подсписки В1 и В2, причем в В1 попадают элементы, не большие m, а в список В2 - элементы, большие m. Потом для непустых подсписков В1 и В2 сортировка продолжается рекурсивно.

1.1.8 Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К1, К2, К3,..., Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то

n

Max{А} = max{ Si, i=1,n }; Avg{А} = Pi Si.

i=1

Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера.

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

Пусть во входном потоке задано 100 целых чисел К1, К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

/* последовательный поиск без стоппера */

#include

main()

{

int k [100],v, i;

for (i=0; i<100; i++) scanf("%d",&k [i]); scanf("%d",&v); i="0; " while(k [i] ! ="v" && i<100) i++; if (k [i] ="=v)" printf("%d%d",v, i); else printf("%d не найден",v); }

С использованием стоппера программу можно записать в виде:

/* последовательный поиск со стоппером */

#include

main()

{

int k [101],v, i;

for (i=0; i<100; i++) scanf("%d",&k [i]); /* ввод данных */ scanf("%d",&v); k [100] ="v; " /* стоппер */ i="0; " while(k [i] ! ="v)" i++; if (i<100) printf ("%d%d",v, i); else printf ("%d не найден",v); }

1.1.9. Бинарный поиск

Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

Пусть, например, во входном потоке задано 101 число, К1, К2,..., К100, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1, К2,..., К100.

/* Бинарный поиск */

#include

main()

{

int k [100],v, i,j,m;

for (i=0; i<100; i++) scanf("%d",&k [i]); scanf("%d",&v); i="0; " j="100; " m="50; " while (k [m] ! ="v)" { if (k [m] < v) i+="m; " else j="m-i; " m="(i+j) /2; " } printf("%d%d",v,m); }

1.1.10 М-блочный поиск

Этот способ удобен при индексном хранении списка. Предполагается, что исходный упорядоченный список B длины N разбит на M подсписков B1,B2,...,Bm длины N1,N2,...,Nm, таким образом, что B=B1,B2,. .,Bm.

Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний элемент которого больше V, а потом применить последовательный поиск к списку Bi.

Хранение списков Bi может быть связным или последовательным. Если длины всех подсписков приблизительно равны и M= N, то Max М-блочного поиска равен 2 N. При одинаковой частоте использования элементов Avg М-блочного поиска равен N.

Описанный алгоритм усложняется, если не известно, действительно ли в списке имеется элемент, совпадающий с ключом V. При этом возможны случаи: либо такого элемента в списке нет, либо их несколько.

Если вместо ключа V имеется упорядоченный список ключей, то последовательный или М-блочный поиск может оказаться более удобным, чем бинарный, поскольку не требуется повторной инициализации для каждого нового ключа из списка V.

1.1.11 Методы вычисления адреса

Методы вычисления адреса. Пусть в каждом из М элементов массива Т содержится элемент списка (например целое положительное число). Если имеется некоторая функция H(V), вычисляющая однозначно по элементу V его адрес - целое положительное число из интервала [0,M-1], то V можно хранить в массиве T с номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит за постоянное время не зависящее от M.

Массив T называется массивом хеширования, а функция H - функцией хеширования.

При конкретном применении хеширования обычно имеется определенная область возможных значений элементов списка V и некоторая информация о них. На основе этого выбирается размер массива хеширования M и строится функция хеширования. Критерием для выбора M и H является возможность их эффективного использования.

Пусть нужно хранить линейный список из элементов K1,K2,. .,Kn, таких, что при Ki=Kj, mod(Ki,26) = mod(Kj,26). Для хранения списка выберем массив хеширования T(26) с пространством адресов 0-25 и функцию хеширования H(V) = mod(V,26). Массив T заполняется элементами T(H(Ki)) =Ki и T(j) =0 если j (H(K1), H(K2),. .,H(Kn)).

Поиск элемента V в массиве T с присваиванием Z его индекса если V содержится в T, или - 1, если V не содержится в T, осуществляется следующим образом

int t [26],v,z, i;

i=(int) fmod((double) v,26.0);

if(t [i] ==v) z=i;

else z=-1;

Добавление нового элемента V в список с возвращением в Z индекса элемента, где он будет храниться, реализуется фрагментом

z=(int) fmod((doule) v,26.0);

t [z] =v;

а исключение элемента V из списка присваиванием

t [(int) fmod((double) v,26)] =0;

Теперь рассмотрим более сложный случай, когда условие Ki=Kj H(Ki) =H(Kj) не выполняется. Пусть V - множество возможных элементов списка (целые положительные числа), в котором максимальное число элементов равно 6. Возьмем M=8 и в качестве функции хеширования выберем функцию H(V) =Mod(V,8).

Предположим, что B=, причем H(K1) =5, H(K2) =3, H(K3) =6, H(K4) =3, H(K5) =1, т.е. H(K2) =H(K4) хотя K2=K4. Такая ситуация называется коллизией, и в этом случае при заполнении массива хеширования требуется метод для ее разрешения. Обычно выбирается первая свободная ячейка за собственным адресом. Для нашего случая массив T [8] может иметь вид

T=<0,K5,0,K2,K4,K1,K3,0>.

При наличии коллизий усложняются все алгоритмы работы с массивом хеширования. Рассмотрим работу с массивом T [100], т.е. с пространством адресов от 0 до 99. Пусть количество элементов N не более 99, тогда в T всегда будет хотя бы один свободный элемент равный нулю. Для объявления массива используем оператор

int static t [100] ;

Добавление в массив T нового элемента Z с занесением его адреса в I и числа элементов в N выполняется так:

i=h(z);

while (t [i] ! =0 && t [i] ! =z)

if (i==99) i=0;

else i++;

if (t [i] ! =z) t [i] =z, n++;

Поиск в массиве T элемента Z с присвоением I индекса Z, если Z имеется в T, или I=-1, если такого элемента нет, реализуется следующим образом:

i=h(z);

while (t [i] ! =0 && t [i] ! =z)

if (i==99) i=0;

else i++;

if (t [i] ==0) i=-1;

При наличии коллизий исключение элемента из списка путем пометки его как пустого, т.е. t [i] =0, может привести к ошибке. Например, если из списка B исключить элемент K2, то получим массив хеширования в виде T=<0,K5,0,0,K4,K1,K3,0>, в котором невозможно найти элемент K4, поскольку H(K4) =3, а T(3) =0. В таких случаях при исключении элемента из списка можно записывать в массив хеширования некоторое значение не принадлежащее области значений элементов списка и не равное нулю. При работе с таким массивом это значение будет указывать на то, что нужно просматривать со средние ячейки.

Достоинство методов вычисления адреса состоит в том, что они самые быстрые, а недостаток в том, что порядок элементов в массиве T не совпадает с их порядком в списке, кроме того довольно сложно осуществить динамическое расширение массива T.

1.1.12 Выбор в линейных списках

Задача выбора. Задан линейный список целых, различных по значению чисел B=, требуется найти элемент, имеющий i-тое наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 поиску элемента с вторым наибольшим значением.

Поставленная задача может быть получена из задачи поиска j-того минимального значения заменой i=n-j+1 и поиском i-того максимального значения. Особый интерес представляет задача выбора при i=a/n, 0<a<1, в частности, задача выбора медианы при a=1/2.

Все варианты задачи выбора легко решаются, если список B полностью отсортирован, тогда просто нужно выбрать i-тый элемент. Однако в результате полной сортировки списка B получается больше информации, чем требуется для решения поставленной задачи.

Количество действий можно уменьшить применяя сортировку выбором только частично до i-того элемента. Это можно сделать, напри мер при помощи функции findi

/* выбор путем частичной сортировки */

int findi(int *s, int n, int i)

{

int c,j,k;

for (k=0; k<=i; k++) for (j="k+1; " j<="n; " j++) if (s [k] < s [j]) { c="s [k] ; " s [k] ="s [j] ; " s [j] ="c; " } return s [i] ; }

Эта функция ищет элемент с индексом i, частично сортируя массив s, и выполняет при этом (n*i) сравнений. Отсюда следует, что функция findi приемлима для решения задачи при малом значении i, и малоэффективна при нахождении медианы.

Для решения задачи выбора i-того наибольшего значения в списке B модифицируем алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B' и B", такие, что если Ki - B', то Ki>K1, и если Ki - B", то Ki<K1, и список B реорганизуется в список B',K1,B". Если K1 элемент располагается в списке на j-том месте и j=i, то искомый элемент найден. При j>i наибольшее значение ищется в списке B'; при j<i будем искать (i-j) значение в подсписке B".

Алгоритм выбора на базе быстрой сортировки в общем эффективен, но для улучшения алгоритма необходимо, чтобы разбиение списка на подсписки осуществлялось почти пополам. Следующий алгоритм эффективно решает задачу выбора i-того наибольшего элемента в списке B, деля его на подсписки примерно равной величины.