Сортировка Выбором (Selection-sort)

Подробности
Категория: Сортировка и поиск

Сортировка выбором – возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду.

 

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

 

  1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;
  2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;
  3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key?1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
  4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

 



С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

 

 

Худшее время

О(n2)
Лучшее время

О(n2)
Среднее время

О(n2)
Затраты памяти

О(n) всего, O(1) дополнительно

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

C

for (int i = 0; i < size - 1; i++) {
/* устанавливаем начальное значение минимального индекса */
        int min_i = i;
	/* находим индекс минимального элемента */
	for (int j = i + 1; j < size; j++) {
		if (array[j] < array[min_i]) {
			min_i = j;
		}
	}
	/* меняем значения местами */
	int temp = array[i];
	array[i] = array[min_i];
	array[min_i] = temp;
}

 

 

C++

template <typename T, typename C = less< typename T::value_type> >
void select_sort( T f, T l, C c = C() )
{
    if (f!= l) {
        while (f != l - 1) {
            T min = f;
            for (T i = f + 1; i != l; i++) {
                if (c(*i, *min)) {
                    typename T::value_type tmp = *min;
                    *min = *i;
                    *i = tmp;
                }
            }
            f++;
        }
    }
}

 

 

C#

public void SelectionSort(int[] arr)
{
    int min, temp;
    int length = arr.Length;
 
    for (int i = 0; i < length - 1; i++)
    {
        min = i;
 
        for (int j = i + 1; j < length; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
 
        if (min != i)
        {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

 

 

Паскаль

for i := 1 to n - 1 do begin
    min := i;
    for j := i + 1 to n do
        if a[min] > a[j] then
            min := j;
    if min<>i then begin
        t := a[i];
        a[i] := a[min];
        a[min] := t;
    end;
end;

 

 

Компонентный Паскаль

PROCEDURE SelectionSort (VAR a: ARRAY OF REAL);
  VAR
    i, min: INTEGER;
    t: REAL;
BEGIN
  FOR i := 0 TO LEN(a) - 2 DO
    min := i;
    FOR j := i + 1 TO LEN(a) - 1 DO
      IF a[min] > a[j] THEN min := j END
    END;
    t := a[i]; a[i] := a[min]; a[min] := t
  END
END SelectionSort;

 

 

D

void selectionSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length - 1; ++i) {
        int min = array[i];
        int nmin = i;
        for (int j = i + 1; j < length; ++j) {
            if (array[j] < min) {
                min = array[j];
                nmin = j;
            }
        }
        array[nmin] = array[i];
        array[i] = min;
    }
}

 

 

VBA

Sub Sort(Mus() As Long)
    Dim n As Long, i As Long, j As Long, min As Long
 
    n = UBound(Mus)
    For i = LBound(Mus) To n - 1
       min = i
       For j = i + 1 To n
          If Mus(min) > Mus(j) Then min = j
       Next
       Swap Mus(i), Mus(min)
    Next
End Sub

 

 

Java

Итерационный алгоритм:

public static void selectionSort (int[] numbers){
    int min, temp;
 
    for (int index = 0; index < numbers.length-1; index++){
        min = index;
        for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
                min = scan;
 
        // Swap the values
        temp = numbers[min];
        numbers[min] = numbers[index];
        numbers[index] = temp;
    }
}

 

Рекурсивный алгоритм:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
 
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
 
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
 
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

 

 

Ruby

a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
 
for i in 0..a.length - 1
 
  min = i
 
  for j in i + 1..a.length - 1
 
    min = j if a[min] > a[j]
 
  end
 
  a[i], a[min] = a[min], a[i]
 
end
 
puts "#{a.join(" ")}"
 
# output => 1 3 3 5 8 10 11 12 17 20

 

 

Python

неустойчивая:

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def select_sort(arr):
    i = len(arr)
    while i > 1:
        max = 0
        for j in xrange(i):
            if arr[j] > arr[max]:
                max = j
        swap(arr, i - 1, max)
        i -= 1

 

устойчивая:

def select_sort_stable(arr):
    if(len(arr) == 0): return
    for j in xrange(len(arr)):
        min = j
        for i in xrange(j+1, len(arr)):
            if(arr[i] < arr[min]): min = i
	if(min != j):
            value = arr[min]
            for l in xrange(min, j-1,-1):
                arr[l] = arr[l-1]
            arr[j] = value

 

 

Ada

type arr is array(1..n) of integer;
   i,j,t:integer;
   min:integer;
   mas1:arr;
begin
   for i in 1..n-1 loop
      min:=i;
      for j in i+1..n loop
         if mas1(min)>mas1(j) then
            min:=j;
         end if;
         end loop;
         t:=mas1(i);
         mas1(i):=mas1(min);
         mas1(min):=t;
   end loop;
end sort;

 

 

PHP

$size = count($arr);
 
for ($i = 0; $i < $size; $i++)
{
    $min = $i;
 
    for ($j = $i + 1; $j < $size; $j++)
    {
        if ($arr[$j] < $arr[$min])
        {
            $min = $j;
        }
    }
 
    $temp = $arr[$i];
    $arr[$i] = $arr[$min];
    $arr[$min] = $temp;
}

 

 

TurboBasic 1.1

CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA VYBOROM" O(N^2)
 
L=1
R=N
MTIMER
FOR J=1 TO R-1 STEP 1
   MIN=J
   FOR I=J+1 TO R STEP 1
      IF Y[I] < Y[MIN] THEN MIN=I
   NEXT I
   IF MIN<>J THEN SWAP Y[J],Y[MIN]
 
   LOCATE 7,1                            REM
   FOR I=1 TO N:PRINT Y[I];:NEXT I:PRINT REM ANIMATION BLOCK
   DELAY 1                               REM
 
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   'PRINT "Y[X]=";Y[X]
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
PRINT FRE(-1)

Сортировка выбором проста в реализации, и в некоторых ситуациях стоит предпочесть ее наиболее сложным и совершенным методам. Но в большинстве случаев данный алгоритм уступает в эффективности последним, так как в худшем, лучшем и среднем случае ей потребуется О(n2) времени. 

 

 

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube

 







Похожие материалы

Видеотека

-->

Яндекс.Метрика