Перейти до змісту

ЛР14. Сортування вибором і std::sort

Коротко про роботу

Невеликий рейтинг треба впорядкувати та пояснити через інваріант відсортованого префікса. Варіант визначає STUDENT_X.

Відкрити робочий зошит Як виконувати лабораторні

1. Умова

Невеликий рейтинг треба впорядкувати та пояснити через інваріант відсортованого префікса.

Перша комірка зошита лише показує значення вашого STUDENT_X разом із типами. Вона не оголошує і не створює предметні змінні. У коді кожного завдання перенесіть потрібні значення та самостійно оголосіть/створіть відповідні змінні.

2. Що треба знати

Робота виконується після Л1–Л8. Потрібні поняття:

  1. сортування вибором
  2. відсортований префікс
  3. std::sort
  4. O(n²)

Межа матеріалу

Використовуйте поняття, вивчені до Л1–Л8. Не підміняйте власне сортування вибором викликом std::sort. Бібліотечний алгоритм тут служить перевіркою.

3. Варіант, вхідні дані та результат

У зошиті заповніть STUDENT_NAME, STUDENT_GROUP і STUDENT_X від 1 до 30.

Вхідні дані

Поле Тип Зміст
values std::vector<int> сім значень рейтингу

Поля результату

Поле Зміст
sorted_values повністю відсортована послідовність
comparison_count кількість порівнянь під час сортування вибором
matches_std_sort збіг із std::sort

Назви полів результату не змінюйте. Перша комірка лише показує значення варіанта і не оголошує предметні змінні. Перед розв’язанням кожного завдання самостійно оголосіть потрібні вхідні змінні з показаними значеннями. Власні та результуючі змінні також оголошуйте звичайно, як у лекційних прикладах. Обчислення виконуйте у блоці { ... }; код над блоком використовуйте лише там, де це позначено. Наприкінці блока вже є службовий рядок самоперевірки для контрольних полів — його не потрібно писати або змінювати. Формат std::cout обирайте за змістом завдання: спеціального формату для самоперевірки немає.

4. Терміни і правила

Терміни

  • сортування вибором — алгоритм, який на кожному проході знаходить мінімум невідсортованої частини та ставить його на наступну позицію.
  • інваріант відсортованого префікса — після кожного проходу початок послідовності вже містить правильні найменші елементи у відсортованому порядку.

Правила

  1. Сортуйте values за зростанням методом сортування вибором.
  2. Під час кожного проходу шукайте мінімум у ще невпорядкованому суфіксі.
  3. comparison_count рахує порівняння кандидатів під час пошуку мінімуму.
  4. matches_std_sort порівнює ваш повний результат із окремою копією, впорядкованою std::sort.

5. Завдання

Завдання 1

Покажіть перші два проходи сортування вибором: активну частину, індекс мінімуму та обмін.

Завдання 2

Відсортуйте values методом вибору. Запишіть sorted_values і comparison_count.

Завдання 3

Відсортуйте копію через std::sort. Запишіть результат порівняння у matches_std_sort.

6. Перевірка і здача

  1. Запустіть самоперевірку та виправте помилки.
  2. Перезапустіть ядро і виконайте роботу ще раз від початку.
  3. Збережіть .ipynb і PDF з кодом та результатами.

Назва PDF: LR14_Прізвище_Група_VNN.pdf.