Разъяснение по сортировке выбором?

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

Насколько я понимаю (в форме псевдокода):

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

Поменять местами текущий нижний элемент с первым элементом несортированного массива. Теперь это часть «отсортированного» раздела. Пройдитесь по несортированному разделу массива (все, кроме первого элемента), найдите новый самый низкий элемент и назначьте его «самому низкому». Поменяйте местами самый низкий с первым несортированным элементом. Повторение.

for i = 1 to n - 1
  min = i
  for j = i + 1 to n
    if array[j] < array[min]
      min = j
  if min != i
    swap array[min] and array[i]

Дай мне знать, если я куда-нибудь уйду.

Более того, если бы кто-то мог собрать быстрый пример простой сортировки Selection на реальном языке C, это было бы здорово!


c arrays sorting algorithm selection-sort
person brld    schedule 23.09.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Да исправить:

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

Простая сортировка выбором в c:

#include <stdio.h>

int main()
{
   int array[100], n, c, d, position, swap;

   printf("Enter number of elements\n");
   scanf("%d", &n);

   printf("Enter %d integers\n", n);

   for ( c = 0 ; c < n ; c++ )
      scanf("%d", &array[c]);

   for ( c = 0 ; c < ( n - 1 ) ; c++ )
   {
      position = c;

      for ( d = c + 1 ; d < n ; d++ )
      {
         if ( array[position] > array[d] )
            position = d;
      }
      if ( position != c )
      {
         swap = array[c];
         array[c] = array[position];
         array[position] = swap;
      }
   }

   printf("Sorted list in ascending order:\n");

   for ( c = 0 ; c < n ; c++ )
      printf("%d\n", array[c]);

   return 0;
}

Выход:

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall main.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
Enter number of elements
4
Enter 4 integers
1
2
6
-7
Sorted list in ascending order:
-7
1
2
6

Источник

person gsamaras    schedule 23.09.2016