CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Рисование прямоугольника. (26290 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (52489 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (82355 hits)
#Сортировка Шелла, обший принцип. (136816 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (249302 hits)
#Отслеживание изменений файла. (32680 hits)
#Поразрядная сортировка, общий принцип. (120174 hits)
#Использование компилируемых(подготовленных) запросов. (25846 hits)
#Рисование множества Мандельброта. (38657 hits)
#Сортировка выбором, общий подход. (65365 hits)
#Динамическое формирование выпадающего списка. (45756 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (55048 hits)
#Рисование окружности (по Брезенхэму). (28290 hits)
#Подмножество с максимальной суммой. (120039 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (90520 hits)
#Таймер. (35836 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (33363 hits)
#Логирование в GUI. (27102 hits)
#Простой генератор случайных чисел. (127142 hits)
#Создание простейшей таблицы. (31777 hits)


Главная >> Каталог задач >> Сортировка >> Сортировка Выбором (selection sort) >> Сортировка выбором, общий подход



Сортировка выбором, общий подход

Aвтор:
Дата:
Просмотров: 65364
реализации(C++: 2шт...) +добавить

Имеется исходная неотсортированния последовательность x[0..n-1]. Отсортируем ее по возрастанию. Выбираем из нее наименьший элемент и ставим на первое место. Т.е. меняем местами найденный наименьший элемент и первый. Затем в последовательности начиная со 2-го элемента и до конца - аналогично ищем наименьший элемент и меняем его местами со 2-ым. И так далее до предпоследнего элемента. Сортировка заканчивается, когда в оставшейся неотсортированной последовательности остается 1 элемент.

Таким образом, алгоритм имеет n-1 итераций. И на каждой i(=[0..n-1])-ой итерации из элементов x[i..n-1] выбирается наименьший и меняется местами с x[i]. Когда i=n-1 сортировка прекращается и мы получаем отсортированную последовательность.

Пример. Имеется последовательность: 7, 2, 6, 5, 10, 4. n = 6. Получим:
0 шаг - i = 0, min = 2(i=1), меняем местами x[0]=7 и x[1]=2, в итоге: 2, 7, 6, 5, 10, 4
1 шаг - i = 1, min = 4(i=5), меняем местами x[1]=7 и x[5]=4, в итоге: 2, 4, 6, 5, 10, 7
2 шаг - i = 2, min = 5(i=3), меняем местами x[2]=6 и x[3]=5, в итоге: 2, 4, 5, 6, 10, 7
3 шаг - i = 3, min = 6(i=3), меняем местами x[3]=6 и x[3]=6, в итоге: 2, 4, 5, 6, 10, 7*
4 шаг - i = 4, min = 6(i=5), меняем местами x[4]=10 и x[5]=7, в итоге: 2, 4, 5, 6, 7, 10
* - пустая итерация. Физически "перестановка" осуществляется, но фактически она ничего меняет.

 псевдокод: сортировка выбором  ссылка
  1. /* до n-2, а не n-1, т.к.
  2. последний элемент уже стоит
  3. на своем месте */
  4. for i = 0 to n-2
  5. k = i
  6. t = x[i]
  7. for j = i+1 to n-1
  8. if (x[j] < t)
  9. k = j
  10. t = x[j]
  11. x[k] = x[i]
  12. x[i] = t


Алгоритм делает n-1 итераций, на каждой из которых осуществляется еще n-i проходов(сравнений) и одна перестановка. Следовательно общее количество операций получаем:
n + (n-1 + 1) + (n-2 + 1) + ... + 2 = 1/2*(n2 + 2*n) - 1. Т.о. производительность ~ O(n2).

К достоинствам можно отнести отсутствие расхода памяти: все операции перестановки происходятся на исходной последовательности.

Алгоритм - очень похож на алгоритм сортировки вставками. Можно даже сказать, что они в некотором отношении "симметричны": этот выбирает нужный элемент из неотсортированной последовательности и вставляет его последним в отсортированную, вставками - выбирает первый элемент из неотсортированных, но вставляет его в нужное место сортированной последовательности.

 

Реализации: C++(2)   +добавить реализацию

1) Сортировка выбором, общий подход, code #18[автор:this]
2) сортировка выбором, code #594[автор:-]



© 2006-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.014104 секунд
Количество запросов к БД: 14, gzip: off