Сортировка пузырьком может осуществляться во многих языках программирования, в том числе и в С. Это достаточно простой способ сортировки, который очень легко реализуется. Его изучают в числе первых в теме «теория алгоритмов», но применяется он крайне редко.
Сегодня мы простыми словами разберем, что такое сортировка пузырьком в Си.
Сортировка пузырьком
Под такой сортировкой понимают многократное прохождение алгоритма по массиву, который нужно отсортировать. При каждом таком «погружении»-прохождении по массиву его элементы будут попарно сравниваться. Если сравниваемые элементы неверно расположены, то они «меняются местами». Подобные «погружения» в массив будут осуществляться такое количество раз, какое потребуется для того, чтобы все элементы массива были правильно отсортированы.
При такой сортировке элементы с «наибольшим» значением «погружаются» в глубь массива, а элементы с «наименьшим» значением «всплывают» в начало массива.
Сортировка пузырьком на простом примере
Представим, что у нас есть некий числовой массив со значениями «6, 2, 5, 3, 9». Нам нужно отсортировать элементы данного массива по возрастанию, для этого будет применяться сортировка пузырьком.
Написав алгоритм сортировки, мы получим отсортированный массив через несколько проходов алгоритма.
Первое «погружение» в массив
(6, 2, 5, 3, 9) — (2, 6, 5, 3, 9) — наш алгоритм сравнил первые элементы и переместил «2», так как 2<6;
(2, 6, 5, 3, 9) — (2, 5, 6, 3, 9) — наш алгоритм сравнил следующие элементы и переместил «5» чуть выше, так как 5<6;
(2, 5, 6, 3, 9) — (2, 5, 3, 6, 9) — наш алгоритм сравнил следующие элементы и переместил «3» выше, так как 3<6;
(2, 5, 3, 6, 9) — (2, 5, 3, 6, 9) — наш алгоритм сравнивает последнюю пару элементов и оставляет их на своих местах, так как требования соблюдаются.
Так как за одно прохождение по массиву сам массив не был отсортирован до конца, у нас будет еще одно прохождение.
Второе «погружение» в массив
(2, 5, 3, 6, 9) — (2, 5, 3, 6, 9) — алгоритм сравнивает первую пару элементов и ничего не меняет, так как все соответствует требованиям;
(2, 5, 3, 6, 9) — (1, 3, 5, 6, 9) — алгоритм сравнивает следующую пару элементов и поднимает «3» выше, так как 3<5;
(1, 3, 5, 6, 9) — (1, 3, 5, 6, 9) — алгоритм сравнивает следующую пару элементов и оставляет все как есть;
(1, 3, 5, 6, 9) — (1, 3, 5, 6, 9) — алгоритм сравнивает следующую пару элементов и тоже оставляет все как есть.
Готово! Наш массив отсортирован, но это на примере видим мы, а не сам алгоритм. Поэтому будет еще одно прохождение по массиву с попарным сравнением элементов, чтобы алгоритм сам удостоверился, что все элементы расположены согласно требованиям. Только после финального прохождения, когда алгоритм убедится, что все в порядке, сам алгоритм завершит свою работу.
Как реализуется сортировка пузырьком в С (Си)
Сортировка пузырьком в С реализуется по следующему шаблону:
#define SWAP(X, Z) { int d = X; X = Z; Z = d; }
void bubblesort(int *a, int n)
{
int i, q;
for (i = n - 1; i > 0; i--)
{
for (q = 0; q < i; q++)
{
if (a[q] > a[q + 1])
SWAP( a[q], a[q + 1] );
}
}
}
Заключение
Сортировка пузырьком — это базовый алгоритм сортировки. Из-за своей низкой скорости и производительности этот алгоритм достаточно редко применяется, так как есть более «шустрые» алгоритмы сортировки, о которых мы обязательно поговорим в следующих статьях.
Другое
