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

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

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;

}

Сортировка методом простого обмена

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

				94

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 не станут равны.

L S R

S=(L+R)/2=4

int b;

cout<<"\nB=?";cin>>b;

int l=0,r=n-1,s;

do

{

s=(l+r)/2;//средний элемент

if(a[s]<b)l=s+1;//перенести леую границу

else r=s;//перенести правую границу

}while(l!=r);

if(a[l]==b)return l;

else return -1;

Указатели