Від алгоритму до функції
На попередній сторінці ми порівняли три способи сортування. Тепер оформимо їх як функції й навчимося впорядковувати лише потрібну частину масиву.
Для прикладів використовуємо знайомі RandArr та PrintArr. Спочатку заповнюємо й виводимо масив, потім викликаємо сортування та знову виводимо результат.
«За зростанням» далі означає за неспаданням: від меншого до більшого, однакові значення дозволені. «За спаданням» означає за незростанням: від більшого до меншого. Кількість елементів не змінюється.
| Назва тут | Спосіб | Назва на попередній сторінці |
|---|---|---|
| SortArr_1 | Вибором | SelectionSort |
| SortArr_2 | Бульбашкою | BubbleSort |
| SortArr_3 | Вставленням | InsertionSort |
Це ті самі алгоритми. Назви SortArr_1, SortArr_2 і SortArr_3 збережено для відповідності учнівським варіантам.
Приклад 1 · Увесь масив методом вибору
Знаходимо найменше число в невпорядкованій частині та ставимо його на чергову позицію. minIndex зберігає індекс, а не значення мінімуму.
void SortArr_1(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}Виклик: SortArr_1(mass, n);
Повна програма для прикладу 1
Введіть n, a, b: кількість n від 0 до 100, межі −100 ≤ a ≤ b ≤ 100. Наприклад: 6 −10 20 (мінус вводьте звичайною клавішею). Для прикладів 2 та 4 після виведення масиву введіть індекси x і y. Кожну повну програму запускайте окремо.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
if (n == 0) cout << "Масив порожній";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
void SortArr_1(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 0 || n > capacity || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
SortArr_1(mass, n);
PrintArr(mass, n);
}
return 0;
}Приклад 2 · Ділянка методом вибору
Параметри k та s є індексами початку й кінця. Обидві межі включаємо. Приклад для k = 1, s = 4:
Числа з індексами 0 і 5 не змінюємо. Сортуємо лише чотири числа на позиціях 1, 2, 3, 4.
void SortArr_1(int arr[], int n, int k, int s) {
if (k >= 0 && k <= s && s < n) {
for (int i = k; i < s; i++) {
int minIndex = i;
for (int j = i + 1; j <= s; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}Виклик: SortArr_1(mass, n, 1, 4);
- Перший цикл починається з i = k і триває, поки i < s.
- Пошук мінімуму завершується на j = s включно.
- Допустимі межі: 0 ≤ k ≤ s < n. За k = s змін немає. За неправильних меж функція залишає масив без змін.
Функції з двома та чотирма параметрами мають однакову назву. C++ розрізняє ці виклики за кількістю аргументів. У повних програмах нижче кожен приклад наведено окремо.
Повна програма для прикладу 2
Введіть n, a, b: кількість n від 0 до 100, межі −100 ≤ a ≤ b ≤ 100. Наприклад: 6 −10 20 (мінус вводьте звичайною клавішею). Для прикладів 2 та 4 після виведення масиву введіть індекси x і y. Кожну повну програму запускайте окремо.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
if (n == 0) cout << "Масив порожній";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
void SortArr_1(int arr[], int n, int k, int s) {
if (k >= 0 && k <= s && s < n) {
for (int i = k; i < s; i++) {
int minIndex = i;
for (int j = i + 1; j <= s; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 0 || n > capacity || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int x, y;
cout << "Введіть індекси x та y: ";
cin >> x >> y;
if (x >= 0 && x <= y && y < n) {
SortArr_1(mass, n, x, y);
} else {
cout << "Некоректні межі, масив не змінено\n";
}
PrintArr(mass, n);
}
return 0;
}Приклад 3 · Бульбашка, потім розворот
Спочатку сортуємо від меншого до більшого. Потім розвертаємо весь масив функцією SwapArr з попередніх сторінок. Отримуємо порядок від більшого до меншого.
void SortArr_2(int arr[], int n) {
for (int pass = 0; pass < n - 1; pass++) {
for (int j = 0; j < n - 1 - pass; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}void SwapArr(int arr[], int n, int k1, int k2) {
if (k1 >= 0 && k1 <= k2 && k2 < n) {
while (k1 < k2) {
int temp = arr[k1];
arr[k1] = arr[k2];
arr[k2] = temp;
k1++;
k2--;
}
}
}SortArr_2(mass, n);
SwapArr(mass, n, 0, n - 1);Тут SwapArr розвертає всю зазначену ділянку, а не лише обмінює два граничні елементи. Після обміну крайніх чисел її межі рухаються до середини.
Повна програма для прикладу 3
Введіть n, a, b: кількість n від 0 до 100, межі −100 ≤ a ≤ b ≤ 100. Наприклад: 6 −10 20 (мінус вводьте звичайною клавішею). Для прикладів 2 та 4 після виведення масиву введіть індекси x і y. Кожну повну програму запускайте окремо.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
if (n == 0) cout << "Масив порожній";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
void SortArr_2(int arr[], int n) {
for (int pass = 0; pass < n - 1; pass++) {
for (int j = 0; j < n - 1 - pass; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void SwapArr(int arr[], int n, int k1, int k2) {
if (k1 >= 0 && k1 <= k2 && k2 < n) {
while (k1 < k2) {
int temp = arr[k1];
arr[k1] = arr[k2];
arr[k2] = temp;
k1++;
k2--;
}
}
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 0 || n > capacity || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
SortArr_2(mass, n);
PrintArr(mass, n);
SwapArr(mass, n, 0, n - 1);
PrintArr(mass, n);
}
return 0;
}Приклад 4 · Ділянка методом бульбашки
Порівнюємо сусідів тільки в межах k…s. Після кожного проходу правий край ділянки вже готовий, тому межа внутрішнього циклу скорочується.
void SortArr_2(int arr[], int n, int k, int s) {
if (k >= 0 && k <= s && s < n) {
for (int pass = 0; pass < s - k; pass++) {
for (int j = k; j < s - pass; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}Виклик: SortArr_2(mass, n, 1, 4);. Для масиву 6 4 1 5 2 9 результат той самий: 6 1 2 4 5 9.
Щоб упорядкувати цю ділянку від більшого до меншого, після сортування викличте SwapArr(mass, n, 1, 4);. Елементи поза ділянкою залишаться на місцях.
Повна програма для прикладу 4
Введіть n, a, b: кількість n від 0 до 100, межі −100 ≤ a ≤ b ≤ 100. Наприклад: 6 −10 20 (мінус вводьте звичайною клавішею). Для прикладів 2 та 4 після виведення масиву введіть індекси x і y. Кожну повну програму запускайте окремо.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
if (n == 0) cout << "Масив порожній";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
void SortArr_2(int arr[], int n, int k, int s) {
if (k >= 0 && k <= s && s < n) {
for (int pass = 0; pass < s - k; pass++) {
for (int j = k; j < s - pass; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 0 || n > capacity || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int x, y;
cout << "Введіть індекси x та y: ";
cin >> x >> y;
if (x >= 0 && x <= y && y < n) {
SortArr_2(mass, n, x, y);
} else {
cout << "Некоректні межі, масив не змінено\n";
}
PrintArr(mass, n);
}
return 0;
}Приклад 5 · Увесь масив вставленням
Зберігаємо наступне число у value. Зсуваємо більші числа праворуч і записуємо value на потрібну позицію.
void SortArr_3(int arr[], int n) {
for (int i = 1; i < n; i++) {
int value = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > value) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = value;
}
}Виклик: SortArr_3(mass, n);. Умова спочатку перевіряє j ≥ 0. Якщо j = −1, друга частина вже не обчислюється, тому до arr[−1] не звертаємося.
Це сортування наявних чисел. Функцію InsArr не викликаємо та n не збільшуємо.
Повна програма для прикладу 5
Введіть n, a, b: кількість n від 0 до 100, межі −100 ≤ a ≤ b ≤ 100. Наприклад: 6 −10 20 (мінус вводьте звичайною клавішею). Для прикладів 2 та 4 після виведення масиву введіть індекси x і y. Кожну повну програму запускайте окремо.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
if (n == 0) cout << "Масив порожній";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
void SortArr_3(int arr[], int n) {
for (int i = 1; i < n; i++) {
int value = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > value) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = value;
}
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cout << "Введіть n, a, b: ";
cin >> n >> a >> b;
if (n < 0 || n > capacity || a < -100 || b > 100 || a > b) {
cout << "Некоректні дані\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
SortArr_3(mass, n);
PrintArr(mass, n);
}
return 0;
}Сортуємо лише обрану ділянку
Бліді комірки поза ділянкою не змінюються. Помаранчеві беруть участь у поточній дії. Зелені показують готові позиції під час сортування. Для спадного порядку після сортування окремо виконується розворот.
Варіанти для самостійної роботи
Зберігайте зазначені назви функцій. Ділянки задавайте індексами, відлік починається з 0. Перед сортуванням за знайденими межами перевіряйте результати пошуку: −1 означає, що елемент не знайдено.
Порожній масив та ділянку без елементів не сортуємо. Один елемент уже впорядкований. Максимумів і мінімумів у порожньому масиві немає.
Варіант 1
Відсортуйте за незростанням одновимірний масив. Використовуйте функції: RandArr, PrintArr, SortArr_1, SwapArr.
↑ До вибору варіантаВаріант 2
Відсортуйте за неспаданням одновимірний масив. Використовуйте функції: RandArr, PrintArr, SortArr_2.
↑ До вибору варіантаВаріант 3
Відсортуйте за незростанням кожну половину одновимірного масиву. Використовуйте функції: RandArr, PrintArr, SortArr_1, SwapArr.
Для однозначності: перша частина має n / 2 елементів, друга містить решту. За непарного n середній елемент входить до другої частини. Кожну частину сортуйте окремо.
↑ До вибору варіантаВаріант 4
Відсортуйте за неспаданням кожну половину одновимірного масиву. Використовуйте функції: RandArr, PrintArr, SortArr_2.
Для однозначності: перша частина має n / 2 елементів, друга містить решту. За непарного n середній елемент входить до другої частини. Кожну частину сортуйте окремо.
↑ До вибору варіантаВаріант 5
Відсортуйте першу половину одновимірного масиву за незростанням, а другу половину за неспаданням. Використовуйте функції: RandArr, PrintArr, SortArr_1, SwapArr.
Для однозначності: перша частина має n / 2 елементів, друга містить решту. За непарного n середній елемент входить до другої частини. Кожну частину сортуйте окремо.
↑ До вибору варіантаВаріант 6
Відсортуйте першу половину одновимірного масиву за неспаданням, а другу половину за незростанням. Використовуйте функції: RandArr, PrintArr, SortArr_2, SwapArr.
Для однозначності: перша частина має n / 2 елементів, друга містить решту. За непарного n середній елемент входить до другої частини. Кожну частину сортуйте окремо.
↑ До вибору варіантаВаріант 7
Відсортуйте за неспаданням елементи одновимірного масиву між першим та останнім додатними елементами. Якщо хоча б один із елементів не знайдено, то виведіть повідомлення. Використовуйте функції: RandArr, PrintArr, FindFirst, FindLast, SortArr_1.
Слово «між» у цих варіантах означає без обох граничних елементів. Обидва індекси знайдіть до сортування; менший позначте L, більший R. Сортуйте від L + 1 до R − 1, якщо L + 1 ≤ R − 1. Якщо межі збігаються чи стоять поруч, сортувати нічого.
↑ До вибору варіантаВаріант 8
Відсортуйте за незростанням елементи одновимірного масиву між першим та останнім від’ємними елементами. Якщо хоча б один із елементів не знайдено, то виведіть повідомлення. Використовуйте функції: RandArr, PrintArr, FindFirst, FindLast, SortArr_2, SwapArr.
Слово «між» у цих варіантах означає без обох граничних елементів. Обидва індекси знайдіть до сортування; менший позначте L, більший R. Сортуйте від L + 1 до R − 1, якщо L + 1 ≤ R − 1. Якщо межі збігаються чи стоять поруч, сортувати нічого.
↑ До вибору варіантаВаріант 9
Відсортуйте за неспаданням елементи одновимірного масиву між першим та останнім парними елементами. Якщо хоча б один із елементів не знайдено, то виведіть повідомлення. Використовуйте функції: RandArr, PrintArr, FindFirst, FindLast, SortArr_1.
Слово «між» у цих варіантах означає без обох граничних елементів. Обидва індекси знайдіть до сортування; менший позначте L, більший R. Сортуйте від L + 1 до R − 1, якщо L + 1 ≤ R − 1. Якщо межі збігаються чи стоять поруч, сортувати нічого.
↑ До вибору варіантаВаріант 10
Відсортуйте за незростанням елементи одновимірного масиву між першим парним та останнім непарним елементами. Якщо хоча б один із елементів не знайдено, то виведіть повідомлення. Використовуйте функції: RandArr, PrintArr, FindFirst, FindLast, SortArr_2, SwapArr.
Слово «між» у цих варіантах означає без обох граничних елементів. Обидва індекси знайдіть до сортування; менший позначте L, більший R. Сортуйте від L + 1 до R − 1, якщо L + 1 ≤ R − 1. Якщо межі збігаються чи стоять поруч, сортувати нічого.
↑ До вибору варіантаВаріант 11
Відсортуйте за неспаданням елементи одновимірного масиву між першим мінімальним та останнім максимальним елементами. Якщо масив порожній, то виведіть повідомлення. Використовуйте функції: RandArr, PrintArr, IndMin, IndMax, SortArr_1.
Слово «між» у цих варіантах означає без обох граничних елементів. Обидва індекси знайдіть до сортування; менший позначте L, більший R. Сортуйте від L + 1 до R − 1, якщо L + 1 ≤ R − 1. Якщо межі збігаються чи стоять поруч, сортувати нічого.
↑ До вибору варіантаВаріант 12
Відсортуйте за незростанням елементи одновимірного масиву до першого мінімального елемента, та за неспаданням після нього. Мінімальний елемент залиште на місці. Використовуйте функції: RandArr, PrintArr, IndMin, SortArr_2, SwapArr.
Індекси всіх зазначених мінімумів або максимумів визначте у початковому масиві й збережіть до будь-якого сортування. Для ділянки без елементів функцію не викликайте.
↑ До вибору варіантаВаріант 13
Відсортуйте за неспаданням елементи одновимірного масиву до першого максимального елемента, та за незростанням після нього. Максимальний елемент залиште на місці. Використовуйте функції: RandArr, PrintArr, IndMax, SortArr_1, SwapArr.
Індекси всіх зазначених мінімумів або максимумів визначте у початковому масиві й збережіть до будь-якого сортування. Для ділянки без елементів функцію не викликайте.
↑ До вибору варіантаВаріант 14
Відсортуйте за неспаданням елементи одновимірного масиву до першого максимального елемента, за незростанням між першим та останнім максимальними елементами включно з ними, та за неспаданням після останнього максимального. Використовуйте функції: RandArr, PrintArr, IndMax (дві функції: для першого та для останнього), SortArr_2, SwapArr.
Індекси всіх зазначених мінімумів або максимумів визначте у початковому масиві й збережіть до будь-якого сортування. Для ділянки без елементів функцію не викликайте.
Середня ділянка тут включає обидва знайдені граничні елементи, як і зазначено в умові. Після сортування їхні значення можуть опинитися на інших позиціях усередині цієї ділянки. Якщо індекси збігаються, середня ділянка має один елемент.
↑ До вибору варіантаВаріант 15
Відсортуйте за незростанням елементи одновимірного масиву до першого мінімального елемента, за неспаданням між першим та останнім мінімальним елементами включно з ними, та за незростанням після останнього мінімального. Використовуйте функції: RandArr, PrintArr, IndMin (дві функції: для першого та для останнього), SortArr_1, SwapArr.
Індекси всіх зазначених мінімумів або максимумів визначте у початковому масиві й збережіть до будь-якого сортування. Для ділянки без елементів функцію не викликайте.
Середня ділянка тут включає обидва знайдені граничні елементи, як і зазначено в умові. Після сортування їхні значення можуть опинитися на інших позиціях усередині цієї ділянки. Якщо індекси збігаються, середня ділянка має один елемент.
↑ До вибору варіантаВаріант 16
Відсортуйте за неспаданням два одновимірні масиви: arr1 з n елементів та arr2 з m елементів. Використовуйте функції: RandArr, PrintArr, SortArr_2. Напишіть функцію з прототипом void MergeArr(int arr1[], int n, int arr2[], int m, int arr3[]), яка зливає масиви arr1 та arr2 у масив arr3, не порушуючи зростання. Масив arr3 не сортувати!
Масив arr3 має містити n + m елементів; за n ≤ 100 і m ≤ 100 оголосіть int arr3[200]. Зливайте вже впорядковані масиви послідовним вибором наступного числа з arr1 або arr2. Однакові значення зберігайте, готовий arr3 повторно не сортуйте. У прототипі виправлено пропущений тип void.
↑ До вибору варіантаВаріант 17
Відсортуйте за незростанням два одновимірні масиви: arr1 з n елементів та arr2 з m елементів. Використовуйте функції: RandArr, PrintArr, SortArr_3, SwapArr. Напишіть функцію з прототипом void MergeArr(int arr1[], int n, int arr2[], int m, int arr3[]), яка зливає масиви arr1 та arr2 у масив arr3, не порушуючи спадання. Масив arr3 не сортувати!
Масив arr3 має містити n + m елементів; за n ≤ 100 і m ≤ 100 оголосіть int arr3[200]. Зливайте вже впорядковані масиви послідовним вибором наступного числа з arr1 або arr2. Однакові значення зберігайте, готовий arr3 повторно не сортуйте. У прототипі виправлено пропущений тип void.
↑ До вибору варіанта