Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

ОРТИРОВКА ОБМЕНОМ
 
Сортировка методом обмена основана на том, что многократно повто-
ренный процесс упорядочения пар соседних элементов приводит к упорядо-
чению всего массива. 
Это обстоятельство отнюдь не является очевидным, но при некотором 
размышлении можно понять причину такого результата. Она заключается в 
том, что при проходе от начала к концу массива с упорядочением пар элемен-
тов на последнее место «выталкивается» максимальное значение. Последую-
щие проходы не меняют его расположения, но постепенно формируют упоря-
доченную по возрастанию последовательность значений в конце массива. 
2.2.3.1 Сортировка простым обменом 
Сортировка простым обменом известна также как метод пузырька и в 
полной мере воплощает принцип обменной сортировки, описанный выше.
Свое образное название этот метод получил в силу одной своей особенности: 
1 / 23

---

25 
при сортировке по возрастанию отсортированная часть массива формируется 
путем выталкивания («всплывания») при каждом просмотре наибольшего из 
значений в неотсортированной части массива. Соответственно, при сорти-
ровке по убыванию «всплывают» минимальные значения. Алгоритм сорти-
ровки простым обменом приведен в листинге 2.7. 
Листинг 2.7. Сортировка методом пузырька 
public void SortBubl(int[] a) 
{ 
int N = a.Length; 
for (int i = 1; i < N; i++) 
for(int j =L-1; j >= i; j--) 
if (a[j-1] > a[j])
{ 
int t = a[j-1]; 
a[j-1] = a[j]; 
a[j] = t; 
} 
} 
Число сравнений в этом алгоритме равно
2
.
2
N
N
C
−
=
 
 
 
(2.7) 
Минимально число перестановок равно нулю для массива, упорядо-
ченного по возрастанию, и совпадает с числом сравнений для массива, упо-
рядоченного по убыванию. Поэтому 
2
.
4
ср
N
N
M
−
=
 
 
 
(2.8) 
Отсюда следует, что данный алгоритм обладает квадратичной скоро-
стью роста O(N
2
). 
2 / 23

---

26