Поговорим о сортировке данных методом подсчета. В этой статье будет рассмотрен алгоритм сортировки и пример программы с ее реализацией на языке программирования Си.
При сортировке методом подсчета упорядоченная последовательность элементов создается на свободном участке памяти. Идея метода заключается в следующем: в отсортированной последовательности, элемент, занимающий позицию с номером К+1, превышает ровно К элементов, поэтому в процессе сортировки методом подсчета на каждом i-ом проходе мы попарно сравниваем i-й элемент со всеми элементами массива. Если установлено, что mass[i] > mass[j], то увеличиваем счетчик К на единицу (в начале К = 0). По окончании текущего прохода счетчик К указывает количество элементов, меньших, чем mass[i], поэтому элемент mass[i] занимает в отсортированной последовательности позицию К + 1 (sortedMass[k + 1] = mass[i]).
Внимание. Рассмотренный алгоритм можно использовать только для последовательностей, которые не содержат одинаковых элементов! Для сортировки последовательностей, содержащих одинаковые элементы, алгоритм необходимо модифицировать.
Приведем реализацию алгоритма сортировки методом подсчета на языке программирования Си. Необходимо учесть, что в языке Си нумерация элементов массива начинается с нуля.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//сортировка методом подсчета void methodOfCalculation(int n, int mass[], int sortedMass[]) { int k; for (int i = 0; i < n; i++) { k = 0; for (int j = 0; j < n; j++) { if (mass[i] > mass[j]) k++; } sortedMass[k] = mass[i]; } } |
Ниже находится пример консольной программы на языке программирования Си, которая считывает исходную последовательность, сортирует ее методом подсчета и выводит отсортированный массив на экран.
|
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 37 38 39 40 41 42 43 44 45 46 47 |
#include <stdio.h> #include <malloc.h> #include <conio.h> //сортировка методом подсчета void methodOfCalculation(int n, int mass[], int sortedMass[]) { int k; for (int i = 0; i < n; i++) { k = 0; for (int j = 0; j < n; j++) { if (mass[i] > mass[j]) k++; } sortedMass[k] = mass[i]; } } int main() { //ввод N int N; printf("Input N: "); scanf_s("%d", &N); //выделение памяти под массивы int *mass, *sortedMass; mass = (int *)malloc(N * sizeof(int)); sortedMass = (int *)malloc(N * sizeof(int)); //ввод элементов массива printf("Input the array elements:\n"); for (int i = 0; i < N; i++) scanf_s("%d", &mass[i]); //сортировка методом подсчета methodOfCalculation(N, mass, sortedMass); //вывод отсортированного массива на экран printf("Sorted array:\n"); for (int i = 0; i < N; i++) printf("%d ", sortedMass[i]); printf("\n"); //освобождение памяти free(mass); free(sortedMass); _getch(); return 0; } |
Демонстрация работы программы приведена на скриншоте:
Если вы хотите скачать исходник этой программы, написанной в Visual Studio, то нажмите на кнопку.
Скачать исходник
Смотрите также:
Сортировка методом выбора на языке Си
Поделиться в соц. сетях: