Рассмотрим метод сортировки данных, который называется сортировка пузырьком (также его называют метод обмена). Будут приведены алгоритм и его реализация на языке программирования Си.
Упорядоченный массив создается на том же участке памяти, где находится исходная последовательность. Идея метода состоит в том, чтобы попарно сравнивать соседние элементы. Каждый проход начинается с начала последовательности. Сравнивается первый элемент со вторым: если порядок между ними нарушен, то они меняются местами. Затем сравниваются второй с третьим, третий с четвертым и так далее до конца массива; элементы с неправильным порядком в паре меняются местами. В итоге, после первого прохода, максимальный (или минимальный, в зависимости от вида сортировки: по возрастанию/по убыванию) элемент будет находится на последнем месте в массиве, он как бы «всплывет» наверх. Именно поэтому этот метод называется сортировка пузырьком. На следующем проходе рассматривается последовательность от 1 до N-1, затем от 1 до N-2, и так до конца. После каждого прохода можно делать проверку: выполнялись ли перестановки элементов. Если не выполнялись, то сортировка завершена.
При сортировке пузырьком максимальное число сравнений составляет 0,5N², а среднее число сравнений приблизительно 0,25N².
Ниже приведена реализация алгоритма сортировки на языке программирования Си:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
int tmp; bool noSwap; for (int i = N - 1; i >= 0; i--) { noSwap = 1; for (int j = 0; j < i; j++) { if (mass[j] > mass[j + 1]) { tmp = mass[j]; mass[j] = mass[j + 1]; mass[j + 1] = tmp; noSwap = 0; } } if (noSwap == 1) break; } |
где N – число элементов в массиве, а mass[] – массив элементов.
Приведем пример консольной программы на языке программирования Си, которая считывает массив, сортирует его пузырьком и выводит результат на экран.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <stdio.h> #include <malloc.h> int main() { int N; printf("Input N: "); scanf_s("%d", &N); int* mass; mass = (int *)malloc(N * sizeof(int)); printf("Input the array elements:\n"); for (int i = 0; i < N; i++) scanf_s("%d", &mass[i]); //сортировка пузырьком int tmp; bool noSwap; for (int i = N - 1; i >= 0; i--) { noSwap = 1; for (int j = 0; j < i; j++) { if (mass[j] > mass[j + 1]) { tmp = mass[j]; mass[j] = mass[j + 1]; mass[j + 1] = tmp; noSwap = 0; } } if (noSwap == 1) break; } printf("Sorted array:\n"); for (int i = 0; i < N; i++) printf("%d ", mass[i]); printf("\n"); free(mass); return 0; } |
Разберем код программы. Подключим необходимые библиотеки (строки 1-2), предложим пользователю ввести число N — количество элементов в массиве (строка 7), считаем число N (строка 8), выделим память под массив (строка 10), предложим пользователю ввести элементы массива (строка 11), считаем элементы массива (строки 12-13), выполним сортировку пузырьком (строки 18-33), выведем отсортированный массив на экран (35-36), освободим память, выделенную под массив элементов (строка 38).
Работа программы представлена на скриншоте ниже:
Для того, чтобы скачать исходник программы, нажмите на кнопку:
Смотрите также:
Сортировка методом выбора на языке Си
Сортировка методом подсчета на Си
Поделиться в соц. сетях: