Сортировка методом пузырька
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).
procedureTForm1.ImageGraphMouseMove(Sender: TObject;
Shift: TShiftState; x, y: Integer);
Параметры в дополнительных пояснениях не нуждаются.
Событие «отпущена кнопка мыши» (MouseUp).
procedureTForm1.ImageGraphMouseUp(Sender: TObject;
Button: TMouseButton; Shift: TShiftState; x, y: Integer);
Параметры в дополнительных пояснениях не нуждаются.
Ссылки на модули Controls и Classes должны присутствовать в предложении uses.
Проект “Graph”, в котором использован алгоритм Дейкстры, представлен файлом Graph.doc, который надо переименовать в Graph.RAR и распаковать.
Алгоритм, в нескольких словах, таков.
На «первом» шаге вообще ничего не делается.
На втором шаге берётся второй элемент (A2) и сравнивается с первым (A1). Если второй элемент меньше первого, они обмениваются местами. Результат – два элемента упорядочены.
На i-ом шаге (теперь i = 3, 4, 5, … , n) берётся i-ый элемент (Ai) и сравнивается с теми элементами Aj , что расположены слева от него: j = i -1, j = i -2, j = i -3, и т.д. – так до тех пор, пока выполняется неравенство Ai < Aj. В последний раз, когда это неравенство будет выполнено, переменная j примет значение, равное новому месту для Ai – такому, куда нужно Ai вставить.
Например, пусть i = 5, а первые 5 элементов массива таковы:4, 3, 9, 11, 5. В последний раз Ai < Aj при j = 3. Следовательно, число 5 должно встать на третью позицию, подвинув числа 9, 11 вправо на 1 шаг. Результат – i элементов упорядочены.
Текст процедуры:
procedureInsertSort;
i, j: int64;
x: single;
nMove:=0;
nCompare:=0;
fori := 2 tonCurr 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;
ifj > 1 then
// Сюда попали => при последнем j проверка «(x < A[j - 1])» была
Inc(nMove);
// Прверка условия «(x < A[j - 1])» требует одного перемещения
Inc(nCompare);
end;
ifj <> 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
| 
n2/2-n/2
| 
n2/4+n/4-1/2
|
Количество переносов (nMove):
| i | Min | Max | Average |
| … | … | … | … |
| i
| 2i | i+1 | |
| … | … | … | … |
| n | 2n | n+1 | |
| ∑ | 
2(n-1)
| 
n2+n-2
| 
n2/2-3n/2-2
|
На первом шаге проверяются все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева.
На втором шаге свое законное место (второе слева) занимает наименьший из оставшихся элементов массива. И т.д.
Текст процедуры:
procedureBubbleSort;