Описание тега selection-sort

В информатике выборочная сортировка - это алгоритм сортировки, в частности сортировка на месте. Он имеет временную сложность O (n ²), что делает его неэффективным для больших списков и, как правило, работает хуже, чем аналогичная сортировка вставкой. Сортировка по выбору отличается своей простотой и имеет преимущество в производительности по сравнению с более сложными алгоритмами в определенных ситуациях, особенно когда вспомогательная память ограничена.

На изображении ниже показано, как работает сортировка выбора.

https://stackru.com/images/c1051b6315d3d23d0504b56887f3c362772bb5f1.gif

Приведенный ниже псевдокод помогает в создании программы (на любом языке) или понимании сортировки выбора.

procedure selection sort 
list  : array of items
n     : size of list

for i = 1 to n - 1
/* set current element as minimum*/
  min = i    

  /* check the element to be minimum */

  for j = i+1 to n 
     if list[j] < list[min] then
        min = j;
     end if
  end for

  /* swap the minimum element with the current element*/
  if indexMin != i  then
     swap list[min] and list[i]
  end if

end for

end procedure

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

• это слишком просто для понимания
• он хорошо работает в небольшом списке
• дополнительное временное хранилище не требуется, кроме того, что необходимо для хранения исходного списка

Подробнее

Ссылка на изображение: Университет RMIT