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

Сортировка — один из наиболее распространённых процессов современной обработки данных.

Сортировка — это распределение элементов массива в соответствии с определёнными правилами.

Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.

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

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

Цель сортировки — ускорить последующий поиск элементов, т. к. нужный элемент легче искать в упорядоченном массиве.

Рассмотрим и проанализируем несколько алгоритмов сортировки для решения следующей задачи. Дан одномерный массив целых чисел. Требуется отсортировать его так, чтобы все элементы были расположены в порядке неубывания: a[i] <= a[i + 1].

Обменная сортировка методом «пузырька»

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

Пусть n — количество элементов в неупорядоченном массиве.

1. Поместим на место n-го элемента (а[n]) наибольший элемент массива. Для этого:

1) положим i = 1;

2) пока не обработана последняя пара элементов, т. е. (n - 1)-й и n-й элементы:

сравниваем i-й и (i + 1)-й элементы массива;
если a[i] > a[i +1] (элементы расположены не по порядку), то меняем элементы местами;
переходим к следующей паре элементов, сдвинувшись на один элемент вправо.

2. Повторяем пункт 1, каждый раз уменьшая размерность неупорядоченного массива на 1, до тех пор, пока не будет обработан массив из одной пары элементов (таким образом, на k-м просмотре будут сравниваться первые (n - k) элементов со своими соседями справа).

Окончание >>>