236______________________________Часть II. Программирование на C++
ходимости меняются местами. Таким образом происходит сортировка массива. Реализация этого алгоритма сортировки на С принадлежит Бриану Керникан и Дэннису Ритчи.
#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. Внешний цикл устанавливает начальный интервал между сравниваемыми элементами в половину размера массива. При каждой итерации интервал уменьшается в два раза. Внешний цикл завершается тогда,