Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге

элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же

подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом

По ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше,

последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и

неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в

Готовую часть массива.

Поиск подходящего места для очередного элемента входной последовательности осуществляется

Путем последовательных сравнений с элементом, стоящим перед ним.

В зависимости от результата сравнения элемент либо остается на текущем месте(вставка

Завершена), либо они меняются местами и процесс повторяется.

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;

}

}Алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный сторожевой элемент. Он должен быть заведомо меньше всех остальных элементов массива. // сортировка вставками со сторожевым элементом

template<class T>

inline void insertSortGuarded(T a[], long size) {

T x;

Long i, j;

T backup = a[0]; // сохранить старый первый элемент

setMin(a[0]); // заменить на минимальный

// отсортировать массив

for (i=1; i < size; i++) {

x = a[i];

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

a[j+1] = a[j];

a[j+1] = x;

}

// вставить backup на правильное место

for (j=1; j<size && a[j] < backup; j++)

a[j-1] = a[j];

// вставка элемента

a[j-1] = backup;

}

16. int increment(long inc[], long size) {

Int p1, p2, p3, s;

p1 = p2 = p3 = 1;

s = -1;

do {

if (++s % 2) {

inc[s] = 8*p1 - 6*p2 + 1;

} else {

inc[s] = 9*p1 - 9*p3 + 1;

p2 *= 2;

p3 *= 2;

}

p1 *= 2;

} while(3*inc[s] < size);

return s > 0? --s: 0;

}

template<class T>

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

long inc, i, j, seq[40];

Int s;

// вычисление последовательности приращений

s = increment(seq, size);

while (s >= 0) {

// сортировка вставками с инкрементами inc[]

inc = seq[s--];

for (i = inc; i < size; i++) {

T temp = a[i];

for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)

a[j+inc] = a[j];

a[j+inc] = temp;

}

}

}

17. template<class T>

void downHeap(T a[], long k, long n) {

// процедура просеивания следующего элемента

// До процедуры: a[k+1]...a[n] - пирамида

// После: a[k]...a[n] - пирамида

T new_elem;

Long child;

new_elem = a[k];

while(k <= n/2) { // пока у a[k] есть дети

child = 2*k;

// выбираем большего сына

if(child < n && a[child] < a[child+1])

child++;

if(new_elem >= a[child]) break;

// иначе

a[k] = a[child]; // переносим сына наверх

k = child;

}

a[k] = new_elem;

}

Учитывая, что высота пирамиды h <= log n, downheap требует O(log n) времени. Полный код процедуры

построения пирамиды будет иметь вид:

// вызвать downheap O(n) раз для преобразования массива в пирамиду целиком

for(i=size/2; i >= 0; i--) downHeap(a, i, size-1);

18. На входе массив a[0]...a[N] и опорный элемент p, по которому будет производиться разделение.

1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец

Последовательности.

Date: 2016-07-25; view: 223; Нарушение авторских прав