40. Метод пузырьковой сортировки

Операция сравнения/перестановки выполняется для каждых двух стоящих рядом элементов. После первого прохода по массиву "вверху" оказывается самый "легкий" элемент. Следующий цикл сортировки выполняется начиная со второго элемента, в результате чего вторым в массиве оказывается второй наименьший по величине элемент, и так далее. Алгоритм прост и крайне неэффективен.

void sort_bubble(int a[], int max) // пузырьковая сортировка

{

for (int i=0; i<max; i++)

for (int j=max-1; j>i; j--)

if (less(a[j], a[j-1]))

swap(a[j], a[j-1]);

}

41. Метод сортировки прямым выбором

Во время i-го прохода по массиву выявляется наименьший элемент, который затем меняется местами с i-м. Все остальное аналогично пузырьковой сортировке.

void sort_choose(int a[], int max) // сортировка выбором

{

for (int i=0; i<max; i++)

{

int k=i;

for (int j=i+1; j<max; j++)

if (less(a[j], a[k]))

k=j;

if (i!=k)

swap(a[i], a[k]);

}

}

42. Метод сортировки прямыми вставками

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.  Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда

Hайден элемент, меньший x или

Достигнуто начало последовательности.

template<class T>

void insertSort(T a[], long size) {

T x;

long i, j;

for ( i=0; i < size; i++) { // цикл проходов, i - номер прохода

x = a[i];

// поиск места элемента в готовой последовательности

for ( j=i-1; j>=0 && a[j] > x; j--)

a[j+1] = a[j]; // сдвигаем элемент направо, пока не дошли

// место найдено, вставить элемент

a[j+1] = x;

}

}

43. Структура (составные части) метода. Форма определения метода.

Для определения методов используется следующий формат:

возвращаемый-тип идентификатор-метода (параметры)

{

тело-метода

}

Пример объявления метода, возвращающего значение типа int – сумму двух своих параметров типаint:

int sum(int a, int b)

{

int x;

x = a + b;

return x;

}

44. Особенности методов, возвращающих значения. Оператор return.

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

В качестве примера создадим метод для вычисления суммы квадратов двух целых чисел. Как и в случае с программой, важно в первую очередь определить входные и выходные данные. Входные данные — это параметры метода. Выходные данные — это его возвращаемое значение.

Простейший вариант метода будет выглядеть следующим образом:

long squearSum(int x, int y) {return x*x + y*y;}