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

Материал из Википедии — свободной энциклопедии

Cортировка выбором (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая что сравнения делаются за постоянное время.

[править] Алгоритм

Шаги алгоритма:

1. находим минимальное значение в текущем списке
2. производим обмен этого значения со значением на первой позиции
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент

Если вы захотите сами изобрести алгоритм сортировки, то вполне вероятно, что вы напишете алгоритм подобный сортировке методом вставок, потому что он, по-видимому, наиболее интуитивно понятный и легко описываемый.

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

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

[править] Примеры реализации

[править] C

for (i = 0; i < n-1; i++) {
   min = i;
   for (j = i+1; j < n; j++) {
      if (x[min] > x[j]) {
         min = j;
      }
   }
   temp = x[i];
   x[i] = x[min];
   x[min] = temp;
}

[править] C++

template <class T>
void Selection_sort( T a[], const int n )
{
    for( int i=0; i<n-1; ++i )
    {
        int min = i;
        for( int j=i+1; j<n; ++j )      
            if( a[min] > a[j] ) min = j;
        T tmp = a[i];
        a[i] = a[min];
        a[min] = tmp;
    }
}

[править] Pascal

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;
  t := a[i];
  a[i] := a[min];
  a[min] := t;  
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;

[править] Бейсик

For i = 1 To n - 1
   min = i
   For j = i + 1 To n
      If x(min) > x(j) Then min = j
   Next j
   Swap x(i), x(min)
Next i

[править] Глагол

ОТ i := 0 ДО n-1 ВЫП
  m := i;
  ОТ j := i+1 ДО n-1 ВЫП
    ЕСЛИ x[m] > x[j] ТО m := j КОН
  КОН;
  t := x[i];
  x[i] := x[m];
  x[m] := t
КОН

[править] 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;
}

[править] Python

#!/bin/python
def sort(w):
        g=len(w)
        e=[]
        i=0
        h=0
        while i<len(w):
                if h<int(w[i]):
                        h=int(w[i])
                i=i+1
        while len(e)!=g:
                i=0
                y=h
                while i<len(w):
                        if int(w[i])<y:
                                y=int(w[i])
                        i=i+1
                w.remove(str(y))
                e.append(str(y))
        return e;

[править] Литература

• Ананий В. Левитин Глава 3. Метод грубой силы: Сортировка выбором // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 143-144. — ISBN 0-201-74395-7