В этой статье рассмотрим один из методов сортировки, который называется — метод выбора. Будет приведен алгоритм и его реализация на языке Си.
На первом проходе цикла выбирается минимальный элемент из текущей последовательности и меняется местами с первым элементом последовательности. На следующей итерации цикла поиск минимального элемента осуществляется со второй позиции, после меняется местами найденный минимальный элемент со вторым в списке. Такую процедуру выполняем до конца массива, пока он весь не будет отсортирован.
При сортировке методом выбора среднее число сравнений пропорционально 0,5N², а число перестановок за всё время сортировки пропорционально числу N/2 (N — число элементов в последовательности).
Приведем реализацию алгоритма на языке программирования Си.
|
1 2 3 4 5 6 7 8 9 10 |
for (int i = 0; i < N; i++) { minPosition = i; for (int j = i + 1; j < N; j++) if (mass[minPosition] > mass[j]) minPosition = j; tmp = mass[minPosition]; mass[minPosition] = mass[i]; mass[i] = tmp; } |
N — число элементов в массиве, mass[] — массив элементов.
Напишем программу на языке Си, которая считывает с клавиатуры последовательность элементов, сортирует ее методом выбора, и выводит результат сортировки на экран.
|
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 |
#include <stdio.h> #include <malloc.h> int main() { int N; printf("Input N: "); scanf_s("%d", &N); int* mass; mass = (int *)malloc(N * sizeof(int)); printf("Input the array elements:\n"); for (int i = 0; i < N; i++) scanf_s("%d", &mass[i]); //сортировка методом выбора int minPosition, tmp; for (int i = 0; i < N; i++) { minPosition = i; for (int j = i + 1; j < N; j++) if (mass[minPosition] > mass[j]) minPosition = j; tmp = mass[minPosition]; mass[minPosition] = mass[i]; mass[i] = tmp; } printf("Sorted array:\n"); for (int i = 0; i < N; i++) printf("%d ", mass[i]); printf("\n"); free(mass); return 0; } |
Прокомментируем код. Считываем число N — количество элементов в массиве (строка 8), выделяем память под массив (строка 10), считываем элементы массива (строки 12-13), выполняем сортировку методом выбора (строки 17-26), выводим отсортированный массив на экран (29-30), освобождаем память, выделенную под массив (строка 32).
На рисунке представлена демонстрация работы программы.
Если хотите скачать исходник этой программы, написанный в Visual Studio, то нажмите на кнопку ниже.
Смотрите также:
Сортировка методом подсчета на Си
Поделиться в соц. сетях: