Сортировка методом пузырька

Begin

Begin

Begin

Begin

Begin

Var

Сортировка вставками

Type

Type

TMouseButton = (mbLeft, mbRight, mbMiddle);

По именам возможных значений параметра понятно, какая из кнопок мыши нажата.

Shift: параметр, имеющий тип–множество, объявленный в модуле Classes:

TShiftState = set of (ssShift, ssAlt, ssCtrl, ssLeft, ssRight, ssMiddle, ssDouble);

Тип TShiftState используется обработчиками событий мыши и клавиатуры для выяснения состояния клавиш Alt, Ctrl, Shift клавиатуры и кнопок мыши в момент происхождения события.

Составляющие множество «флаги» имеют следующий смысл:

ssShift – клавиша Shift нажата.

ssAlt – клавиша Alt нажата.

ssCtrl – клавиша Ctrl нажата.

ssLeft – левая кнопка мыши нажата.

ssRight – правая кнопка мыши нажата.

ssMiddle – средняя кнопка мыши нажата.

ssDouble – мышь получила двойной щелчок.

x, y: координаты указателя мыши (в пикселях) относительно верхнего левого угла элемента, с которым произошло событие (в данном случае, ImageGraph).

Событие «перемещается указатель мыши» (MouseMove).

procedure TForm1.ImageGraphMouseMove(Sender: TObject;

Shift: TShiftState; x, y: Integer);

Параметры в дополнительных пояснениях не нуждаются.

Событие «отпущена кнопка мыши» (MouseUp).

procedure TForm1.ImageGraphMouseUp(Sender: TObject;

Button: TMouseButton; Shift: TShiftState; x, y: Integer);

Параметры в дополнительных пояснениях не нуждаются.

Ссылки на модули Controls и Classes должны присутствовать в предложении uses.

Проект “Graph”, в котором использован алгоритм Дейкстры, представлен файлом Graph.doc, который надо переименовать в Graph.RAR и распаковать.

Алгоритм, в нескольких словах, таков.

На «первом» шаге вообще ничего не делается.

На втором шаге берётся второй элемент (A ₂) и сравнивается с первым (A ₁). Если второй элемент меньше первого, они обмениваются местами. Результат – два элемента упорядочены.

На i -ом шаге (теперь i = 3, 4, 5, …, n) берётся i -ый элемент (A_i) и сравнивается с теми элементами A_j, что расположены слева от него: j = i - 1, j = i - 2, j = i - 3, и т.д. – так до тех пор, пока выполняется неравенство A_i < A_j. В последний раз, когда это неравенство будет выполнено, переменная j примет значение, равное новому месту для A_i – такому, куда нужно A_i вставить.

Например, пусть i = 5, а первые 5 элементов массива таковы: 4, 3, 9, 11, 5. В последний раз A_i < A_j при j = 3. Следовательно, число 5 должно встать на третью позицию, подвинув числа 9, 11 вправо на 1 шаг. Результат – i элементов упорядочены.

Текст процедуры:

procedure InsertSort;

i, j: int64;

x: single;

nMove:=0;

nCompare:=0;

for i:= 2 to nCurr do

x:= A[i];

Inc(nMove);

j:= i;

while (j > 1) and (x < A[j - 1]) do

// Попаданий в тело цикла будет на 1 меньше,

// чем вычислений логического условия « (j > 1) and (x < A[j - 1])».

Inc(nCompare);

A[j]:= A[j - 1];

Inc(nMove, 2);

Dec(j);

end;

if j > 1 then

// Сюда попали => при последнем j проверка «(x < A[j - 1])» была

Inc(nMove);

// Прверка условия «(x < A[j - 1])» требует одного перемещения

Inc(nCompare);

end;

if j <> i then

A[j]:= x;

Inc(nMove);

end;

end;

end;

Назначение переменных:

nCurr – текущее количество элементов в массиве,

nMove – найденное количество перемещений.

nCompare – найденное количество сравнений.

Количество сравнений (nCompare):

i	Min	Max	Average
			3/2
…	…	…	…
i		i -1	i /2
…	…	…	…
n		n -1
∑	n -1	n ^2/2- n /2	n ^2/4+ n /4-1/2

Количество переносов (nMove):

i	Min	Max	Average
…	…	…	…
i		2 i	i +1
…	…	…	…
n		2 n	n +1
∑	2(n -1)	n ^2+ n -2	n ^2/2-3 n /2-2

На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.

На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.

Текст процедуры:

procedure BubbleSort;

Дата добавления: 2014-01-06