Як працює алгоритм сортування вибору? Сортування вибору працює беручи найменший елемент у несортованому масиві та виводячи його на передній план. Ви будете переглядати кожен предмет (зліва направо), поки не знайдете найменший. Перший елемент у масиві тепер відсортовано, а решта масиву не відсортовано.
Сортування вибору в Java – структура даних і алгоритм
- Встановіть мінімальну змінну індексу на індекс першого елемента.
- Ітерація по несортованій частині масиву від другого елемента до останнього.
- У кожній ітерації знайдіть мінімальний елемент у невідсортованій частині, порівнюючи кожен елемент із поточним мінімумом.
Вибір Сортування Складність Кількість порівнянь: (n – 1) + (n – 2) + (n – 3) + ….. + 1 = n(n – 1) / 2 майже дорівнює n2. Крім того, ми можемо проаналізувати складність, просто спостерігаючи за кількістю циклів. Є 2 цикли, тому складність n*n = n2.
Просте рішення – це спочатку знайдіть найменший елемент і поміняйте його місцями з першим елементом. Потім знайдіть найбільший елемент, поміняйте його місцями з другим елементом, і так далі.
Кроки
- Виберіть перший елемент списку.
- Порівняти вибраний елемент з усіма іншими елементами списку.
- Для кожного порівняння, якщо будь-який елемент менший (або більший) за вибраний елемент, поміняйте ці два елементи місцями.
- Повторіть ту саму процедуру з наступною позицією в списку, доки не буде відсортовано весь список.