«Сортировка данных в массиве. Оценка эффективности метода»
Содержание:
Введение
Целью работы является создание программы для исследования сортировки массивов методами пузырька и простых вставок. В ходе исследования должны быть построены графики, показывающие время сортировки массивов в зависимости от количества элементов в массиве для обоих методов.
Второй целью работы является изучить методы сортировок. В результате работы должна быть написана программа, которая сортирует массив данных различного типа методом подсчета.
Результаты исследования должны сохраняться в текстовом файле.
Исходные данные для исследования задаются с помощью генератора случайных чисел. В исследовании используются массивы с количеством элементов от 500 до 5000 с шагом 50. Так же должна быть выполнена визуализация методов сортировки. Исходный массив для визуализации должен иметь 10 элементов, инициализация его должна быть выполнена с помощью генератора случайных чисел. Для визуализации метода сортировки должна использоваться гистограмма и таблица. Признак сортировки по убыванию.
Объект исследования – Сортировка данных в массиве.
Предмет исследования - Оценка эффективности метода.
Глава 1.Описание методов сортировки массива
1.1 Метод пузырька
Последовательно просматриваем числа a0 , ..., an-1 находим наибольшее i такое, что ai < ai+1 . Поменять ai и ai+1 местами, возобновить просмотр с элемента ai+1 и т.д. Тем самым наименьшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.
Блок – схема метода пузырька
1.2 Метод простых вставок
Сортировка массива методом простой вставки состоит в следующем. Последовательно просматриваются элементы массива a1 , ..., an-1 и каждый новый элемент ai вставляется на подходящее место в уже упорядоченную совокупность элементов a0 , ..., ai-1. Это место определяется последовательным сравнением элемента ai с упорядоченными элементами a0 , ..., ai-1.
Блок – схема метода простой вставки
Глава 2. Описание решения задачи
Для реализации проекта создано три формы:
- Форма (рисунок 1), на которой изображен титульный лист, где представлены:
- С помощью меток ( Label) необходимые надписи оформления первого титульного листа курсовой работы.
- Кнопка (Command Button) для перехода к следующей форме проекта.
- Титульный лист проекта
- Форма (рисунок 2),с представлением сортировки массива методом пузырька и простых вставок, на которой расположены:
- Графические окна (PictureBox) для вывода исходного и отсортированного массива, гистограммы и графика.
- Текстовое окно (TextBox) для вывода пути к массиву.
- Кнопки (CommandButton) для поиска массива, вывода, сортировки, построения графика и выхода из формы.
- Кнопки (OptionButton) для выбора метода сортировки для построения графика.
- Меню для поиска массива, сохранения результата эксперимента, сортировки методами пузырька и простых вставок и выхода из программы.
- Элементы – FRAMEs –служат для объединения в группы элементов относящихся к одной логической группе.
- Главная форма программы
- Форма (рисунок 3), которая позволяет выбрать нужный файл с массивом. На этой форме расположены:
- Окно (DriveListBox) для выбора нужного диска.
- Окно (DirListBox) для выбора нужной папки.
- Окно (FieleListBox) для выбора текстового файла с массивом.
- Текстовое окно (TextBox) для вывода пути к массиву из текстового файла.
- Кнопка (CommandButton) копирует путь к массиву из текстового окна и выводит его в текстовое окно главной формы.
- Элементы – FRAMEs –служат для объединения в группы элементов относящихся к одной логической группе.
- Форма поиска массива
Глава 3. Фрагмент программного кода
3.1 Метод пузырька
В фрагменте программного кода, представленного ниже, идет сортировка массива методом пузырька. Условием выполнения цикла является W(I)<W(J) (где W(I) – массив, состоящий из 10 элементов). Пока выполняется данное условие, элементы массива последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Если условие не выполняется, значит массив отсортирован.
3.2 Метод простых вставок
В фрагменте программного кода, представленного ниже, идет сортировка массива методом простых вставок.
При сортировке исходный массив разбивается на две части:
W[1], W[2], ..., W[I-1] - отсортированную часть
W[I], ...,W[n] - не отсортированную часть
На I - м шаге элемент W[I] включается в отсортированную часть, на соответствующее место. При этом часть элементов, меньших W[I], (если таковые есть) сдвигаются на одну позицию правее, чтобы освободить место для элемента W[I]. Прежде чем производить сдвиг элементов необходимо сохранить значение W[I] во временной переменной B. Сортировка завершается если набор входных данных исчерпан.
Глава 4. Программные коды
Форма 1
Private Sub Command1_Click()
Form3.Show
Form1.Hide
End Sub
Форма 2
Dim pathSearch As String
Dim diskName As String
Private Sub Dir1_change()
File1.Path = Dir1.Path
End Sub
Private Sub Drive1_Change()
diskName = Drive1.Drive
Dir1.Path = diskName & "\"
File1.Path = Dir1.Path
End Sub
Private Sub File1_Click()
If Right(File1.Path, 1) = "\" Then
Text1.Text = File1.Path & File1.FileName
Else
Text1.Text = File1.Path & "\" & File1.FileName
End If
ptu = Text1
End Sub
Private Sub Form_Load()
pathSearch = App.Path
Drive1.Drive = pathSearch
Dir1.Path = pathSearch
File1.FileName = pathSearch
End Sub
Private Sub Command1_Click()
Form3.Text1.Text = ptu
Form2.Hide
Form3.Show
End Sub
Форма 3
Dim X(100) As String
Dim w(100) As Integer
Dim o As Long
Private am(0 To 5000), qm(0 To 1000), mm(0 To 5000) As Double
Private t As Boolean
Dim FPIName As String
Private Sub Command2_Click()
End
End Sub
Private Sub Command1_Click()
Picture1.Cls
Picture2.Cls
Picture3.Cls
Picture3.ScaleWidth = 220
Picture3.ScaleHeight = 190
p = 1
j = 0
a = Text1
If Text1 <> "" Then
Open a For Input As 1
Do While Not (EOF(1))
Input #1, m
For i = 1 To Len(m)
Y = Mid(m, i, 1)
If Y = " " Then
j = j + 1
X(j) = Mid(m, p, i - p)
p = i + 1
End If
Next i
j = j + 1
X(j) = Mid(m, p, Len(m))
For i = 1 To j
Picture1.Print X(i)
Next i
Loop
Close #1
For i = 1 To j
w(i) = CInt(X(i))
Next i
For o = 1 To 10
Picture3.Line (0, 0 + 15 * o)-(w(o), 10 + 15 * o), RGB(w(o) + 255, w(o), w(o)), B
Next
Else
pushbutton = MsgBox("Некорректно указан путь к файлу!!! Проверьте правильность пути!", 16, "Ошибка!!!")
End If
End Sub
Private Sub Command3_Click()
If X(1) <> "" Then
Picture2.Cls
Picture3.Cls
If Option1.Value Then
For i = 1 To 10
For j = i + 1 To 10 Step 1
If w(i) < w(j) Then
k = w(i)
w(i) = w(j)
w(j) = k
End If
Next j
Next i
End If
If Option2.Value Then
For i = 2 To 10
B = w(i)
j = 1
Do While B < w(j)
j = j + 1
Loop
For k = i To j + 1 Step -1
w(k) = w(k - 1)
Next k
w(j) = B
Next i
End If
For i = 1 To 10
Picture2.Print w(i)
Next i
For o = 1 To 10
Picture3.Line (0, 0 + 15 * o)-(w(o), 10 + 15 * o), RGB(w(o) + 255, w(o), w(o)), B
Next
For i = 1 To 10
ren = ren + CStr(w(i)) + " "
Next i
Else
pushbutton = MsgBox("Выберите массив!", 16, "Ошибка!!!...")
End If
End Sub
Private Sub Command5_Click()
If ptu = "" Then
pushbutton = MsgBox("Для правильного отображения массива программой, файл, содержащий массив, должен иметь расширение *.txt, в конце и в начале данного массива должны стоять ковычки (в противном случае, программа не будет считывать пробелы).", 64, "Информация...")
End If
Form2.Show
End Sub
Private Sub Command6_Click()
Dim ss As String
If FPIName = "" Then
MsgBox Prompt:="Не указано имя файла для сохранения результата.Для этого во вкладке файл веберите пункт (Файл сохранения результата) ", _
Title:="Исследование"
Exit Sub
End If
s = 0
If Option4.Value Then
f = FreeFile
Open FPIName For Append As #f
Print #f, vbCrLf & "Метод простых вставок"
x0 = 360
y0 = 5280
Picture4.PSet (x0, y0)
h = 1
For r = 500 To 5000 Step 50
For e = 0 To r - 1
am(e) = mm(e)
Next
s = Timer
For Y = 2 To r - 1
Xm = am(Y)
j = Y - 1
Do While Xm < am(j)
j = j - 1
Loop
For k = Y To j + 1 Step -1
am(k) = am(k - 1)
Next k
am(j) = Xm
Next Y
qm(h) = Timer - s
ss = r & " - " & Format(Abs(Timer - s), "0.000 000")
Picture4.Line -(x0 + r, y0 - qm(h) * 2000), RGB(255, 0, 0)
h = h + 1
' Print #f, r, " - ", qm(h)
Print #f, ss
Next r
Close #f
End If
s = 0
If Option3.Value Then
f = FreeFile
Open FPIName For Append As #f
Print #f, "Метод пузырька"
x0 = 360
yo = 5280
Picture4.PSet (x0, yo)
h = 1
For r = 500 To 5000 Step 50
For e = 1 To r - 1
am(e) = mm(e)
Next e
s = Timer
For i = 1 To r - 1
For j = i + 1 To r - 1 Step 1
If am(i) < am(j) Then
k = am(i)
am(i) = am(j)
am(j) = k
End If
Next j
Next i
qm(h) = Timer - s
ss = r & " - " & Format(Abs(Timer - s), "0.000 000")
Y1 = yo - qm(h) * 2000
Picture4.Line -(x0 + r, Y1), RGB(0, 0, 255)
h = h + 1
' Print #f, r, " - ", qm(h)
Print #f, ss
Next r
Close #f
End If
End Sub
Private Sub Form_Load()
FPIName = ""
Form1.Width = 5130
Form1.Height = 7740
Picture1.BackColor = QBColor(10)
Picture3.BackColor = QBColor(15)
Randomize
For i = 1 To 5000
mm(i) = Int(Rnd * 99)
Next
End Sub
Private Sub FPIMnu_Click()
CommonDialog1.InitDir = App.Path
CommonDialog1.FileName = ""
CommonDialog1.Filter = "Текстовые файлы(*.txt)|*.txt|Все файлы(*.*)|*.*"
CommonDialog1.Flags = CommonDialog1.Flags Or 4
CommonDialog1.ShowSave
If CommonDialog1.FileName = "" Then
FPIName = ""
Exit Sub
End If
FPIName = CommonDialog1.FileName
CommonDialog1.FileName = ""
End Sub
Private Sub Open_Click()
Command5 = True
End Sub
Private Sub Exit_Click()
Command2 = True
End Sub
Private Sub Puz_Click()
If X(1) <> "" Then
Picture2.Cls
Picture3.Cls
For i = 1 To 10
For j = 10 To i + 1 Step -1
If w(i) < w(j) Then
k = w(i)
w(i) = w(j)
w(j) = k
End If
Next j
Next i
For i = 1 To 10
Picture2.Print w(i)
Next i
For o = 1 To 10
Picture3.Line (0, 0 + 15 * o)-(w(o), 10 + 15 * o), RGB(w(o) + 255, w(o), w(o)), B
Next
Else
pushbutton = MsgBox("Выберите массив!", 16, "Ошибка!!!...")
End If
End Sub
Private Sub Vstavok_Click()
If X(1) <> "" Then
Picture2.Cls
Picture3.Cls
For i = 2 To 10
B = w(i)
j = 1
Do While B < w(j)
j = j + 1
Loop
For k = i To j + 1 Step -1
w(k) = w(k - 1)
Next k
w(j) = B
Next i
For i = 1 To 10
Picture2.Print w(i)
Next i
For o = 1 To 10
Picture3.Line (0, 0 + 15 * o)-(w(o), 10 + 15 * o), RGB(w(o) + 255, w(o), w(o)), B
Next
Else
pushbutton = MsgBox("Выберите массив!", 16, "Ошибка!!!...")
End If
End Sub
Глава 5. Математическая модель
Сортировка подсчётом – алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.
Алгоритм сортировки состоит из следующих шагов:
- Просмотр исходного массива и подсчет количества элементов в этом массиве (количество сохраняется во вспомогательном массиве);
- Просмотр вспомогательного массива и запись элементов в отсортированном порядке.
Идея сортировки заключается в том, что необходимо посчитать количество элементов в исходном массиве и дальше записать их в отсортированном порядке посчитанное число раз.
Свойства сортировки:
- Не является сортировкой сравнением: ни одна пара элементов не сравнивается друг с другом.
- Требует дополнительную память под массив-счетчик.
Модификации сортировки подсчетом:
- Если известно, что в исходном массиве минимальный элемент равен – Min, а максимальный – Max, то вспомогательного массив достаточно создавать размером – Max-Min+1.
- С помощью сортировки подсчетом можно сортировать знаковые типы. Например, при сортировке – signed char, принимающего значения от -128 до 127, индексу – 0 во вспомогательном массиве будет соответствовать значение – 128, индексу – 1 – 127, …, индексу 255 – 127.
НАЧАЛО
Ввод
*f[6](),
choice
FOR
, ;
scanf("%d", &c)==0
Вывод
“Ошибка”
fflush(stdin);
FOR
A
break
void (*f[6]) () = {Menu, ForIntegerFromMinToMax, ForIntegerFromMaxToMin, ForSymbolsFromMinToMax, ForSymbolsFromMaxToMin, Exit};
схема алгоритма основной процедуры
FOR
, ;
c>0 и c<7
(*f[choice-1])();
Вывод
“Ошибка”
FOR
, ;
scanf("%d", &c)==0
Вывод
“Ошибка”
fflush(stdin);
продолжение схемы алгоритма основной процедуры
A
B
break
FOR
FOR
КОНЕЦ
НАЧАЛО
Ввод
“Меню”
КОНЕЦ
Текст задачи.
Сортировка подсчетом для целых чисел (от меньшего к большему).
Сортировка подсчетом для целых чисел (от большего к меньшему).
Сортировка подсчетом для букв (по алфавиту).
Сортировка подсчетом для букв (в обратном порядке).
Выход.
схема алгоритма процедуры Menu
B
продолжение схемы алгоритма основной процедуры
НАЧАЛО
Ввод
i, j, n, a, b, *A, *C, maxC, minC
FOR
, ;
scanf("%d", &n)==0
Вывод
“Ошибка”
fflush(stdin)
FOR
break
схема алгоритма процедуры ForIntegerFromMinToMax
C
FOR
, ;
scanf("%d", &a)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
, ;
scanf("%d", &b)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
FOR
продолжение схемы алгоритма процедуры ForIntegerFromMinToMax
C
D
D
F
A=(int *)malloc(n*sizeof(int));
FOR
0, n; 1
A[i]=rand()%(b+1-a)+a;
Вывод
A[i]
FOR
maxC=A[0];
minC=A[0];
maxC<A[i]
maxC=A[i];
FOR
0, n; 1
minC>A[i]
minC=A[i];
FOR
Рпродолжение схемы алгоритма процедуры ForIntegerFromMinToMax
F
G
G
H
C=(int *)calloc(maxC-minC+1,sizeof(int));
FOR
0, n; 1
C[A[i]-minC]++;
FOR
FOR
0, maxC-minC+1; 1
FOR
0, C[i]; 1
Вывод
i+minC
FOR
FOR
free(C);
free(A);
КОНЕЦ
продолжение схемы алгоритма процедуры ForIntegerFromMinToMax
H
I
I
НАЧАЛО
Ввод
i, j, n, a, b, *A, *C, maxC, minC
FOR
, ;
scanf("%d", &n)==0
Вывод
“Ошибка”
fflush(stdin)
FOR
break
схема алгоритма процедуры ForIntegerFromMaxToMin
J
FOR
, ;
scanf("%d", &a)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
, ;
scanf("%d", &b)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
FOR
продолжение схемы алгоритма процедуры ForIntegerFromMaxToMin
J
K
K
L
A=(int *)malloc(n*sizeof(int));
FOR
0, n; 1
A[i]=rand()%(b+1-a)+a;
Вывод
A[i]
FOR
maxC=A[0];
minC=A[0];
maxC<A[i]
maxC=A[i];
FOR
0, n; 1
minC>A[i]
minC=A[i];
FOR
продолжение схемы алгоритма процедуры ForIntegerFromMaxToMin
L
M
M
N
C=(int *)calloc(maxC-minC+1,sizeof(int));
FOR
0, n; 1
C[A[i]-minC]++;
FOR
FOR
maxC-minC, 0; 1
FOR
0, C[i]; 1
Вывод
i+minC
FOR
FOR
free(C);
free(A);
КОНЕЦ
продолжение схемы алгоритма процедуры ForIntegerFromMaxToMin
N
O
O
НАЧАЛО
Ввод
i, j, n, a, b, *A, *C, maxC, minC
FOR
, ;
scanf("%d", &n)==0
Вывод
“Ошибка”
fflush(stdin)
FOR
break
схема алгоритма процедуры ForSymbolsFromMinToMax
P
FOR
, ;
scanf("%d", &a)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
, ;
scanf("%d", &b)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
FOR
продолжение схемы алгоритма процедуры ForSymbolsFromMinToMax
P
Q
Q
R
A=(char *)malloc(n*sizeof(char));
FOR
0, n; 1
A[i]=rand()%(char(b)+1-char(a))+char(a);
Вывод
A[i]
FOR
maxC=(int)A[0];
minC=(int)A[0];
maxC<A[i]
maxC=A[i];
FOR
0, n; 1
minC>A[i]
minC=A[i];
FOR
продолжение схемы алгоритма процедуры ForSymbolsFromMinToMax
R
S
S
T
C=(int *)calloc(maxC-minC+1,sizeof(int));
FOR
0, n; 1
C[(int)A[i]-minC]++;
FOR
FOR
0, maxC-minC+1; 1
FOR
0, C[i]; 1
Вывод
char(i+minC)
FOR
FOR
free(C);
free(A);
КОНЕЦ
продолжение схемы алгоритма процедуры ForSymbolsFromMinToMax
T
U
U
НАЧАЛО
Ввод
i, j, n, a, b, *A, *C, maxC, minC
FOR
, ;
scanf("%d", &n)==0
Вывод
“Ошибка”
fflush(stdin)
FOR
break
схема алгоритма процедуры ForSymbolsFromMaxToMin
V
FOR
, ;
scanf("%d", &a)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
, ;
scanf("%d", &b)==0
Вывод
“Ошибка”
fflush(stdin)
break
FOR
FOR
продолжение схемы алгоритма процедуры ForSymbolsFromMaxToMin
V
W
W
X
A=(char *)malloc(n*sizeof(char));
FOR
0, n; 1
A[i]=rand()%(char(b)+1-char(a))+char(a);
Вывод
A[i]
FOR
maxC=(int)A[0];
minC=(int)A[0];
maxC<A[i]
maxC=A[i];
FOR
0, n; 1
minC>A[i]
minC=A[i];
FOR
продолжение схемы алгоритма процедуры ForSymbolsFromMaxToMin
X
Y
Y
Z
C=(int *)calloc(maxC-minC+1,sizeof(int));
FOR
0, n; 1
C[(int)A[i]-minC]++;
FOR
FOR
maxC-minC, 0; 1
FOR
0, C[i]; 1
Вывод
char(i+minC)
FOR
FOR
free(C);
free(A);
КОНЕЦ
продолжение схемы алгоритма процедуры ForSymbolsFromMaxToMin
Z
1
1
НАЧАЛО
КОНЕЦ
exit(0);
схема алгоритма процедуры exit
#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);
}
Заключение
Использование правильно подобранных алгоритмов в современной разработке программного обеспечения жизненно важно для проекта, так как ошибочный выбор алгоритма для тривиальной, на первый взгляд, задачи может прямо сказаться на скорости выполнения реализованной функциональности. На текущей момент разработано множество библиотек, включающих в себя множество реализованных эффективных алгоритмов, которые могут быть использованы любым разработчиком программного обеспечения для достижения сравнительно высоких показателей скорости выполнения программы. Практика показывает, что зачастую разработчик полностью доверяется встроенным средствам и не анализирует в достаточной степени ситуацию, в которой будет применен выбранный алгоритм.
В ходе работы был изучен метод сортировки подсчетом, которая имеет свои особенности.
Во-первых, применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать.
Во-вторых, сортировка подсчетом не годится для вещественного типа исходных данных, так как размер дополнительного массива-счетчика равен максимальному элементу исходного массива, а это может быть только натуральное число.
Список литературы
- ГОСТ 19.701-90 Схемы алгоритмов программ, данных и систем. М., 1992. 22 с.
- ГОСТ 2.105-95. Общие требования к текстовым документам. М., 1996. 31 с.
- Форум программистов и сисадминов CyberForum.ru http://www.cyberforum.ru/visual-basic/thread141819.html
- Интерактивный учебник по Visual Basic http://msdn.microsoft.com/ru-ru/library/2x7h1hfk(v=vs.90).aspx
- Пособие-самоучитель on-line «Visual Basic с нуля» http://vbzero.narod.ru/page_7.htm
- Система дистанционной поддержки учебного процесса кафедры информатики. URL: http://informatic.ugatu.ac.ru/kafedra/index.php.
- Дональд Эрвин Кнут, Искусство программирования. Том 1. Основные алгоритмы. — СПб.: Вильямс, 2015. — 720 с. 2. Роберт Седжвик, Кевин Уэйн, Алгоритмы на Java. — СПб.: Вильямс, 2016. — 848 с. 3. Томас Х. Кормен, Чарльз И. Лейзерсон, Алгоритмы. Построение и анализ. — СПб.: Вильямс, 2016. — 1328 с.
- Рыжов С. С. Анализ эффективности алгоритмов сортировки и вcтроенных реализаций на примере языка программирования Java // Молодой ученый. — 2017. — №21. — С. 26-29. — URL https://moluch.ru/archive/155/43911/ (дата обращения: 12.09.2019).
- Организационная культура в менеджменте и её влияние на деятельность компании
- Информационное и коммуникационное обеспечение управления маркетингом (теоретические аспекты) (Теоретические аспекты информационного и коммуникационного обеспечения управления маркетингом)
- Аббревиатуры в современном английском языке (Теоретические проблемы изучения аббревиаций и сокращений как объект лингвистического исследования )
- Аббревиатуры в современном английском языке (Теоретические проблемы изучения аббревиаций и сокращений как объект лингвистического исследования)
- Проблема переводимости (Особенности оценки качества перевода и переводческая норма)
- Понятие средств в ОРД и их нормативная фиксация
- Жизненный цикл организации и управление организацией (понятие и этапы цикла организации)
- Правовые основы оперативно-розыскной деятельности. Структура ФЗ об ОРД
- Роль кадровой службы в формировании и реализации кадровой стратегии (Кадровое направление и его роль в деятельности организации)
- Особенности политики мотивации персонала малых предприятий
- Технология «Клиент-сервис»
- Разработка регламента выполнения процесса «Управление документооборотом»