Сортировка методом подсчета
Федеральное бюджетное государственное
образовательное учреждение
Высшего профессионального образования
Кафедра автоматизированных систем
управления
Отчет к лабораторной работе
Сортировка методом подсчета
Руководитель: Бакусова Наталья Сергеевна
Разработал: Давлетов Даниил Альбертович
Уфа, 2015
Содержание
Постановка задачи
Математическая модель
Текст программы
Руководство пользователя
Заключение
Список литературы
Постановка
задачи
Целью работы является изучить методы сортировок. В результате
работы должна быть написана программа, которая сортирует массив данных
различного типа методом подсчета.
Математическая
модель
Сортировка подсчётом - алгоритм сортировки, в котором
используется диапазон чисел сортируемого массива (списка) для подсчёта
совпадающих элементов.
Алгоритм сортировки состоит из следующих шагов:
) Просмотр исходного массива и подсчет количества
элементов в этом массиве (количество сохраняется во вспомогательном массиве);
2) Просмотр вспомогательного массива и запись элементов
в отсортированном порядке.
Идея сортировки заключается в том, что необходимо посчитать
количество элементов в исходном массиве и дальше записать их в отсортированном
порядке посчитанное число раз.
Свойства сортировки:
) Не является сортировкой сравнением: ни одна пара
элементов не сравнивается друг с другом.
2) Требует дополнительную память под массив-счетчик.
Модификации сортировки подсчетом:
) Если известно, что в исходном массиве минимальный
элемент равен - Min, а максимальный - Max, то вспомогательного массив
достаточно создавать размером - Max-Min+1.
2) С помощью сортировки подсчетом можно сортировать
знаковые типы. Например, при сортировке - signed char, принимающего значения от
- 128 до 127, индексу - 0 во вспомогательном массиве будет соответствовать
значение - 128, индексу - 1 - 127, …, индексу 255 - 127.
Алгоритмическая
модель
Текст
программы
#include <stdio. h>
#include <windows. h>
#include <stdlib. h>
#include <iostream>namespace std;Menu
();ForIntegerFromMinToMax ();ForIntegerFromMaxToMin ();ForSymbolsFromMinToMax
();ForSymbolsFromMaxToMin ();Exit ();main () {(1251);(1251);(*f [6]) () =
{Menu, ForIntegerFromMinToMax, ForIntegerFromMaxToMin, ForSymbolsFromMinToMax,
ForSymbolsFromMaxToMin, Exit};
int choice; // переменная для выбора пункта
меню("_____\nМеню. \n1: Текст задачи\n");("2: Сортировка
подсчетом для целых чисел (от меньшего к большему) \n");("3:
Сортировка подсчетом для целых чисел (от большего к меньшему)
\n");("4: Сортировка подсчетом для букв (по алфавиту)
\n");("5: Сортировка подсчетом для букв (в обратном порядке)
\n");("6: Выход\n_____\n");("\nВведите число от 1 до 6
включительно, выбрав пункт меню: ");
for (;;) {(scanf ("%d", &choice)
==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите число от 1 до 6 включительно: ");
fflush (stdin);
}break;
}(;;) {(choice>0 && choice<7) {
(*f [choice-1]) ();
printf ("\nВведите число от 1 до 6 включительно, выбрав
пункт меню: ");
}("\n\n\aТакого пункта меню не существует! \nВведите
число от 1 до 6 включительно, выбрав пункт меню: ");
for (;;) {(scanf ("%d", &choice)
==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите число от 1 до 6 включительно: ");
fflush (stdin);
}break;
}
}0;
void Menu () {("Написать программу сортировки методом
подсчета различных типов данных. \n");("_____\nМеню. \n1: Текст
задачи\n");("2: Сортировка подсчетом для целых чисел (от меньшего к
большему) \n");("3: Сортировка подсчетом для целых чисел (от большего
к меньшему) \n");("4: Сортировка подсчетом для букв (по алфавиту)
\n");("5: Сортировка подсчетом для букв (в обратном порядке)
\n");
printf ("6: Выход\n_____\n");
}ForIntegerFromMinToMax () {i, j, n, a, b;*A,
*C;maxC, minC;
("Введите размер массива: \t");
for (;;) {(scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите размер массива заново: ");(stdin);
}break;
}("Введите левую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите левую границу диапазона сортировки заново: ");(stdin);
}break;
}("Введите правую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}break;
}= (int *) malloc (n*sizeof (int));("Исходный массив:
\t");(i=0; i<n; i++) {[i] =rand () % (b+1-a) +a;("%d\t", A
[i]);
}("\n");=A [0];=A [0];(i=1; i<n;
i++) {(maxC<A [i])=A [i];(minC>A [i])=A [i];
}= (int *) calloc (maxC-minC+1,sizeof
(int));(i=0; i<n; i++) {[A [i] - minC] ++;
}
// Вывод от меньшего к большему
printf ("Результат: \t");(i=0;
i<maxC-minC+1; i++) {(j=0; j<C [i]; j++) {("%d\t", i+minC);
}
}("\n\n");(C);(A);
}ForIntegerFromMaxToMin () {i, j, n, a, b;*A,
*C;maxC, minC;
("Введите размер массива: \t");
for (;;) {(scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите размер массива заново: ");(stdin);
}break;
}("Введите левую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите левую границу диапазона сортировки заново:
");(stdin);
}break;
}("Введите правую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста,
введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}break;
}= (int *) malloc (n*sizeof (int));("Исходный массив:
\t");(i=0; i<n; i++) {[i] =rand () % (b+1-a) +a;("%d\t", A
[i]);
}("\n");=A [0];=A [0];(i=1; i<n;
i++) {(maxC<A [i])=A [i];(minC>A [i])=A [i];
}= (int *) calloc (maxC-minC+1,sizeof
(int));(i=0; i<n; i++) {[A [i] - minC] ++;
}("Результат: \t");
// Вывод в от большего к меньшему
for (i=maxC-minC; i>=0; i--) {(j=0; j<C
[i]; j++) {("%d\t", i+minC);
}
}("\n\n");(C);(A);
}ForSymbolsFromMinToMax () {i, j, n, a,
b;*C;*A;maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {(scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите размер массива заново: ");(stdin);
}break;
}("Введите левую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &a) ==0) { ("\n\n\aОшибка! Неправильный тип
данных. \nПожалуйста, введите левую границу диапазона сортировки заново:
");(stdin);
}break;
}("Введите правую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}break;
}= (char *) malloc (n*sizeof (char));("Исходный массив:
\t");(i=0; i<n; i++) {[i] =rand () % (char (b) +1-char (a)) +char
(a);<< A [i] << "\t";
}("\n");= (int) A [0];= (int) A
[0];(i=1; i<n; i++) {(maxC<A [i])=A [i];(minC>A [i])=A [i];
}= (int *) calloc (maxC-minC+1,sizeof
(int));(i=0; i<n; i++) {[ (int) A [i] - minC] ++;
}("Результат: \t");
// Вывод от меньшего к большему
for (i=0; i<maxC-minC+1; i++) {(j=0; j<C
[i]; j++) {<< char (i+minC) << "\t";
}
}("\n\n");(C);(A);
}ForSymbolsFromMaxToMin () {i, j, n, a,
b;*C;*A;maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {(scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите размер массива заново: ");(stdin);
}break;
for (;;) {(scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных.
\nПожалуйста, введите левую границу диапазона сортировки заново:
");(stdin);
}break;
}("Введите правую границу диапазона сортировки:
\t");
for (;;) {(scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста,
введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}break;
}= (char *) malloc (n*sizeof (char));("Исходный массив:
\t");(i=0; i<n; i++) {[i] =rand () % (char (b) +1-char (a)) +char
(a);<< A [i] << "\t";
}("\n");= (int) A [0];= (int) A
[0];(i=1; i<n; i++) {(maxC<A [i])=A [i];(minC>A [i])=A [i];
}= (int *) calloc (maxC-minC+1,sizeof
(int));(i=0; i<n; i++) {[ (int) A [i] - minC] ++;
}("Результат: \t");
// Вывод в от большего к меньшему
for (i=maxC-minC; i>=0; i--) {(j=0; j<C
[i]; j++) {<< char (i+minC) << "\t";
}
}("\n\n");(C);
free (A);
}Exit () {("\n\nВы ввели 6 для завершения работы.
\n");(0);
}
Руководство
пользователя
1) Запустите приложение "SORTCPP”.
2) Выберите нужный пункт меню.
Рисунок 1 - экранная форма
) Далее следуя подсказкам вводите данные.
Рисунок 2 - экранная форма
) После того, как будет введено количество элементов и
границы сортируемого диапазона, на экран выведется исходный массив (он
заполняется случайным образом).
Рисунок 3 - экранная форма
) После этого программа проделает вычисления и выведет
отсортированный массив.
Рисунок 4 - экранная форма
) После этого программа предложит выбрать пункт меню
еще раз.
Заключение
В ходе работы был изучен метод сортировки подсчетом, которая
имеет свои особенности.
Во-первых, применение сортировки подсчётом целесообразно лишь
тогда, когда сортируемые числа имеют диапазон возможных значений, который
достаточно мал по сравнению с сортируемым множеством. Эффективность алгоритма
падает, если при попадании нескольких различных элементов в одну ячейку, их
надо дополнительно сортировать.
Во-вторых, сортировка подсчетом не годится для вещественного
типа исходных данных, так как размер дополнительного массива-счетчика равен
максимальному элементу исходного массива, а это может быть только натуральное
число.
сортировка подсчет алгоритм массив
Список
литературы
1) Кнут
Д.Э. Искусство программирования. - Вильямс, 2001. - 800 с.
2) Кормен
Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е
издание. - М.: Вильямс, 2010. - 1296 с.
) Гасфилд
Д. Строки, деревья и последовательности в алгоритмах. - БХВ - Петербург, 2003.
- 654 с.