Сортировка массива

Сортировка массива — это упорядочивание элементов по возрастанию или убыванию значений. Сортировка применяется при выводе значений, а также при подготовке массива к частому поиску значений. Поиск по отсортированному массиву производится гораздо быстрее, так как не нужно каждый раз просматривать все значения массива.

Для упорядочивания элементов массива в учебных целях очень часто применяется метод, называемый пузырьковой сортировкой (листинг 6.2). При этом методе наименьшее значение как бы «всплывает» в начало массива, а наибольшее значение «погружается» в конец массива. Сортировка выполняется в несколько проходов. При каждом проходе последовательно сравниваются значения двух элементов, которые расположены рядом. Если значение первого элемента больше второго, то значения элементов меняются местами. Для сортировки массива из пяти элементов необходимо максимум четыре прохода и десять сравнений. Если после прохода не было ни одной перестановки, то сортировку можно прервать. В этом случае для сортировки ранее уже отсортированного массива нужен всего один проход.

Листинг 6.2. Пузырьковая сортировка по возрастанию

#include <iostream>

int main() {
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {10, 5, 6, 1, 3};
   int j = 0, tmp = 0, k = ARR_SIZE - 2;
   bool is_swap = false;
   for (int i = 0; i <= k; ++i) {
      is_swap = false;
      for (j = k; j >= i; --j) {
         if (arr[j] > arr[j + 1]) {
            tmp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = tmp;
            is_swap = true;
         }
      }
      // Если перестановок не было, то выходим
      if (!is_swap) break;
   }
   // Выводим отсортированный массив
   for (int i = 0; i < ARR_SIZE; ++i) {
      std::cout << arr[i] << std::endl;
   }
   return 0;
}

В качестве еще одного примера произведем сортировку по убыванию (листинг 6.3). Чтобы пример был более полезным изменим направление проходов.

Листинг 6.3. Пузырьковая сортировка по убыванию

#include <iostream>

int main() {
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {5, 6, 1, 10, 3};
   int j = 0, tmp = 0;
   bool is_swap = false;
   for (int i = ARR_SIZE - 1; i >= 1; --i) {
      is_swap = false;
      for (j = 0; j < i; ++j) {
         if (arr[j] < arr[j + 1]) {
            tmp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = tmp;
            is_swap = true;
         }
      }
      if (!is_swap) break;
   }
   // Выводим отсортированный массив
   for (int i = 0; i < ARR_SIZE; ++i) {
      std::cout << arr[i] << std::endl;
   }
   return 0;
}

Для сортировки массива лучше воспользоваться стандартной функцией qsort(). Прототип функции:

#include <cstdlib> /* или #include <stdlib.h> */
void qsort(void *base, size_t numOfElements, size_t sizeOfElements, 
           int (*PtFuncCompare)(const void *, const void *));

В параметре base указывается адрес первого элемента массива, в параметре numOfElements — количество элементов массива, а в параметре sizeOfElements — размер каждого элемента в байтах. Адрес пользовательской функции (указывается название функции без круглых скобок и параметров), внутри которой производится сравнение двух элементов, передается в последнем параметре. Прототип пользовательской функции сравнения должен выглядеть так:

int <Название функции>(const void *arg1, const void *arg2);

При сортировке по возрастанию функция должна возвращать отрицательное значение, если arg1 меньше arg2, положительное значение, если arg1 больше arg2, или 0, если значения равны. Внутри функции необходимо выполнить приведение указателя void * к определенному типу. Пример использования функции qsort() приведен в листинге 6.4.

Листинг 6.4. Сортировка массива с помощью функции qsort()

#include <iostream>
#include <cstdlib>

int compare(const void *arg1, const void *arg2) {
   if (*(int *)arg1 < *(int *)arg2) return -1;
   if (*(int *)arg1 > *(int *)arg2) return 1;
   return 0;
}

int main() {
   const int ARR_SIZE = 5;
   int arr[ARR_SIZE] = {10, 5, 6, 1, 3};
   std::qsort(arr, ARR_SIZE, sizeof(int), compare);
   for (int i = 0; i < ARR_SIZE; ++i) {
      std::cout << arr[i] << std::endl;
   }
   return 0;
}

Пример функции сравнения для сортировки по убыванию:

int compare(const void *arg1, const void *arg2) {
   if (*(int *)arg1 > *(int *)arg2) return -1;
   if (*(int *)arg1 < *(int *)arg2) return 1;
   return 0;
}

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

int compare(const void *arg1, const void *arg2) {
   return *(int *)arg1 - *(int *)arg2;
}

Чтобы произвести сортировку по убыванию, достаточно поменять значения местами:

int compare(const void *arg1, const void *arg2) {
   return *(int *)arg2 - *(int *)arg1;
}
На заметку

Учебник C++ (MinGW-W64)
Учебник C++ (MinGW-W64) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов