Сортировка посредством выбора
Упорядоченный список В' получается из В многократным применением выборки из В
минимального элемента, удалением этого элемента из В и добавлением его в конец списка
В', который первоначально должен быть пустым.
Например:
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) действий и не
требуется дополнительной памяти.
Рис.27. Схема движения индексов при сортировке выбором.
Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М
подсписков В1,В2,...,Вm, где М равно квадратному корню из N, и в каждом В1 находится
минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный
элемент Gj в списке , и выбранный элемент Gj заменяется новым наименьшим из списка Bj.
Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше,
чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка
G.