bulgakov

37. Пузырьковая сортировка по функциям

Хорошая программа разбита на функции: одна функция — одна работа. Пузырьковую сортировку из прошлого урока удобно разложить на три функции: одна сортирует, вторая меняет двух соседей, третья печатает. Так программа читается, а каждую часть можно проверять отдельно. Приём тот же, что в уроке про рефакторинг.

Что пригодится из прошлого: свои функции, прототипы и void, пузырьковая сортировка. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Файл bubbleSort.c целиком

Это программа, которую разбирали на занятии, без изменений. В ней сортировка из прошлого урока (версия с границей compareUntil), только вынесенная в функции:

C
#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 — это прототипы: объявления функций без тела.

C
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 переехали туда:

C
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. Проверим:

C
#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
C
#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) даёт размер адреса.
  • Прототипы позволяют вызывать функции, определённые ниже по тексту.
ПрактикаЗагружаем тест…