Сортировка выбором

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

Вопросы для самопроверки

Инициализация массива

Инициализацию массивов можно осуществить либо программно, либо с помощью типизированных констант.

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

Пример: заполнения массива данными

const

N=10;

M=5;

type

TMatrix = array[1..N, 1..M] of real;

var

X: TMatrix;

i, j: integer;

…

for i:=1 to N do

for j:=1 to M do writeln(X[i, j]);

При инициализации с помощью типизированных констант значения элементов заключаются в скобки и разделяются запятыми.

Пример: пример инициализации одномерного массива с помощью типизированных констант

type

TStatus = array[1..3] of string[7];

const

Status: TStatus = ('Active','Passive','Waiting');

В случае многомерных массивов значения каждой размерности заключаются в отдельные скобки и разделяются запятыми.

Пример: пример инициализации многомерного массива с помощью типизированных констант

type Cube = array[0..1,0..1,0..1] of integer;

const Maze: Cube = ( ( (0,1), (2,3) ), ( (4,5), (6,7) ) );

1. Что такое массив?

2. Как описываются массивы на языке Паскаль?

3. Что такое элемент массива? Индексный тип?

4. Какие операции допустимы над массивами?

5. Как можно на языке Паскаль описать многомерный массив?

6. Как можно просуммировать значения элементов массива?

Нередко в программировании возникает задача отсортировать какие-либо величины. Иногда предварительная сортировка данных позволяет существенно сократить содержательную часть алгоритма программы. В этой ситуации могут помощь существующие алгоритмы сортировки.

В данном параграфе будут рассмотрены так называемые простые сортировки. К ним относятся методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N² действий, где С – некоторая константа.

Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно же, зависит не только от длины этой последовательности, но и от ее структуры. Например, если на вход подается уже упорядоченная последовательность, то количество действий будет значительно меньше, чем в случае перемешанных входных данных.

Для начала рассмотрим алгоритм сортировки выбором.

Суть алгоритма заключается в следующем: находим наименьший элемент в массиве и меняем его местами с элементом, находящимся на первом месте. Далее процесс повторяется, но уже начиная со второй позиции в массиве и так далее, пока не отсортируем весь массив.

Алгоритм для сортировки массива из N элементов.

1. Начинаем сортировку с 1-го элемента: i:=1.

2. Находим номер j минимального элемента среди элементов от i до N.

3. Меняем местами элементы i и j.

4. Если i < N-1, то увеличиваем значение i на 1 и возвращаемся к шагу 2.

5. Конец алгоритма. Массив отсортирован.

Пример: алгоритм сортировки выбором массива str

for i := 1 to n-1 do

begin

min:=i;

for j := i+1 to n do

if str[ j ]<str[ min ] then min := j;

if i<>j then

begin

t := str[ min ];

str[ min ] := str[ i ];

str[ i ] := t;

end;

end;

В лучшем случае (если исходная последовательность уже упорядочена) алгоритм произведет (N-1)*(N+2)/2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов будет равным 3*(N-1).