2.2. Сортировка методом прямого выбора
 

Алгоритм сортировки заключается в следующем:

1. В исходной последовательности из n элементов отыскива¬ется элемент с наименьшим ключом. 2. Он меняется местами с первым элементом. 3. В оставшейся последовательности из (n - 1) элементов отыскивается минимальный элемент и меняется местами со вторым элементом и т.д., пока не останется один, самый большой элемент.

Число сравнений С = (п² - n), число перестановок: М_min=(n-1), М_средн = n(In n + g), где g = 0.577216 — константа Эйлера, M_max=n²/4+3(n-1).

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

Пример.

/* СОРТИРОВКА ПОСРЕДСТВОМ ПРЯМОГО ВЫБОРА */
#include
#include
#define n 8
int A[n]={27,412,71,81,59,14,273,87};
main()
{ void StrSel(int A[],int nn);
int j;
printf("\n Исходный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
StrSel(A,n);
printf("\n Отсортированный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n"); getch();
return 0;
}
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ */
void StrSel(int A[],int nn)
{ int i,j,x,k;
for (i=0; i<nn-1; i++)
{ x=A[i]; k=i; printf("\n %d",i);
for (j=j+1; j<nn; j++)
if (A[j]<x)
{ k=j; x=A[k]; }
A[k]=A[i]; A[i]=x;
/* Отладочная печать по шагам сортировки */
for (j=0; j<nn;j++)
printf("\t %d”,A[j]);
}
}

Исходный массив:
27   412   71    81   59    14    273   87
Отладочная печать по шагам сортировки:
0   14  412  71  81  59  27  273  87
1   14  27  71  81  59  412  273  87
2   14  27  59  81  71  412  273  87
3   14  27  59  71  81  412  273  87
4   14  27  59  71  81  412  273  87
5   14  27  59  71  81  87  273  412
6   14  27  59  71  81  87  273  412

Отсортированный массив:
14   27   59   71   81   87   273   412.
Несмотря на то, что после пятого шага последовательность уже отсортирована, сортировка продолжается.