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

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

			42

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

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;

…

Постановка задачи

1) Сформировать массив из n элементов с помощью датчика случайных чисел (n задается пользователем с клавиатуры).

2) Распечатать полученный массив.

3) Выполнить удаление указанных элементов из массива.

4) Вывести полученный результат.

5) Выполнить добавление указанных элементов в массив.

6) Вывести полученный результат.

7) Выполнить перестановку элементов в массиве.

8) Вывести полученный результат.

9) Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений, необходимых для поиска нужного элемента.

10) Вывести полученный результат.

11) Выполнить сортировку массива указанным методом.

12) Вывести полученный результат.

13) Выполнить поиск указанных элементов в отсортированном массиве и подсчитать количество сравнений, необходимых для поиска нужного элемента.

14) Вывести полученный результат.

Варианты

Методические указания

1. При решении задач использовать псевдодинамические массивы. Псевдодинамические массивы реализуются следующим образом:

1) при определении массива выделяется достаточно большое количество памяти:

const int MAX_SIZE=100;//именованная константа

int mas[MAX_SIZE];

2) пользователь вводит реальное количество элементов массива меньшее N.

int n;

cout<<”\nEnter the size of array<”<<MAX_SIZE<<”:”;cin>>n;

3) дальнейшая работа с массивом ограничивается заданной пользователем размерностью n.

2. Формирование массива осуществляется с помощью датчика случайных чисел. Для этого можно использовать функцию int rand(), которая возвращает псевдослучайное число из диапазона 0..RAND_MAX=32767, описание функции находится в файле <stdlib.h>. В массиве должны быть записаны и положительные и отрицательные элементы. Например, оператор a[I]=rand()%100-50; формирует псевдослучайное число из диапазона [-50;49].

3. Вывод результатов должен выполняться после выполнения каждого задания. Элементы массива рекомендуется выводить в строчку, разделяя их между собой пробелом.

6. Содержание отчета:

1) Постановка задачи (общая и конкретного варианта).

2) Анализ поставленного задания: определить к какому классу задач относится задача и объяснить почему.

3) Текст программы.

4) Результаты тестов.

5) Решение одной из задач с использованием указателей для доступа к элементам массива.