37. Пузырьковая сортировка по функциям
Хорошая программа разбита на функции: одна функция — одна работа. Пузырьковую сортировку из прошлого урока удобно разложить на три функции: одна сортирует, вторая меняет двух соседей, третья печатает. Так программа читается, а каждую часть можно проверять отдельно. Приём тот же, что в уроке про рефакторинг.
Что пригодится из прошлого: свои функции, прототипы и void, пузырьковая сортировка. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Файл bubbleSort.c целиком
Это программа, которую разбирали на занятии, без изменений. В ней сортировка из прошлого урока (версия с границей compareUntil), только вынесенная в функции:
#include <stdio.h>
void bubblesort(int arr[], int size);
void swapArrayElements(int arr[], int i);
void printArray(int arr[], int size);
int main() {
int size = 5;
int arr[] = {5, 3, 8, 4, 6};
bubblesort(arr, size);
printArray(arr, size);
}
void bubblesort(int arr[], int size) {
int swapped = 0;
int compareUntil = size;
do {
swapped = 0;
for (int i = 0; i < compareUntil - 1; i++) {
if (arr[i] > arr[i + 1]) {
swapArrayElements(arr, i);
swapped = 1;
}
}
compareUntil--;
} while (swapped);
}
void swapArrayElements(int arr[], int i) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
}
Вывод:
3 4 5 6 8
После последнего числа стоит пробел, перевода строки нет: так печатает функция printArray. Ниже разберём файл по частям.
Прототипы
Первые три строки после #include — это прототипы: объявления функций без тела.
void bubblesort(int arr[], int size);
void swapArrayElements(int arr[], int i);
void printArray(int arr[], int size);
Они сообщают компилятору, что функции с такими именами и параметрами существуют. Благодаря этому main может вызывать их, хотя определения записаны ниже. Если убрать прототипы и оставить определения под main, компилятор при вызове ещё не знает этих функций и в современных версиях C сообщит об ошибке. Подробно про прототипы и void — в уроке про объявление функций.
Кто что делает
| Функция | Что получает | Что делает |
|---|---|---|
main |
— | задаёт массив и размер, вызывает сортировку и печать |
bubblesort(arr, size) |
массив и число элементов | сортирует массив по возрастанию |
swapArrayElements(arr, i) |
массив и индекс | меняет местами arr[i] и arr[i + 1] |
printArray(arr, size) |
массив и число элементов | печатает элементы через пробел |
Теперь тело bubblesort короче. Условие if (arr[i] > arr[i + 1]) читается как вопрос «соседи стоят неправильно?», а всю механику обмена прячет swapArrayElements. Исходные три строки с temp переехали туда:
void swapArrayElements(int arr[], int i) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
Как массив попадает в функцию
Здесь есть неочевидный момент. Обычные параметры, например int size, функция получает копией: если изменить копию внутри, исходное значение в main не поменяется. Но функция bubblesort ничего не возвращает (void), а в main массив после вызова уже отсортирован. Почему?
Потому что массив в функцию не копируется. Функция получает адрес начала массива и работает с теми же самыми элементами. Поэтому swapArrayElements(arr, i), вызванная глубоко внутри, меняет настоящий массив из main.
main: arr ──────► [ 5 | 3 | 8 | 4 | 6 ] size = 5
▲
bubblesort: arr ──────┘ (тот же массив) size = 5 (своя копия)
Оговорка: в main arr — настоящий массив из пяти чисел. В bubblesort arr — только адрес его начала, поэтому там уже нельзя узнать длину (см. ниже).
Что такое «адрес» и как им пользоваться, разберём в главе про указатели. Пока достаточно правила: изменения элементов массива внутри функции видны снаружи.
Почему размер передаётся отдельно
Можно спросить: зачем параметр size? Функция могла бы вычислить размер сама через sizeof. Проверим:
#include <stdio.h>
void show_size(int arr[])
{
printf("inside the function: %zu bytes\n", sizeof(arr));
}
int main(void)
{
int arr[] = {5, 3, 8, 4, 6};
printf("in main: %zu bytes\n", sizeof(arr));
show_size(arr);
return 0;
}
Вывод на 64-разрядной системе:
in main: 20 bytes
inside the function: 8 bytes
В main sizeof(arr) даёт 20: пять int по четыре байта. Внутри функции получается 8, и это размер адреса, а не массива. Функция получила только адрес начала массива и ничего не знает о его длине. Компилятор обычно предупреждает об этом: sizeof on array function parameter will return size of 'int *'. Здесь int * — тип «адрес целого числа»; подробно о нём в главе про указатели. Поэтому длину нужно передавать отдельным параметром: так делают bubblesort и printArray.
Разбор вызова на примере
Проследим bubblesort для {5, 3, 8, 4, 6}, где size = 5:
| Проход | compareUntil |
Сравнений | Массив после прохода |
|---|---|---|---|
| 1 | 5 |
4 |
3 5 4 6 8 |
| 2 | 4 |
3 |
3 4 5 6 8 |
| 3 | 3 |
2 |
3 4 5 6 8 |
В третьем проходе замен нет, поэтому swapped остаётся 0, и цикл do…while завершается. Всего 4 + 3 + 2 = 9 сравнений. В простой версии из прошлого урока было бы 4 + 4 + 4 = 12.
Чем файл отличается от стиля курса
Файл рабочий. Но в нём три особенности, которые в нашем курсе принято писать иначе.
int main()с пустыми скобками. В нашем курсе пишемint main(void): так компилятор точно знает, что параметров нет. Со строгими предупреждениями (-Wstrict-prototypes) пустые скобки дают замечание.- У
mainнетreturn 0;. Стандарт C99 и новее разрешает это дляmainи считает результатом0. Мы всё же пишемreturn 0;явно. - Печать без перевода строки. Чтобы приглашение терминала не склеилось с ответом, после вызова
printArrayможно добавитьprintf("\n");вmain.
Практика
Напишите функцию int isSorted(int arr[], int size). Она возвращает 1, если массив отсортирован по возрастанию, и 0, если нет. Проверьте на {3, 4, 5, 6, 8}, {3, 5, 4, 6, 8} и на массиве из одного элемента.
Функция isSorted
#include <stdio.h>
int isSorted(int arr[], int size)
{
for (int i = 0; i < size - 1; i++) {
if (arr[i] > arr[i + 1]) {
return 0;
}
}
return 1;
}
int main(void)
{
int a[] = {3, 4, 5, 6, 8};
int b[] = {3, 5, 4, 6, 8};
int c[] = {7};
printf("%d\n", isSorted(a, 5));
printf("%d\n", isSorted(b, 5));
printf("%d\n", isSorted(c, 1));
return 0;
}
Вывод: 1, 0, 1.
Достаточно найти одну пару соседей в неправильном порядке: тогда ответ 0, и функция сразу выходит через return. Если пары не нашлось, возвращается 1. У массива из одного элемента пар нет: цикл не выполняется, ответ 1. Такой массив считается отсортированным.
Что запомнить
- Разбиваем программу по задачам: сортировка, обмен, печать.
- Массив не копируется при передаче в функцию, поэтому функция может его менять.
- Длину массива передаём отдельным параметром: внутри функции
sizeof(arr)даёт размер адреса. - Прототипы позволяют вызывать функции, определённые ниже по тексту.
