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

Алгоритмы сортировки и поиска / Сортировка прямым выбором

 

Алгоритм сортировки прямым выбором в некотором смысле противоположен сортировке прямыми включениями.

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

При прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы входной последовательности и найденный элемент помещается как очередной элемент в конец готовой последовательности.









 
Метод сортировки прямым выбором основан на следующих правилах:

  • Выбирается элемент с наименьшим ключом.
  • Он меняется местами с первым элементом a0.
  • Затем эти операции повторяются с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

Сортировка прямым выбором
Реализация сортировки прямым выбором на Си

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
// Функция сортировки прямым выбором
void selectionSort(int *num, int size)
{
  int min, temp; // для поиска минимального элемента и для обмена
  for (int i = 0; i < size - 1; i++) 
  {
    min = i; // запоминаем индекс текущего элемента
    // ищем минимальный элемент чтобы поместить на место i-ого
    for (int j = i + 1; j < size; j++)  // для остальных элементов после i-ого
    {
      if (num[j] < num[min]) // если элемент меньше минимального,
        min = j;       // запоминаем его индекс в min
    }
    temp = num[i];      // меняем местами i-ый и минимальный элементы
    num[i] = num[min];
    num[min] = temp;
  }
}
int main() 
{
  int a[10]; // Объявляем массив из 10 элементов
  // Вводим значения элементов массива
  for (int i = 0; i < 10; i++) 
  {
    printf("a[%d] = ", i);
    scanf("%d", &a[i]);
  }
  selectionSort(a, 10);  // вызываем функцию сортировки
  // Выводим отсортированные элементы массива
  for (int i = 0; i<10; i++)
    printf("%d ", a[i]);
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат сортировки прямым выбором

Анализ алгоритма прямым выбором

Число сравнений ключей С не зависит от порядка ключей:

C=½(n2-n).

Число перестановок минимально

Mmin=3(n-1)

в случае изначально упорядоченных ключей и максимально

Mmax= n2/4 +3(n-1),

если первоначально ключи располагаются в обратном порядке.

Среднее число пересылок

Mср≈n(ln n + g),

где g = 0,577216... — константа Эйлера.

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


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 3

  • Алексей
    Здравствуйте! А как понимать "Число перестановок минимально Mmin=3(n-1)". В рассмотренном примере было всего 5 перестановок, а по формуле М=3(n-1)=3(8-1)=21. Или под перестановками понимается что-то другое?

  • Василий
    перед
    1
    temp = num[i];      // меняем местами i-ый и минимальный элементы
    можно добавить:
    1
    if (min == i) continue;

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *