236______________________________Часть II. Программирование на C++

ходимости меняются местами. Таким образом происходит сортировка массива. Реализация этого алгоритма сортировки на С принадлежит Бриану Керникан и Дэннису Ритчи.

h02361.jpg

#include <stdlib.h>

#include <iostream.h>

void main() (

const int ARRAY_SIZE = 10;

int array[ARRAY_SIZE] ;

for (int i = 0; i < ARRAY_SIZE; i++) array[i] = rand();

cout « "Изначальный массив:\n";

for (int i = 0; i < ARRAY_SIZE; i++) cout « " " « array(i];

for (int gap = ARRAYJ3IZE/2; gap > 0; gap /= 2) for (int i = gap; i < ARRAY_SIZE; i++)

for (int j = i-gap; (j >= 0) && (array[j] > array[j+gap]:

j — gap) { int temp = array [j];

arrayij] = array[j+gap] ;

arraytj+gap] = temp;

}

cout « "\п0тсортированный массив:\n";

for (int i = 0; i < ARRAYJ3IZE; i++) cout « " " « array[i];

cout « endl;

}

После компиляции и запуска программы на экране появляется:

Исходный массив:

2 5030 615 130 10982 1090 11656 7117 17595 6415 22948 Отсортированный массив:

2 130 615 1090 5030 6415 7117 10982 11656 17595 22948

' 1

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

Сначала массив заполняется случайными числами, которые генерирует компьютер. Функция rand (), которую можно найти в stdlib.h, используется для генерации случайных чисел. Алгоритм сортировки состоит из 3-х вложенных циклов for. Внешний цикл устанавливает начальный интервал между сравниваемыми элементами в половину размера массива. При каждой итерации интервал уменьшается в два раза. Внешний цикл завершается тогда,