Сортируем c С++ массив целых чисел

newbie_

Опубликован:  2019-06-24T06:49:54.016336Z

Сортировка - очень распространённая типовая задача, которую часто приходится решать в повседневной жизни даже обычным людям никак не связанным с программированием и разработкой программного обеспечения. Этот обзор посвящён сортировке массива целых чисел по возрастанию, я покажу один из классических алгоритмов сортировки - сортировку вставками.

Условия задачи следующие:

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

Опять следует сказать пару слов о самой задаче... Дело в том, что работодатели в сфере IT и разработки программного обеспечения в нашем богом хранимом отечестве очень часто не имеют или не могут отчётливо и понятно сформулировать критерии отбора персонала, и видимо поэтому, на первичных собеседованиях предлагают своим соискателям решить одну из подобные задач. Плохо то, что решить эту задачу вас скорей всего попросят на листе бумаги. Отсюда следует простой вывод, надо быть готовым к такому повороту событий.

Сортировка массива целых чисел по определённому условию - это типовая задача, задача продуманная и имеющая на текущий момент развития компьютерных технологий описанные типовые решения. Мне известны три основных алгоритма сортировки: сортировка вставками, сортировка выбором и пузырьковая сортировка. Если вы готовитесь к собеседованию на вакансию программиста, стоит качественно разобрать и понять все три алгоритма. В рамках этого обзора я рассмотрю только один - сортировку вставками.

Решать эту задачу я буду как всегда на базе десктопа с Debian buster и интегрированной среды разработки Geany. Запускаю редактор, вхожу в каталог workspace и создаю новый файл - sorter.cpp.

8CK3qVeFgc.png

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

#include <iostream>
#include <cstdlib>
#include <ctime>

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

  1. Заполнение исходного массива случайными целыми числами;
  2. Вывод всех элементов массива в заданной форме на терминал;
  3. Сортировка исходного массива по возрастанию.

Для каждой из этих задач декларирую соответствующую функцию.

void fill(int * ar, const int l);
void show(const int * ar, const int l);
void sort(int * ar, const int l);

Итого три функции. На начальном этапе разработки я ограничусь использованием только первых двух и создам исходный массив следующих в случайном порядке целых чисел, а затем выведу его элементы на экран терминала.

int main()
{
  const int L = 16;
  int * ar = new int[L];
  fill(ar, L);
  std::cout << "Initial array:" << std::endl;
  show(ar, L);
  delete [] ar;
  return 0;
}

Теперь я сосредоточу своё внимание на разработке двух вспомогательных функций: fill и show.

void fill(int * ar, const int l)
{
  std::srand(std::time(0));
  for (int i = 0; i < l; i++)
    ar[i] = std::rand() % 127 + 1;
}

Функция fill принимает в качестве аргументов указатель на массив целых чисел и количество элементов в массиве. Функция при помощи соответствующих инструментов модулей cstdlib и ctime инициализирует стандартный генератор псевдослучайных чисел, а затем заполняет заданный аргументом массив, ничего сложного, только стандартные процедуры.

void show(const int * ar, const int l)
{
  for (int i = 0; i < l; i++)
  {
    if (i < l - 1)
      std::cout << ar[i] << ", ";
    else
      std::cout << ar[i];
  }
  std::cout << std::endl;
}

Функция show принимает в качестве аргументов указатель на заданный массив целых чисел и количество элементов в массиве и выводит в заданной форме все элементы массива на экран терминала. В стандартной библиотеке С++ конечно же имеются более изящные средства для вывода элементов массива на печать, но, поскольку цель этого обзора не предполагает умение пользоваться этими средствами, я же новичок, предложенная функция будет считаться вполне приемлемым решением.

Пишу этот код в файл sorter.cpp.

jPp5DOzw4a.png

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

g++ -o exe sorter.cpp
./exe

Запускаю программу несколько раз.

S0362bJV4l.png

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

Классический алгоритм сортировки вставками, на котором я и буду основывать своё решение, сортирует элементы массива на месте, при этом не создавая другого временного массива. В коде этот алгоритм выглядит следующим образом.

