Викиконспекты - Вклад участника [ru]

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

2014-10-02T10:03:45Z

62.134.204.132: /* Реализация */

'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.

== Алгоритм ==
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.

== Реализация ==
Вариант 1.
SelectionSort(a)
for i = 0 to n - 2
min = i;
for j = i + 1 to n - 1
if a[j] < a[min]
min = j;
swap(a[i], a[min]);

Вариант 2.
SelectionSort(a)
for i = 0 to n - 2
for j = i + 1 to n - 1
if a[i] > a[j]
swap(a[i], a[j]);

== Пример ==

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

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1'''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами
|-
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2'''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами
|-
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3'''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4'''
|-
|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"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]

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

2014-10-02T09:56:45Z

62.134.204.132: /* Реализация */

'''Сортировка выбором''' (англ. '''selection sort''') {{---}} простой алгоритм сортировки со сложностью <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.

== Алгоритм ==
На каждом <tex>i</tex>-ом шаге алгоритма находим <tex>i</tex>-ый минимальный элемент и меняем его местами с <tex>i</tex>-ым элементом в массиве. Таким образом будет получен массив отсортированный по неубыванию.

== Реализация ==
Вариант 1.
SelectionSort(a)
for i = 0 to n - 1
min = i;
for j = i + 1 to n
if a[j] < a[min]
min = j;
swap(a[i], a[min]);

Вариант 2.
SelectionSort(a)
for i = 0 to n - 1
for j = i + 1 to n
if a[i] > a[j]
swap(a[i], a[j]);

== Пример ==

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

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Массив
!style="background-color:#EEE"| Описание шага
|-
|colspan=3|''Первый проход (текущий массив начинается с первого элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 5 4 '''1''' 2 3
|style="background-color:#FFF;padding:2px 10px"| Находим первый минимальный элемент {{---}} '''1'''
|-
|style="background-color:#FFF;padding:2px 10px"| '''1''' 4 '''5''' 2 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и первый элементы местами
|-
|colspan=3|''Второй проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 5 4 '''2''' 3
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''2'''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 '''2''' 4 '''5''' 3
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и второй элементы местами
|-
|colspan=3|''Третий проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 5 '''3'''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''3'''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''3''' 5 '''4'''
|style="background-color:#FFF;padding:2px 10px"| Меняем минимальный и третий элементы местами
|-
|colspan=3|''Четвертый проход (текущий массив начинается со следующего элемента)''
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 3 5 '''4'''
|style="background-color:#FFF;padding:2px 10px"| Находим следующий минимальный элемент {{---}} '''4'''
|-
|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"| 1 2 3 4 5
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC Сортировка выбором в русской википедии]

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]