Модуль: (Python) Квадратичные сортировки


Задача

4 /8


Сортировка выбором

Теория Нажмите, чтобы прочитать/скрыть

Сортировка выбором

Сортировка выбором (англ. selection sort) — простой алгоритм сортировки со сложностью O(n2), где n — количество элементов для сортировки.

Сортировка обменом – это еще один вид простого, но неэффективного алгоритма сортировки.

Идея алгоритма достаточна проста
Проходим по массиву в поисках минимального элемента. Найденный минимум меняем местами с первым элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает первый элемент, куда мы переставили найденный минимум). К этой неотсортированной части применяем те же действия — находим минимум и ставим его на первое место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.

Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ I=0 ДО N-2 ШАГ 1
  МИН = I
  ЦИКЛ ДЛЯ J=I+1 ДО N-1 ШАГ 1
    ЕСЛИ a[J] < a[МИН],
      ТО МИН = J 
    СЛЕДУЮЩЕЕ J
  ПОМЕНЯТЬ МЕСТАМИ (a[I], a[МИН])
 СЛЕДУЮЩЕЕ I
Вычислительная сложность: \(\displaystyle O(n^{2})\).

Задача

Требуется отсортировать массив по неубыванию методом "выбора".

Входные данные 
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные 
Вывести получившийся массив.
 
Пример
№ Входные данные Выходные данные
1 5
5 4 3 2 1		 1 2 3 4 5

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python262
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!