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

Прежде всего, находим наименьший элемент массива. Меняем его местами с x[0] . Затем наименьший из оставшихся меняем местами с x[1] и т.д. Может случиться, что наименьший элемент в рассматриваемом подмассиве уже стоит на первом месте. В этом случае перестановки не нужны. Определим переменную exchange , которая будет признаком того, что перестановка не нужна. Приходим к следующему тексту подпрограммы и вызывающей программы:

# include < stdio . h >

#include <time.h>

#include <stdlib.h>

#include <conio.h>

void select (int *x, int n)

{

int i, j, k, exchange;

int temp;

for (i=0; i<n-1; i++)

{ exchange =0; //нет перестановок

k = i ; //номер наименьшего

temp = x [ i ]; //значение наименьшего

for ( j = i +1; j < n ; j ++)

if (x[j] < temp)

{

k = j ; temp = x [ j ];//номер и значение наименьшего среди

exchange=1; //перестановка нужна

}

if (exchange)

{

x[k]=x[i]; x[i]=temp;

}

}

}

main()

{ int a[20]; int i;

с lrscr();

randomize();

printf(" До сортировки :\n");

for (i=0; i<20; i++){

a[i]=random(100); printf(" %d ", a[i]); }

printf ("\ n ");

select ( a , 20); //вызов программы сортировки

printf(" После сортировки :\n");

for (i=0; i<20; i++)

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

}

Результат работы программы

До сортировки:

80 41 92 63 91 5 3 23 68 78 66 15 27 46 7 33 33 6 52 36

После сортировки:

3 5 6 7 15 23 27 33 33 36 41 46 52 63 66 68 78 80 91 92

Этот алгоритм имеет n ( n -1)/2 сравнений. Число копирований в худшем случае равно n 2 /4+3( n -1).