|
Сортировка выбором
Сортировка выбором (англ. selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из элементов имеет время выполнения в худшем, среднем и лучшем случае , предполагая что сравнения делаются за постоянное время. Алгоритм без дополнительного выделения памяти Шаги алгоритма:
Реализация алгоритма на языках программированияДалее находится пример неустойчивой реализации данного алгоритма: 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);
}
}
}
Почему такая реализация неустойчива?Покажем, почему данная реализация является неустойчивой. Рассмотрим следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю. Теперь заметим, что взаимное расположение элементов Сравнение с другими алгоритмами сортировкиТак как после каждого прохода по внутреннему циклу делается только один обмен, то общее число обменов равно , что в раз меньше, чем в сортировке пузырьком.
Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе сортировкой выбором составило ≈ 40 секунд, а ещё более улучшенной сортировкой пузырьком ≈ 30 секунд. Литература
См. такжеСсылки
|
||||||||||||||||||||||||||||||||||||
