Информатика. Общая информатика. Основы языка C++. Мамонова Т.Е. - 142 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

Выбирается минимальный элемент массива и меняется местами
с первым элементом массива. Затем процесс повторяется с оставшимися
элементами и т.д.
Пример 44. Сортировка методом выбора.
int i,min,n_min,j;
for(i=0;i<n-1;i++)
{
min=a[i];n_min=i;//поиск минимального
for(j=i+1;j<n;j++)
if(a[j]<min){min=a[j];n_min=j;}
a[n_min]=a[i];//обмен
a[i]=min;
}
Сортировка методом простого обмена
Сравниваются и меняются местами пары элементов, начиная с по-
следнего. В результате самый маленький элемент массива оказывается
самым левым элементом массива. Процесс повторяется с оставшимися
элементами массива.
Пример 45. Сортировка методом простого обмена
for(int i=1;i<n;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
{int r=a[j];a[j]=a[j-1];a[j-1]=r;}
}
Поиск в отсортированном массиве
В отсортированном массиве используется дихотомический (бинар-
ный) поиск. При последовательном поиске требуется в среднем n/2
сравнений, где n – количество элементов в массиве. При дихотомиче-
ском поиске требуется не более m сравнений, если n-m-я степень 2, если
n не является степенью 2, то n < k = 2
m
.
Массив делится пополам S:=(L+R)/2+1 и определяется, в какой ча-
сти массива находится нужный элемент Х. Т.к. массив упорядочен, то
если a[S] < X, то искомый элемент находится в правой части массива,
иначе – находится в левой части. Выбранную часть массива снова надо
разделить пополам и т.д., до тех пор, пока границы отрезка L и R не ста-
нут равны [11].
Пример 46
int b;
142

Страницы