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

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

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

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

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

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

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

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

Реализация сортировки прямым выбором
#include <stdio.h>
void selectionSort(int *num, int size) {
  int i, j;
  int min, temp;
  for (i = 0; i < size-1; i++) {
    min = i;
    for (j = i+1; j < size; j++) {
      if (num[j] < num[min])
        min = j;
    }
    temp = num[i];
    num[i] = num[min];
    num[min] = temp;
  }
}
int main() {
  int a[10];
  int i, j, index;
  for(i=0;i<10;i++) {
    printf("a[%d] = ", i);
    scanf("%d",&a[i]);
  }
  selectionSort(a,10);
  for(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... — константа Эйлера.

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

Назад

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

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