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

ФЕДЕРАЛЬНОЕ БЮДЖЕТНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО       КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ           СОРТИРОВКА ПОДСЧЕТОМ     Отчет к лабораторной работе           Руководитель: Бакусова Наталья Сергеевна Разработал: Давлетов Даниил Альбертович Группа: ПИЭ-111 № зачетной книжки: 133006               Уфа, 2015

 

Содержание

 

 

 

1. Постановка задачи

Целью работы является изучить методы сортировок. В результате работы должна быть написана программа, которая сортирует массив данных различного типа методом подсчета.

 

2. Математическая модель

Сортировка подсчётом – алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Алгоритм сортировки состоит из следующих шагов:

1. Просмотр исходного массива и подсчет количества элементов в этом массиве (количество сохраняется во вспомогательном массиве);
2. Просмотр вспомогательного массива и запись элементов в отсортированном порядке.

Идея сортировки заключается в том, что необходимо посчитать количество элементов в исходном массиве и дальше записать их в отсортированном порядке посчитанное число раз.

Свойства сортировки:

1. Не является сортировкой сравнением: ни одна пара элементов не сравнивается друг с другом.
2. Требует дополнительную память под массив-счетчик.

Модификации сортировки подсчетом:

1. Если известно, что в исходном массиве минимальный элемент равен – Min, а максимальный – Max, то вспомогательного массив достаточно создавать размером – Max-Min+1.
2. С помощью сортировки подсчетом можно сортировать знаковые типы. Например, при сортировке – signed char, принимающего значения от -128 до 127, индексу – 0 во вспомогательном массиве будет соответствовать значение – 128, индексу – 1 – 127, …, индексу 255 – 127.
 

3. Алгоритмическая модель

 

4. Текст программы

#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);