Алгоритм сортировки

1. Ввести n чисел.

2. Для номера_просмотра от 1 до n-1 выполнить

2.1. Для номера_числа (i) от 1 до n-1 выполнить

Если число[i] > число[i+1], то поменять их местами.

3. Вывести отсортированную последовательность.

4. Закончить.

Программа для этого алгоритма будет иметь вид

Program Sort;

Const

Nmax = 100;

Var

X : Array [1..Nmax] Of Real;

A : Real;

n, k, i : Integer;

Begin

Writeln('Введите количество чисел');

Readln(n);

Writeln('Введите массив чисел');

For i := 1 To n Do

Read (X[i]);

{ Сортировка }

For k := 1 To n-1 Do

For i := 1 To n-1 Do

If X[i] > X[i+1] Then

Begin

A:=X[i];

X[i]:=X[i+1];

X[i+1]:=A

End;

Writeln('Отсортированный массив чисел:');

For i:=1 To n Do

Write (X[i]);

End.

Глубину просмотра можно уменьшать, основываясь на том, что большие числа "опускаются" вниз (в конец последовательности) и затем не переставляются:

For k := 1 To n-1 Do

For i := 1 To n-k Do

If X[i] > X[i+1] Then

. . . . . . . .

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

Приведем алгоритм для этого метода.

В этом алгоритме используется переменная "Перестановка_есть", которой сначала присваивается значение "истина", а как только в одном из просмотров не будет перестановок – ей присвоится значение "ложь". Это позволит прервать выполнение цикла "Пока".

1. Ввести массив.

2. Перестановка_есть = истина.

3. Номер_просмотра = 1.

4. Пока перестановка_есть = истина выполнить

сортировку массива.

5. Вывести результат.

6. Закончить.

Уточним отдельные пункты этого алгоритма.

1. Ввести массив.

2. Перестановка_есть = истина

3. Номер_просмотра (к)=1

4. Пока перестановка_есть = истина выполнить

4.1. Количество_перестановок = 0

4.2. Для i от 1 до n-k выполнить

Если x[i] > x[i+1], то

4.2.1. поменять x[i] и x[i+1]

4.2.2. количество_перестановок = количество_перестановок + 1

4.3. Если количество_перестановок = 0, то

перестановка_есть =ложь.

4.4. к=к+1

5. Для i от 1 до n выполнить

Вывести x[i].

6. Закончить.

Программа для этого алгоритма будет иметь вид

Program SortUsk;

Const

Nmax = 100;

Var

X : Array [1..Nmax] Of Real;

A : Real;

P : Boolean;

L, K, I, N : Integer;

Begin

Writeln('Введите количество чисел');

Readln(n);

Writeln('Введите массив чисел');

For i := 1 To n Do

Read(X[i]);

P := True; {Перестановка есть}

K := 1; {Номер просмотра}

While P Do

Begin

L:=0; {Кол. перестановок}

For i := 1 To n-k Do

If X[i] > X[i+1] Then

Begin

A := X[i];

X[i]:=X[i+1];

X[i+1]:=A;

L:=L+1

End;

If L=0 Then

P:=False;

k:=k+1;

End;

Writeln('Отсортированный массив чисел');

For i := 1 To n Do

Write(X[i]);

End.