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

Это наиболее простой и очевидный способ сортировки.

Выбирается минимальный элемент массива, затем он меняется местами с первым элементом.

Теперь массив состоит из двух частей: отсортированной, в которой на данный момент один элемент, и неотсортированной, содержащей все остальные элементы.

Далее описанные шаги повторяются для неотсортированной части массива, в результате чего отсортированная часть массива увеличивается. а неотсортированнаяч — уменьшается.

В итоге приходится несколько раз просматривать неотсортированные элементы в поисках минимального. Асимптотическая сложность данного алгоритма — O(N²).

Приводим алгоритм сортировки выбором на разных языках программирования.


#include <stdio.h>
#include <stdlib.h>

int arr[] = { 12,5,4,9,8,10,0,2,1,3, -1 };

void selection_sort(int ar[], int length)
{
	int min, minIndex, i;
	min = 0;
	minIndex = 0;

	for (i = 0; i < length - 1; i++) {
		min = ar[i];
		minIndex = i;
		for (int j = i + 1; j < length; j++) {
			if (ar[j] < min) {
				min = ar[j];
				minIndex = j;
			}
		}

		if (i != minIndex) {
			ar[minIndex] = ar[i];
			ar[i] = min;
		}
	}
}

void show(const int ar[], int length)
{
	for (int i = 0; i < length; i++)
		printf("%d ", ar[i]);
	puts("\n========================\n");
}

int main(void)
{
	int length = sizeof(arr) / sizeof(*arr);

	show(arr, length);

	selection_sort(arr, length);

	show(arr, length);

	return 0;
}


internal class Program
{
    static void SelectionSort(T[] arr) where T: IComparable 
    {
        int length=arr.Length;
        
        for(int i=0; i<length-1; i++)
        {
            int minIndex = i;
            for(int j=i+1; j<length; j++)
            {
                if (arr[j].CompareTo(arr[minIndex])==-1)
                {                      
                    minIndex = j;
                }
            }

            if (i!=minIndex)
            {
                T temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    static void Main(string[] args)
    {
        int[] arr = { 12, 5, 4, 9, 8, 10, 0, 2, 1, 3 };
        
        Console.WriteLine($"Array: {string.Join(" ", arr)}");

        SelectionSort(arr1);

        Console.WriteLine($"Sorted array: {string.Join(" ", arr)}");

        Console.ReadKey();
    }
}

<?php

function SelectionSort(array &$arr): void
{
    $length=count($arr);
    $min=0;
    $minIndex=0;
    
    for($i=0; $i<$length-1; $i++) {
        $min=$arr[$i];
        $minIndex=$i;
        for($j=$i+1; $j<$length; $j++) {
            if ($arr[$j]<$min) {
                $min=$arr[$j];
                $minIndex=$j;
            }
        }

        if ($i!=$minIndex) {
            $arr[$minIndex]=$arr[$i];
            $arr[$i]=$min;
        }
    }
}

function SelectionSort(arr) 
{
    if (Array.isArray(arr)) {
       const len=arr.length;
       
       let min=0,
           minIndex=0;

           for (let i = 0; i < len - 1; i++) {
            min = arr[i];
            minIndex = i;
            for (let j = i + 1; j < len; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
        
            if (i != minIndex) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
    else {
        throw new Error("Argument must be of type Array");
    }
}