Выбор в линейных списках заключается в следующем. Задан линейный список целых, различных по значению чисел B=<K1,K2. ...Kn>, требуется найти элемент, имеющий 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, деля его на подсписки примерно равной величины.
1. Если N<21, то выбрать i-тый наибольший элемент списка B обычной сортировкой.
2. Если N>21 разделим список на 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. При j>i повторим процедуру поиска сначала, но только в подсписке 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<21) return findi(b, n, i);    /*  шаг 1  */
  p=(int)(n/7);
  w=calloc(p+1,sizeof(int));          /*   шаги 2 и 3   */
  for (t=0; t < p; t++)
  w[t]=findi(b+7*t, 7, 3);
  if (n%7!=0)
    { w[p]=findi(b+7*p,n%7,(n%7)/2);
      p++;
    }
  m=search(w, p, p/2);
  free (w);
  for (j=0, t=0; t < n; t++)         /*   шаг 4   */
  if (b[t]>=m) j++;
  if (j>i)
    {
      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<100; k++)
  b[k]=k; /* заполнение массива */
  for (k=1; k < l/4; k++)
   { t=b[k];      /*   перемешивание   */
     b[k]=b[l-k]; /*    массива   */
     b[l-k]=t;
   }
  k=search(b,l,i);    /*   выбор  элемента   */
  printf ("\n выбран элемент равный %d\n\n",k);
  return 0;
}
Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28*N сравнений. Действительно, если N<21, то выполнение функции findi потребует сравнений порядка N*(N-1)/2, т.е. меньше чем 28*N. Предположим, что для любого T<N количество сравнений при выполнении функции search не более 28*T и подсчитаем, сколько сравнений потребуется функции search при произвольном значении N. Для поиска медианы в каждом из подсписков функцией findi требуется не более 7*(7-1)/2=21 сравнений, а для формирования массива W в целом не более 21*(N/7)=3*N сравнений. По предположению индукции для поиска медианы в массиве W длины N/7 требуется 28*(N/7)=4*N сравнений. После удаления из B части элементов с помощью медианы в B' (или в B") останется не более N*5/7 элементов, и для удаления ненужных элементов необходимо количество сравнений порядка N. Для поиска в оставшейся части массива (в B' или B") по предположению индукции требуется не более 28*(N*5/7)=20*N сравнений. Таким образом, всего потребуется 3*N+4*N+N+20*N=28*N сравнений, т.е. выдвинутое предположение доказано.