Сортировка методом подсчета

Федеральное бюджетное государственное образовательное учреждение

Высшего профессионального образования

Кафедра автоматизированных систем управления

Отчет к лабораторной работе

Сортировка методом подсчета

Руководитель: Бакусова Наталья Сергеевна

Разработал: Давлетов Даниил Альбертович

Уфа, 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 с.