Курсовая работа: Написание программы « Методы сортировки массивов» на языке С++ (сортировка вставками, сортировка подсчетом)

Написание программы, использующей методы сортировки массивов, является одним из фундаментальных навыков в программировании на языке C++. В данной статье рассмотрим два таких метода: сортировку вставками и сортировку подсчетом.

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

Для начала создадим функцию, которая будет реализовывать сортировку вставками. Пусть у нас есть массив чисел - numbers, его размер - n. Код функции может выглядеть следующим образом:

```cpp
void insertionSort(int numbers[], int n) {
for (int i = 1; i < n; i++) {
int key = numbers[i];
int j = i - 1;

while (j >= 0 && numbers[j] > key) {
numbers[j + 1] = numbers[j];
j = j - 1;
}

numbers[j + 1] = key;
}
}
```

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

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

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

```cpp
int[] countingSort(int numbers[], int n) {
int max = numbers[0];
int min = numbers[0];

for (int i = 1; i < n; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
if (numbers[i] < min) {
min = numbers[i];
}
}

int range = max - min + 1;
int count[range] = {0};

for (int i = 0; i < n; i++) {
count[numbers[i] - min]++;
}

for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}

int sortedNumbers[n];

for (int i = n - 1; i >= 0; i--) {
sortedNumbers[count[numbers[i] - min] - 1] = numbers[i];
count[numbers[i] - min]--;
}

for (int i = 0; i < n; i++) {
numbers[i] = sortedNumbers[i];
}

return numbers;
}
```

В данной программе мы сначала находим минимальное и максимальное значения в массиве. Затем создаем вспомогательный массив count, в котором будем хранить количество вхождений каждого элемента. Затем простой цикл позволяет нам посчитать сумму элементов массива, что будет использоваться для определения конечной позиции каждого элемента в отсортированном массиве. Затем мы создаем новый массив sortedNumbers, который будет содержать отсортированные элементы. Последний цикл переносит значения из sortedNumbers обратно в исходный массив.

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