void sort(int * ar, const int l)
{
  for (int i = 1; i < l; i++)
  {
    int box = ar[i];
    int j = i - 1;
    while (j >= 0 and box < ar[j])
    {
      ar[j+1] = ar[j];
      j -= 1;
    }
    ar[j+1] = box;
  }
}

Классический алгоритм сортировки вставками содержит два цикла. Первый цикл - for - делит заданный массив на две последовательности: исходную последовательность и отсортированную последовательность. Первым элементом исходной последовательности на первой итерации цикла for является второй элемент заданного массива ar[1], все остальные элементы исходной последовательности находятся справа от первого элемента исходной последовательности. Цикл for перебирает все элементы исходной последовательности слева-на-право.

Отсортированная последовательность на первой итерации цикла for находится слева от первого элемента исходной последовательности. При сортировке второй цикл алгоритма - цикл while - перебирает все элементы отсортированной последовательности справа-на-лево и сравнивает их с первым элементом исходной последовательности, значение которого сохранено в переменной box для временного хранения. Таким образом по мере продвижения цикла for исходная последовательность сокращается, а отсортированная последовательность растёт. На каждой итерации цикла for первый элемент исходной последовательности находит своё место в отсортированной последовательности посредством цикла while - происходит вставка элемента на своё место в зависимости от заданного в голове цикла while условия. Визуально работу алгоритма можно представить следующим образом.

Sdp6p8PUks.png

Проверим, насколько теория подтверждается практикой. Вписываю в файл sorter.cpp определение функции sort и слегка изменяю главную функцию программы.

int main()
{
  ...
  ...
  sort(ar, L);
  std::cout << "Sorted array:" << std::endl;
  show(ar, L);
  ...
  ...
}

0s36k64wQp.png

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

QYgbJ5cO0r.png

На снимке экрана видно, что каждый раз отсортированный массив содержит все элементы начального массива, и числа в отсортированном массиве следуют в порядке возрастания слева-на-право. Чтобы изменить порядок следования элементов в отсортированном массиве, достаточно изменить условие цикла while, всё очень просто. Подвожу итог, задача решена.

Следует иметь ввиду, что в повседневной практике программирования на C++ вам вряд ли придётся прибегать к этому алгоритму только потому, что стандартная библиотека диалекта содержит специально разработанные средства для сортировки данных по различным условиями и в различных последовательностях. Тем не менее, очень полезно понять и проникнуться классическими алгоритмами сортировки, по-крайней мере, когда на очередном собеседовании вас попросят написать сортировку массива на листе бумаги, что само по себе в сущности является маразмом, вы будете готовы. :-)

Метки:  sort, cplusplus, sorter
Комментарии:

newbie_

2019-06-24T06:53:28.795809Z

Код программы целиком:

#include <iostream>
#include <cstdlib>
#include <ctime>

void fill(int * ar, const int l);
void show(const int * ar, const int l);
void sort(int * ar, const int l);

int main()
{
  const int L = 16;
  int * ar = new int[L];
  fill(ar, L);
  std::cout << "Initial array:" << std::endl;
  show(ar, L);
  sort(ar, L);
  std::cout << "Sorted array:" << std::endl;
  show(ar, L);
  delete [] ar;
  return 0;
}

void sort(int * ar, const int l)
{
  for (int i = 1; i < l; i++)
  {
    int box = ar[i];
    int j = i - 1;
    while (j >= 0 and box < ar[j])
    {
      ar[j+1] = ar[j];
      j -= 1;
    }
    ar[j+1] = box;
  }
}

void fill(int * ar, const int l)
{
  std::srand(std::time(0));
  for (int i = 0; i < l; i++)
    ar[i] = std::rand() % 127 + 1;
}

void show(const int * ar, const int l)
{
  for (int i = 0; i < l; i++)
  {
    if (i < l - 1)
      std::cout << ar[i] << ", ";
    else
      std::cout << ar[i];
  }
  std::cout << std::endl;
}