Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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

Читайте также:
  1. II. Индукция методом исключения
  2. Pасчет простого трубопровода постоянного сечения
  3. XVI. Принятие решений. Процесс выбора
  4. А. ЛАБОРАТОРНОЕ ИЗМЕРЕНИЕ ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ НА ГРАНИЦЕ РАЗДЕЛА ЖИДКОСТИ МЕТОДОМ СЧЕТА КАПЕЛЬ
  5. Автоматическое создание простого отчета.
  6. Алгоритм решения ЗЛП графическим методом
  7. Билет № 10. 1.Сущность процесса дефектовки деталей люминисцентным методом.
  8. Билет № 3. Альтернативные издержки и проблема экономического выбора.
  9. БУФЕРНЫЕ СИСТЕМЫ. ИЗУЧЕНИЕ СВОЙСТВ БУФЕРНЫХ И НЕБУФЕРНЫХ СИСТЕМ.ОПРЕДЕЛЕНИЕ БУФЕРНОЙ ЕМКОСТИ РАСТВОРА.ОПРЕДЕЛЕНИЕ рН ПОТЕНЦИОМЕТРИЧЕСКИМ МЕТОДОМ В БИОЛОГИЧЕСКИХ ОБЪЕКТАХ.
  10. Быстрая и точная диагностика заболеваний щитовидной железы методом тонкоигольной аспирационной биопсии под контролем ультразвука

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

  мин      

 

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=2m.

Массив делится пополам 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;


 

Указатели


Дата добавления: 2015-01-29; просмотров: 3; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Задачи 4-ого класса | Понятии указателя
lektsii.com - Лекции.Ком - 2014-2018 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты