Ми познайомилися зі стандартним методом sort, що дозволяє здійснювати сортування списків. Проте його не завжди можна використати для розв’язання задач, в яких потрібно застосувати сортування.

Так, наприклад, якщо у попередній вправі про результати участі в олімпіаді є необхідність відсортувати список учасників за рейтингом, то окремо результати учасників метод sort відсортує, але разом із цим відсортувати прізвища учасників не вийде.

Для виконання сортування існують десятки методів сортування. Розглянемо найбільш уживані з них.

Нехай потрібно впорядкувати масив, що містить 5 елементів за зростанням:

Алгоритм сортування

Відшукати максимальний елемент з послідовності a[0]...a[4]. Максимальний елемент із цієї послідовності поміняти місцями з а[4].

Відшукати максимальний елемент із послідовності а[0]...а[3]. Максимальний елемент із цієї послідовності поміняти місцями з а[3].

Максимальний елемент із послідовності а[0]..а[1] поміняти місцями з а[1].

Так, наприклад, якщо ми маємо список а=[3,5,1,2,7], його сортування вибором максимального елемента буде мати вигляд, як на рис. 37.1, де синьою рамкою виділено діапазон пошуку максимального елемента, в блакитній клітинці вказано максимальне значення, стрілкою позначено місце переміщення максимального елемента. Відсутність стрілки вказує на те, що елемент залишається на своєму місці.

Нижче наведено програмний код, що відповідає описаному алгоритму:

Аналіз програмного коду

Неважко здогадатися, що в перших двох рядках здійснюється створення списку та виведення його на екран. У третьому рядку створено оператор циклу, що містить на одну ітерацію менше ніж кількість елементів у списку.

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

Так, для і=0 діапазон буде [0:5], що означає до 4-го елемента включно. Для і=1 діапазон буде змінено на [0:4], що означає до 3-го елемента включно. Таким чином, з допомогою вказаної конструкції і-5 значення діапазону буде зменшуватися. Останній діапазон, у якому буде здійснено пошук максимального [0:2], він буде сформований для і=3. Команда

дозволяє визначити номер знайденого максимального елемента. Цей номер потрібен для того, щоб далі вказати елементи, з якими номерами необхідно обміняти місцями.

Для обміну місцями елементів списку використовують наступну конструкцію:

Неважко здогадатися, що вона означає поміняти місцями значення елементів, що розташовані під номерами n та 4-і.

Як ви думаєте, як має змінитися даний програмний код для сортування його елементів за спаданням?

Для цього існує принаймні два варіанти. Перший і найпростіший — це пошук мінімальних значень замість максимальних. Також для зворотного сортування можна використати діапазон пошуку максимального значення та замінювати його не на останній елемент, а на перший.

До речі, у такий спосіб можна сортувати і текстові дані. При визначенні максимального значення серед двох слів більшим уважаєть-ся те, що стоїть далі за алфавітом.

Так, наприклад,

Розглянемо використання даного методу сортування текстових та числових даних, виконавши вправу.

ВПРАВА 37.1

Завдання. Програма місить дані про найбільш відомі озера України (рис. 37.1). В першому списку розташовано перелік їхніх назв, у другому — середня глибина озера, в третьому — площа. Створити обробники подій для кнопок, що мають здійснити відповідні сортування. Врахуйте, що при сортуванні даних одного списку відповідні елементи інших списків мають бути також переміщені.

Кнопка За назвою здійснює сортування озер за назвою в алфавітному порядку.

Кнопка За глибиною здійснює сортування глибин озер за спаданням.

Кнопка За площею здійснює сортування площ озер за спаданням.

1. Завантажте файл Вправа_37_1.ру із матеріалів до даного уроку.

2. Створіть обробник події натискання кнопки За назвою.

а. Створіть команду обробника події натискання кнопки та додайте оператор циклу сортування масиву name в алфавітному порядку методом вибору:

b. Оскільки відповідно до умови дані, що розміщені в інших списках, мають переміщуватися на ті ж місця, що й імена під час сортування, у тілі цього ж циклу додайте команди обміну елементами списків depth та area:

c. Додайте команди очищення списків Lbox_name, Lbox_depth, Lbox_area:

d. Додайте оператор циклу виведення відсортованих списків до елементів керування Lbox_name, Lbox_depth, Lbox_area:

3. Додайте команду виклику обробника події в конструкторі кнопки За назвою.

4. Обробники подій натискання кнопок За глибиною та За площею створіть самостійно.

ВПРАВА 37.2

Завдання. Дано список учасників олімпіади та їхні результати. У третьому списку вивести переможців олімпіади у форматі результат-прізвище, впорядкувавши їх за рейтингом у порядку спадання (рис. 37.3).

1. Завантажте файл-заготовку Вправа_37_2^ із матеріалів до даного параграфа.

2. Створіть обробник події натискання кнопки Переможці олімпіади.

a. Уведіть команду заголовка обробника події:

b. Додайте команди створення двох порожніх списків rez_n для розташування у ньому прізвищ переможців та rez для розташування їхній результатів.

c. Додайте оператор циклу для формування списків прізвищ та результатів переможців:

d. Додайте команду визначення довжини одного із утворених масивів rez або rez_n, оскільки вони мають однакову розмірність, результат надайте змінній size.

e. Додайте команду сортування масиву rez за спаданням методом вибору:

f. Аби разом з результатами під час сортування було переміщено і прізвища переможців олімпіади, у тілі циклу сортування масиву rez додайте команду обміну елементами rez_n:

g. Додайте команди вивведення списків rez та rez_n до елемента керування Lbox_rez у форматі результат-прізвище: ^{3 4}

3. Додайте команду виклику обробника події в конструкторі кнопки.

4. Запустіть програму та перевірте правильність її виконання.

ВПРАВА 37.3

Створити програми розв’язання задач, використовуючи для сортування

метод вибору.

a. Дано цілочисельний масив з 20 елементів. Відсортуйте 10 перших елементів масиву за зростанням, а 10 останніх елементів — за спаданням.

b. Дано цілочисельний масив з 15 елементів. Відсортуйте 5 перших елементів, 5 других елементів та 5 останніх елементів за спаданням. Знайдіть суму кожної п’ятірки чисел.

c. Дано дійсний масив з 10 елементів. Відсортуйте за спаданням усі елементи цього масиву, що розташовані між першим та останнім від’ємними елементами.

d*. Дано цілочисельний масив з 10 елементів. Відсортуйте за спаданням усі елементи цього масиву, що розташовані між першим парним та останнім непарним елементами. e*. Дано масив, що містить n елементів. Після впорядкування його за зростанням визначте:

скільки елементів масиву змінили своє початкове розташування; порядкові номери елементів масиву, які залишилися стояти на своїх місцях;

на якому місці в масиві знаходився елемент до сортування, який зараз розташований на k-му місці.

Контрольні запитання та завдання

1. Опишіть алгоритм сортування вибором.

2. Наведіть приклад завдання коли для сортування списку неможливо або не доцільно використовувати метод sort.

3*. Як змінити команди сортування методом вибору за зростанням для сортування цим же методом за спаданням?

Питання для роздумів

1*. Установіть послідовність, в якій змінюється список а=[5, 4, 7, 9, 6] у процесі сортування за спаданням методом вибору.

№	0	1	2	3	4
	9	7	6	5	4
	5	6	7	9	4
	9	6	7	5	4
	5	4	7	9	6

2*. Яким буде програмний код сортування методом бульбашок, якщо замість оператора циклу з параметром використати цикл з умовою?

Завдання для досліджень

1*. Дізнайтеся, які ще існують методи сортування.

 

 

Це матеріал з підручника Інформатика 9 клас Казанцева, Стеценко 2022