Сортировка выбором — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 7: Строка 7:
  
 
== Алгоритм ==
 
== Алгоритм ==
[[file:Selection_sort.png|thumb|150px|Пример работы алгоритма]]
+
[[file:Selection_sort.png|thumb|300px|Пример работы алгоритма]]
 
0. Назовем элементы массива списком.
 
0. Назовем элементы массива списком.
  
Строка 16: Строка 16:
 
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.
 
3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.
  
=== Пример ===
+
'''Пример'''
  
 
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.
 
Пусть дана последовательность из <tex>6</tex> элементов <tex>5, 4, 1, 6, 2, 3</tex>.

Версия 15:05, 20 мая 2012

Сортировка выбором (англ. selection sort) - это простой алгоритм сортировки со сложностью [math]O(n^2)[/math], где [math]n[/math] - количество элементов для сортировки. Сортировка выбором предназначена для решения задачи сортировки (sorting problem).

Задача сортировки

На входе последовательность из [math]n[/math] чисел.

На выходе отсортированная последовательность по неубыванию.

Алгоритм

Пример работы алгоритма

0. Назовем элементы массива списком.

1. Находим номер минимального элемента из текущего списка.

2. Меняем минимальный элемент с первым элементом списка.

3. Если список пуст, то массив отсортирован. Иначе вернемся к шагу 1, убрав первый элемент из списка.

Пример

Пусть дана последовательность из [math]6[/math] элементов [math]5, 4, 1, 6, 2, 3[/math].

Белым фоном обозначен текущий список, зеленым отсортированная часть, а красным минимальный элемент.

Реализация

 // Входной массив x, содержащий n элементов.
 for (i = 0 to n - 1)
    int min = i;
       for (j = i + 1 to n - 1)
          if (x[j] < x[min])
             min = j;
    swap(x[i], x[min]);
 // Массив x отсортирован

Ссылки

Литература

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4