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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 28: Строка 28:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3
 
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элемент
+
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами
 
|-
 
|-
 
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
 
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
Строка 36: Строка 36:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3
 
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элемент
+
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами
 
|-
 
|-
 
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
 
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
Строка 44: Строка 44:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элемент
+
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами
 
|-
 
|-
 
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
 
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
Строка 52: Строка 52:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 '''4''' '''5'''
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элемент
+
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и четвертый элементы местами
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5
 
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 4 5

Версия 10:41, 22 мая 2012

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

Алгоритм

На каждом [math]i[/math]-ом шаге алгоритма находим [math]i[/math]-ый минимальный элемент и меняем его местами с [math]i[/math]-ым элементом в массиве. Таким образом, будет получен массив отсортированный по неубыванию.

Реализация

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

Пример

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

Массив Описание шага
Первый проход (текущий массив начинается с первого элемента)
5 4 1 2 3 Находим первый минимальный элемент — 1
1 4 5 2 3 Меняем минимальный и первый элементы местами
Второй проход (текущий массив начинается со следующего элемента)
1 5 4 2 3 Находим следующий минимальный элемент — 2
1 2 4 5 3 Меняем минимальный и второй элементы местами
Третий проход (текущий массив начинается со следующего элемента)
1 2 4 5 3 Находим следующий минимальный элемент — 3
1 2 3 5 4 Меняем минимальный и третий элементы местами
Четвертый проход (текущий массив начинается со следующего элемента)
1 2 3 5 4 Находим следующий минимальный элемент — 4
1 2 3 4 5 Меняем минимальный и четвертый элементы местами
1 2 3 4 5 Массив отсортирован


Ссылки

Литература

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