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

Сортировки   11 июля 2012  Автор статьи:  

Сортировка выбором один из самых простых методов сортировки. Однако достаточно неэффективный.
 
Описание алгоритма:
Пусть дана последовательность А из n элементов, нумерация элементов начинается с 0 (То есть первый элемент последовательности — A[0], второй — A[1], n-ый элемент A[n-1].) Необходимо упорядочить эту последовательность по возрастанию (по убыванию).
Сортировка выбором состоит из следующих шагов:
1. Кладется счетчик i равный 0.
2. Среди элементов последовательности от A[i] до A[n — 1] ищется минимальный элемент (максимальный элемент).
3. Меняются местами элемент A[i] и найденный на предыдущем шаге.
4. Счетчик i увеличивается на единицу.
5. Если i < n - 1, то повторяются шаги 2 - 5, в противном случае - конец алгоритма.   Пример работы алгоритма:
Пусть дана последовательность А из 5 элементов, необходимо упорядочить её по возрастанию:

1. Кладем счетчик i = 0.
2. Среди элементов от А[0] до A[4] ищем минимальный элемент.

3. Меняем местами элементы А[0] и A[4].

4. Увеличиваем счетчик i на 1. i = 1.
5. 1 < 4, переходим ко второму шагу алгоритма. 6. Среди элементов от А[1] до A[4] ищем минимальный элемент.
7. Меняем местами элементы А[1] и A[2].

8. Увеличиваем счетчик i на 1. i = 2.
9. 2 < 4, переходим ко второму шагу алгоритма. 10. Среди элементов от A[2] до A[4] ищем минимальный элемент.
11. Меняем местами элементы А[2] и A[2].

12. Увеличиваем счетчик i на 1. i = 3.
13. 3 < 4, переходим ко второму шагу алгоритма. 14. Среди элементов от А[3] до A[4] ищем минимальный элемент.
15. Меняем местами элементы А[3] и А[4].

16. Увеличиваем i на 1. i = 4.
17. 4 < 4, конец алгоритма.   Как видите, мы получили последовательность, упорядоченную по возрастанию элементов. Для получения последовательности, упорядоченной по убыванию элементов, необходимо искать максимальный, а не минимальный элемент на втором шаге алгоритма.  

Научиться программировать

  • на Delphi

  • на Java

  • на C++