Сортировка выбором (Vkjmnjkftg fdQkjkb)

Перейти к навигации Перейти к поиску
Сортировка выбором

Предназначение Алгоритм сортировки
Структура данных Массив
Худшее время
Лучшее время
Среднее время
Затраты памяти
Логотип Викисклада Медиафайлы на Викискладе

Сортировка выбором (англ. selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из элементов имеет время выполнения в худшем, среднем и лучшем случае , предполагая что сравнения делаются за постоянное время.

Алгоритм без дополнительного выделения памяти

[править | править код]
Сортировка выбором

Шаги алгоритма:

  1. Находим номер минимального значения в текущем списке.
  2. Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции).
  3. Теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

Реализация алгоритма на языках программирования

[править | править код]

Далее находится пример неустойчивой реализации данного алгоритма:

template <typename type_arr>
void selection_sort(type_arr *arr, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min_index = i;
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[min_index])
            {
                min_index = j;
            }
        }
        if (min_index != i)
        {
            swap(arr[i], arr[min_index]);
        }
    }
}
public static IList<T> Selection<T>(IList<T> list) where T : IComparable<T>
{
    for (int i = 0; i < list.Count - 1; ++i)
    {
        int min = i;
        for (int j = i + 1; j < list.Count; ++j)
        {
        	if (list[j].CompareTo(list[min]) < 0)
            {
                min = j;
            }
        }
        
        var dummy = list[i];
        list[i] = list[min];
        list[min] = dummy;
    }
    
    return list;
}
type sort_choice_list is table of integer index by binary_integer; 
---------------------------------------------
function SORT_CHOICE return sort_choice_list
  IS
    list sort_choise_list;
    l_min pls_integer;
    l_dummy pls_integer;
  begin 
  
      for n in 1..100 loop
        list(n):=dbms_random.random; --инициализация массива случайными числами
      end loop;
      
      for i in list.first..list.last loop
           l_min:=i;
           for j in (i + 1)..list.last loop
                if (list(j) < list(l_min)) then
                    l_min := j;
                end if;
            end loop;
            l_dummy:=list(i);
            list(i):=list(l_min);
            list(l_min) := l_dummy;
      end loop;
         
    return list;
      
end SORT_CHOICE;
	public static void selectionSort(int [] arr) {
		int n = arr.length;
		for(int i = 0; i<n-1; i++) {
			int minIndex = i;
			for(int j=i+1; j<n; j++) {
				if(arr[j]<arr[minIndex]) {
					minIndex = j;
				}
			}
			if(minIndex!=i) swap(arr,i,minIndex);
			
		}
}
def selection_sort(array)
	for min in 0..array.count-2
		least = min
		for j in (min + 1)..array.count-1
			if array[j] < array[least]
				least = j
			end
		end
		temp = array[min]
		array[min] = array[least]
		array[least] = temp
	end
end
func selectionSort<Element>(_ array: inout Array<Element>) where Element: Comparable {
	for min in 0..<array.count - 1 {
		for j in min..<array.count {
			if array[j] < array[min] {
				let temp = array[min]
				array[min] = array[j]
				array[j] = temp
			}
		}
	}
}
begin
  var a := ArrRandom;
  a.Println;

  for var i:=0 to a.High do
     Swap(a[i],a[i+a[i:].IndexMin]);

  a.Println;
end
def select_sort(A):
    for i in range(len(A) - 1):
        min_index = i
        for k in range(i + 1, len(A)):
            if A[k] < A[min_index]:
                A[k], A[min_index] = A[min_index], A[k]
    return A
func selectionSort(nums []int) {
    n := len(nums)

    for i := 0; i < n; i++ {
        min := i 
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[min] {
                min = j
            }
        }
        nums[i], nums[min] = nums[min], nums[i]
    }
}
fn selection_sort<T: Ord>(array: &mut [T]) {
    let n = array.len();

    for i in 0..n {
        let mut min_index = i;
        for j in i + 1..n {
            if array[min_index] > array[j] {
                min_index = j;
            }
        }
        if min_index != i {
            array.swap(i, min_index);
        }
    }
}

Почему такая реализация неустойчива?

[править | править код]

Покажем, почему данная реализация является неустойчивой.

Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
Массив до сортировки: { (2, a), (2, b), (1, a) }
Уже после первой итерации внешнего цикла будем иметь отсортированную последовательность: { (1, a), (2, b), (2, a) }

Теперь заметим, что взаимное расположение элементов (2, a) и (2, b) изменилось.
Таким образом, рассматриваемая реализация является неустойчивой.

Сравнение с другими алгоритмами сортировки

[править | править код]

Так как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно , что в раз меньше, чем в сортировке пузырьком.
Число проходов по внутреннему циклу равно даже в случае сортировки частично или полностью отсортированного массива.

  • Число сравнений в теле цикла равно .
  • Число сравнений в заголовках циклов .
  • Число сравнений перед операцией обмена .
  • Суммарное число сравнений .
  • Число обменов .

Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈ 40 секунд, а ещё более улучшенной сортировкой пузырьком ≈ 30 секунд.
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента. Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

Литература

[править | править код]
  • Левитин А. В. Глава 3. Метод грубой силы: Сортировка выбором // Алгоритмы. Введение в разработку и анализМ.: Вильямс, 2006. — С. 143—144. — 576 с. — ISBN 978-5-8459-0987-9
  • Роберт Седжвик. Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором // Алгоритмы на C++ = Algorithms in C++. — М.: «Вильямс», 2011. — С. 246-247. — ISBN 978-5-8459-1650-1.
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.