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

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.