Сортировка методом подсчета
Разработка программы, сортирующей массивы данных различного типа методом подсчета. Основные шаги алгоритма сортировки, ее свойства и модификация подсчетом. Целесообразность применения сортировки подсчетом. Условия эффективности алгоритма сортировки.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 16.07.2015 |
| Размер файла | 438,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное бюджетное государственное образовательное учреждение
Высшего профессионального образования
Кафедра автоматизированных систем управления
Отчет к лабораторной работе
Сортировка методом подсчета
Руководитель: Бакусова Наталья Сергеевна
Разработал: Давлетов Даниил Альбертович
Уфа, 2015
Содержание
- Постановка задачи
- Математическая модель
- Текст программы
- Руководство пользователя
- Заключение
- Список литературы
Постановка задачи
Целью работы является изучить методы сортировок. В результате работы должна быть написана программа, которая сортирует массив данных различного типа методом подсчета.
Математическая модель
Сортировка подсчётом - алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.
Алгоритм сортировки состоит из следующих шагов:
1) Просмотр исходного массива и подсчет количества элементов в этом массиве (количество сохраняется во вспомогательном массиве);
2) Просмотр вспомогательного массива и запись элементов в отсортированном порядке.
Идея сортировки заключается в том, что необходимо посчитать количество элементов в исходном массиве и дальше записать их в отсортированном порядке посчитанное число раз.
Свойства сортировки:
1) Не является сортировкой сравнением: ни одна пара элементов не сравнивается друг с другом.
2) Требует дополнительную память под массив-счетчик.
Модификации сортировки подсчетом:
1) Если известно, что в исходном массиве минимальный элемент равен - Min, а максимальный - Max, то вспомогательного массив достаточно создавать размером - Max-Min+1.
2) С помощью сортировки подсчетом можно сортировать знаковые типы. Например, при сортировке - signed char, принимающего значения от - 128 до 127, индексу - 0 во вспомогательном массиве будет соответствовать значение - 128, индексу - 1 - 127, …, индексу 255 - 127.
Алгоритмическая модель
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Текст программы
#include <stdio. h>
#include <windows. h>
#include <stdlib. h>
#include <iostream>
using namespace std;
void Menu ();
void ForIntegerFromMinToMax ();
void ForIntegerFromMaxToMin ();
void ForSymbolsFromMinToMax ();
void ForSymbolsFromMaxToMin ();
void Exit ();
int main () {
SetConsoleCP (1251);
SetConsoleOutputCP (1251);
void (*f [6]) () = {Menu, ForIntegerFromMinToMax, ForIntegerFromMaxToMin, ForSymbolsFromMinToMax, ForSymbolsFromMaxToMin, Exit};
int choice; // переменная для выбора пункта меню
printf ("_____\nМеню. \n1: Текст задачи\n");
printf ("2: Сортировка подсчетом для целых чисел (от меньшего к большему) \n");
printf ("3: Сортировка подсчетом для целых чисел (от большего к меньшему) \n");
printf ("4: Сортировка подсчетом для букв (по алфавиту) \n");
printf ("5: Сортировка подсчетом для букв (в обратном порядке) \n");
printf ("6: Выход\n_____\n");
printf ("\nВведите число от 1 до 6 включительно, выбрав пункт меню: ");
for (;;) {
if (scanf ("%d", &choice) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите число от 1 до 6 включительно: ");
fflush (stdin);
}
else break;
}
for (;;) {
if (choice>0 && choice<7) {
(*f [choice-1]) ();
printf ("\nВведите число от 1 до 6 включительно, выбрав пункт меню: ");
}
else
printf ("\n\n\aТакого пункта меню не существует! \nВведите число от 1 до 6 включительно, выбрав пункт меню: ");
for (;;) {
if (scanf ("%d", &choice) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите число от 1 до 6 включительно: ");
fflush (stdin);
}
else break;
}
}
return 0;
}
void Menu () {
printf ("Написать программу сортировки методом подсчета различных типов данных. \n");
printf ("_____\nМеню. \n1: Текст задачи\n");
printf ("2: Сортировка подсчетом для целых чисел (от меньшего к большему) \n");
printf ("3: Сортировка подсчетом для целых чисел (от большего к меньшему) \n");
printf ("4: Сортировка подсчетом для букв (по алфавиту) \n");
printf ("5: Сортировка подсчетом для букв (в обратном порядке) \n");
printf ("6: Выход\n_____\n");
}
void ForIntegerFromMinToMax () {
int i, j, n, a, b;
int *A, *C;
int maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {
if (scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите размер массива заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите левую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите левую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите правую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
A= (int *) malloc (n*sizeof (int));
printf ("Исходный массив: \t");
for (i=0; i<n; i++) {
A [i] =rand () % (b+1-a) +a;
printf ("%d\t", A [i]);
}
printf ("\n");
maxC=A [0];
minC=A [0];
for (i=1; i<n; i++) {
if (maxC<A [i])
maxC=A [i];
if (minC>A [i])
minC=A [i];
}
C= (int *) calloc (maxC-minC+1,sizeof (int));
for (i=0; i<n; i++) {
C [A [i] - minC] ++;
}
// Вывод от меньшего к большему
printf ("Результат: \t");
for (i=0; i<maxC-minC+1; i++) {
for (j=0; j<C [i]; j++) {
printf ("%d\t", i+minC);
}
}
printf ("\n\n");
free (C);
free (A);
}
void ForIntegerFromMaxToMin () {
int i, j, n, a, b;
int *A, *C;
int maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {
if (scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите размер массива заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите левую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите левую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите правую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
A= (int *) malloc (n*sizeof (int));
printf ("Исходный массив: \t");
for (i=0; i<n; i++) {
A [i] =rand () % (b+1-a) +a;
printf ("%d\t", A [i]);
}
printf ("\n");
maxC=A [0];
minC=A [0];
for (i=1; i<n; i++) {
if (maxC<A [i])
maxC=A [i];
if (minC>A [i])
minC=A [i];
}
C= (int *) calloc (maxC-minC+1,sizeof (int));
for (i=0; i<n; i++) {
C [A [i] - minC] ++;
}
printf ("Результат: \t");
// Вывод в от большего к меньшему
for (i=maxC-minC; i>=0; i--) {
for (j=0; j<C [i]; j++) {
printf ("%d\t", i+minC);
}
}
printf ("\n\n");
free (C);
free (A);
}
void ForSymbolsFromMinToMax () {
int i, j, n, a, b;
int *C;
char *A;
int maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {
if (scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите размер массива заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите левую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите левую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите правую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
A= (char *) malloc (n*sizeof (char));
printf ("Исходный массив: \t");
for (i=0; i<n; i++) {
A [i] =rand () % (char (b) +1-char (a)) +char (a);
cout << A [i] << "\t";
}
printf ("\n");
maxC= (int) A [0];
minC= (int) A [0];
for (i=1; i<n; i++) {
if (maxC<A [i])
maxC=A [i];
if (minC>A [i])
minC=A [i];
}
C= (int *) calloc (maxC-minC+1,sizeof (int));
for (i=0; i<n; i++) {
C [ (int) A [i] - minC] ++;
}
printf ("Результат: \t");
// Вывод от меньшего к большему
for (i=0; i<maxC-minC+1; i++) {
for (j=0; j<C [i]; j++) {
cout << char (i+minC) << "\t";
}
}
printf ("\n\n");
free (C);
free (A);
}
void ForSymbolsFromMaxToMin () {
int i, j, n, a, b;
int *C;
char *A;
int maxC, minC;
printf ("Введите размер массива: \t");
for (;;) {
if (scanf ("%d", &n) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите размер массива заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите левую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &a) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите левую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
printf ("Введите правую границу диапазона сортировки: \t");
for (;;) {
if (scanf ("%d", &b) ==0) {
printf ("\n\n\aОшибка! Неправильный тип данных. \nПожалуйста, введите правую границу диапазона сортировки заново: ");
fflush (stdin);
}
else break;
}
A= (char *) malloc (n*sizeof (char));
printf ("Исходный массив: \t");
for (i=0; i<n; i++) {
A [i] =rand () % (char (b) +1-char (a)) +char (a);
cout << A [i] << "\t";
}
printf ("\n");
maxC= (int) A [0];
minC= (int) A [0];
for (i=1; i<n; i++) {
if (maxC<A [i])
maxC=A [i];
if (minC>A [i])
minC=A [i];
}
C= (int *) calloc (maxC-minC+1,sizeof (int));
for (i=0; i<n; i++) {
C [ (int) A [i] - minC] ++;
}
printf ("Результат: \t");
// Вывод в от большего к меньшему
for (i=maxC-minC; i>=0; i--) {
for (j=0; j<C [i]; j++) {
cout << char (i+minC) << "\t";
}
}
printf ("\n\n");
free (C);
free (A);
}
void Exit () {
printf ("\n\nВы ввели 6 для завершения работы. \n");
exit (0);
}
Руководство пользователя
1) Запустите приложение "SORTCPP”.
2) Выберите нужный пункт меню.
Рисунок 1 - экранная форма
3) Далее следуя подсказкам вводите данные.
Рисунок 2 - экранная форма
4) После того, как будет введено количество элементов и границы сортируемого диапазона, на экран выведется исходный массив (он заполняется случайным образом).
Рисунок 3 - экранная форма
5) После этого программа проделает вычисления и выведет отсортированный массив.
Рисунок 4 - экранная форма
6) После этого программа предложит выбрать пункт меню еще раз.
Заключение
В ходе работы был изучен метод сортировки подсчетом, которая имеет свои особенности.
Во-первых, применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать.
Во-вторых, сортировка подсчетом не годится для вещественного типа исходных данных, так как размер дополнительного массива-счетчика равен максимальному элементу исходного массива, а это может быть только натуральное число.
сортировка подсчет алгоритм массив
Список литературы
1) Кнут Д.Э. Искусство программирования. - Вильямс, 2001. - 800 с.
2) Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е издание. - М.: Вильямс, 2010. - 1296 с.
3) Гасфилд Д. Строки, деревья и последовательности в алгоритмах. - БХВ - Петербург, 2003. - 654 с.
Размещено на Allbest.ru
Подобные документы
Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Сортировка как процесс расстановки элементов "в некотором порядке", ее структура и основные компоненты, характеристика методов. Порядок выбора того или иного метода сортировки: линейный с обменом и подсчетом, методом Шелла, с отложенными обменами.
реферат [27,1 K], добавлен 13.09.2009Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.
реферат [189,8 K], добавлен 06.12.2014Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.
курсовая работа [637,6 K], добавлен 29.11.2014Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.
курсовая работа [203,8 K], добавлен 03.12.2010Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.
реферат [20,7 K], добавлен 20.05.2010Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне.
контрольная работа [32,8 K], добавлен 20.01.2012Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.
курсовая работа [23,1 K], добавлен 24.05.2015
