Сортировка выбором в языке программирования C

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

Алгоритм сортировки выбором состоит из следующих шагов:

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

Вот пример реализации сортировки выбором на языке программирования C:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        // Обмен значениями между arr[i] и arr[min_idx]
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;
    
    printf("Исходный массив: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
        
    selectionSort(arr, n);
    
    printf("\nОтсортированный массив: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
        
    return 0;
}
    

В приведенном примере мы используем функцию selectionSort, которая принимает массив arr и его размер n в качестве параметров. Алгоритм сортировки выбором реализуется с помощью вложенных циклов for. Во внутреннем цикле мы находим индекс минимального элемента в неотсортированной части массива. Затем мы обмениваем значения между текущим элементом и элементом с наименьшим значением. После завершения алгоритма массив будет отсортирован в порядке возрастания.

Исходный массив: 64 25 12 22 11 Отсортированный массив: 11 12 22 25 64

Таким образом, мы рассмотрели алгоритм сортировки выбором и предоставили пример его реализации на языке программирования C. Этот алгоритм является простым, но неэффективным на больших массивах данных. Если требуется сортировка больших объемов данных, более эффективные алгоритмы, такие как сортировка слиянием или быстрая сортировка, могут быть предпочтительными.