Листинг 5.4

#include “stdafx.h”

#include < iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

const int n = 20;

float *arr = new float[n], middle, temp;

int *stackl = new int[n], *stackr = new int[n];

int sp = 0, i, j, left, right;

setlocale(LC_ALL, " Russian");

cout < < “Введите элементы массива: “;

for(i = 0; i < n; i++) cin > > a[i];

// Сортировка

sp = 1; stackl[1] = 0; stackr[1] = n - 1; // 1

while(sp > 0)

{ // 2

// Выборка из стека последнего запроса

left = stackl[sp]; // 3

right = stackr[sp]; // 4

sp--; // 5

while(left < right)

{ // 6

// Разделение {arr[left]..arr[right]}

i = left; j = right; // 7

middle = arr[(left + right)/2]; // 8

while(i < j)

{ // 9

while(arr[i] < middle) i++; // 10

while(middle < arr[j]) j--; // 11

if(i < = j)

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++; j--;

}

}

if(i < right)

{ // 12

//Запись в стек запроса из правой части

sp++;

stackl[sp] = i;

stackr[sp] = right;

}

right = j; // 13

// Теперь left и right ограничивают левую часть

}

}

// Вывод результата

for(i = 0; i < n; i++) cout < < arr[i] < < “ “;

cout < < endl;

// Удаление динамических массивов

delete[] arr;

delete[] stackl;

delete[] stackr;

getch();

return 0;

}

На каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, правая - в переменной right. Сначала фрагмент уста­навливается размером с массив целиком (строка 1). В операторе 8 выбирается «сред­ний» элемент фрагмента.

Для продвижения по массиву слева направо в цикле 10 используется переменная i, справа налево - переменная j (в цикле 11). Их начальные значения устанавлива­ются в операторе 7. После того, как оба счетчика «сойдутся» где-то в средней части массива, происходит выход из цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые грани­цы левой части для сортировки на следующем шаге.

Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла 6, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3, 4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.

Ссылки. Ссылка представляет собой синоним имени, указанного при инициализации ссылки. Ссылку можно рассматривать как указатель, который всегда разымено­вывается. Формат объявления ссылки:

тип & имя;

где тип - это тип величины, на которую указывает ссылка, & - оператор ссылки, означающий, что следующее за ним имя является именем переменной ссылочного типа, например:

int kol;

int& pal = kol; //ссылка pal-альтернативное имя для kol

const char& CR = " \n"; // ссылка на константу

Запомните следующие правила.

- переменная-ссылка должна явно инициализироваться при ее описании, кро­ме случаев, когда она является параметром функции, описана как extern или ссылается на поле данных класса.

- после инициализации ссылке не может быть присвоена другая переменная.

- тип ссылки должен совпадать с типом величины, на которую она ссылается.

- не разрешается определять указатели на ссылки, создавать массивы ссылок и ссылки на ссылки.

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

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

Пример 5.3. Составить программу нахождения тех элементов массива С (из n элементов), индексы которых являются степенями двойки (1, 2, 4, 8…). UML-диаграмма этого алгоритма приведена на рисунке 5.1.

Рисунок 5.1 - UML-диаграмма деятельности для примера 5.3