Сортування вибором

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування вибором
Selection sort animation.gif
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія О(n2)
Найкраща швидкодія О(n2)
Середня швидкодія О(n2)
Просторова складність у найгіршому випадку О(n), O(1)
Оптимальний Не практичний

Сортування (програмування) — це впорядкування елементів за якоюсь ознакою. Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.

Метод[ред.ред. код]

Сортування вибором

Алгоритм працює таким чином:

  1. Знаходить у списку найменше значення
  2. Міняє його місцями із першим значеннями у списку
  3. Повторює два попередніх кроки, доки список не завершиться (починаючи з другої позиції)

Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.

Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:

64 25 12 22 11
11 25 12 22 64

11 12 25 22 64
11 12 22 25 64

Сортування вставками також може працювати зі списками, які підтримують операції додавання і видалення, як то зв'язаний список. У такому разі, більш зручно видаляти зі списку найменший елемент, і вставляти його в кінець відсортованої частини масиву. Наприклад:

64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64 

Аналіз[ред.ред. код]

Сортування вибором не є складним в аналізі та порівнянні його з іншими алгоритмами, оскільки жоден з циклів не залежить від даних у списку. Знаходження найменшого елементу вимагає перегляду усіх n елементів (у цьому випадку n − 1 порівняння), і після цього, перестановки його до першої позиції. Знаходження наступного найменшого елементу вимагає перегляду n − 1 елементів, і так далі, для (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n2) порівнянь (дивіться арифметична прогресія). Кожне сканування вимагає однієї перестановки для n − 1 елементів (останній елемент знаходитиметься на своєму місці).

Приклади використання на різних мовах програмувння[ред.ред. код]

Pascal[ред.ред. код]

procedure selection_sort(var a: array of Double; min, max : integer);
     //a - динамічний масив типу Double; min, max - мінімальний та максимальний індекс масиву а.
var
    i,j,k,m:Integer;
    q:Double;
begin
    j:=min;
    m:=j;
    k:=max
    repeat
        q:=a[j];
        for i:=j to k do
            if a[i]<q then
            begin
                m:=i;
                q:=a[i];
            end;
        a[m]:=a[j];
        a[j]:=q;
        j:=j+1;
    until j=k;
end;

С[ред.ред. код]

void selection(int *array, int length)
{
    for(int i=0;i<length;i++){
            int index=i,temp=0;
            for(int j=i;j<length;j++)if(array[index]>array[j])index=j; //Finds smallest number
            temp=array[i];
            array[i]=array[index];
            array[index]=temp;
            }
 }

С++[ред.ред. код]

#include <algorithm> // for: std::iter_swap, std::min_element
 
template <typename Iterator>
void selection_sort(Iterator begin, Iterator end)
{
    Iterator min;
    while (begin != end)
    {
        min = std::min_element(begin, end);
        std::iter_swap(begin, min);
        ++begin;
    }
}

Java[ред.ред. код]

public static int[] selectionsort(int[] numbers){
    for (int i = 0; i < numbers.length-1; i++)
    {
        int index = i;
        for (int j = i+1; j < numbers.length; j++)
            if (numbers[j] < numbers[index]) //Finds smallest number
                index = j;  
 
        int smallerNumber = numbers[index];  //Swap
        numbers[index] = numbers[i];
        numbers[i] = smallerNumber;
 
    }
    return numbers;
}

Python[ред.ред. код]

def selection_sort(list):
    l = list[:]                  # створюємо копію списку
    sorted = []
 
    while len(l):                # доки присутні елементи для сортування...
        lowest = l[0]            # створюємо змінну для ідентифікації найменшого елементу
 
        for x in l:              # і перевіряємо кожен елементи списку...
            if x < lowest:       # ...чи він не найменший
                lowest = x
 
        sorted.append(lowest)    # додаємо найменший елемент до нового списку
        l.remove(lowest)         # і видаляємо його зі старого
 
    return sorted

Ruby[ред.ред. код]

def selectionsort(list)
  0.upto(list.size-1) do |start|
    min = start
    start.upto(list.size-1) do |i|
      min = i if list[i] < list[min]
    end
    list[start], list[min] = list[min], list[start]
  end
  list
end

ActionScript 3.0[ред.ред. код]

private function sortMethodSelection(array:Array):Array
{
   var countIteration:int = array.length;
   var max:int;
   var tmp:int; 
   while (countIteration > 0)
   {
      max = 0;
      for (var i:int = 1; i < countIteration; i++)
         if (array[i] > array[max]) max = i; 
         tmp = array[countIteration -1];
         array[countIteration-1] = array[max];
         array[max] = tmp;
         countIteration--;              
   }                    
   return array;
 }

Посилання[ред.ред. код]