Сортировка выбором/Selection sort

Сортировка выбором - это еще один простой алгоритм сортирования. Сортировка выбором является сортировкой на месте. Полезна на небольших файлах. Используется для сортировки файлов с большими значениями и маленькими ключами. Это потому, что сортировка выбором построена на работе с ключами и обмен елементов применяется только там где необходимо.

Преимущества:

  1. Простой в применении
  2. Сортировка на месте(не использует дополнительного места)

Недостатки:

  1. Не очень хорошо масштабируется (О(n^2))

Алгоритм:

  1. Найти наименьший элемент в массиве.
  2. Поменять наименьший элемент с текущим.
  3. Продолжать до тех пор пока массив не будет отсортирован.

Пример на Java:

//Selection sort Algorithm
public static void SelectionSort(Integer[] vector) {
	int min, temp;
	for (int i = 0; i < vector.length - 1; i++) {
		min = i;
		for (int j = i+1; j < vector.length; j++) {
			if (vector[j] < vector[min]) {
				min = j;
			}
		}
		temp = vector[min];
		vector[min] = vector[i];
		vector[i] = temp;
	}
}
LikeMe: