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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 23: Строка 23:
 
     swap(x[i], x[min]);
 
     swap(x[i], x[min]);
 
   // Массив x отсортирован
 
   // Массив x отсортирован
 +
 +
== Ссылки ==
 +
*[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
 +
 +
[[Категория: Дискретная математика, алгоритмы и структуры данных]]
 +
[[Категория: Сортировка]]

Версия 15:35, 13 мая 2012

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

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

На входе последовательность из [math]n[/math] чисел ([math]x_1, x_2, ..., x_n[/math]).

На выходе перестановка данной последовательности ([math]{x_1}^{'}, {x_2}^{'}, ..., {x_n}^{'}[/math]) таким образом, что для ее членов выполняется [math]{x_1}^{'} \le {x_2}^{'} \le ... \le {x_n}^{'}[/math].

Алгоритм

Шаг 1. Выбираем минимальный элемент из текущего массива.

Шаг 2. Ставим его на первое место.

Шаг 3. Новый массив начинается со следующего элемента. Перейти к шагу 1, если массив не пустой.

Реализация

 // Входной массив 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