C++ · Масиви
Одновимірні масиви · 8.12.2

Функції сортування масиву

Упорядковуємо весь масив або лише обрану ділянку

Від алгоритму до функції

На попередній сторінці ми порівняли три способи сортування. Тепер оформимо їх як функції й навчимося впорядковувати лише потрібну частину масиву.

Для прикладів використовуємо знайомі 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);

Було: 6 4 1 5 2 9 Стало: 1 2 4 5 6 9
Повна програма для прикладу 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 1 2 3 4 5 Було: 6 4 1 5 2 9 Стало: 6 1 2 4 5 9

Числа з індексами 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);
Було: 6 4 1 5 2 9 Після SortArr_2: 1 2 4 5 6 9 Після SwapArr: 9 6 5 4 2 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.

↑ До вибору варіанта