Файл: «Сортировка данных в массиве. Оценка эффективности метода».pdf

Содержание:

Введение

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

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

Результаты исследования должны сохраняться в текстовом файле.

Исходные данные для исследования задаются с помощью генератора случайных чисел. В исследовании используются массивы с количеством элементов от 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. Форма (рисунок 1), на которой изображен титульный лист, где представлены:
   1. С помощью меток ( Label) необходимые надписи оформления первого титульного листа курсовой работы.
   2. Кнопка (Command Button) для перехода к следующей форме проекта.

1. Титульный лист проекта
2. Форма (рисунок 2),с представлением сортировки массива методом пузырька и простых вставок, на которой расположены:
   1. Графические окна (PictureBox) для вывода исходного и отсортированного массива, гистограммы и графика.
   2. Текстовое окно (TextBox) для вывода пути к массиву.
   3. Кнопки (CommandButton) для поиска массива, вывода, сортировки, построения графика и выхода из формы.
   4. Кнопки (OptionButton) для выбора метода сортировки для построения графика.
   5. Меню для поиска массива, сохранения результата эксперимента, сортировки методами пузырька и простых вставок и выхода из программы.
   6. Элементы – FRAMEs –служат для объединения в группы элементов относящихся к одной логической группе.

1. Главная форма программы
2. Форма (рисунок 3), которая позволяет выбрать нужный файл с массивом. На этой форме расположены:
   1. Окно (DriveListBox) для выбора нужного диска.
   2. Окно (DirListBox) для выбора нужной папки.
   3. Окно (FieleListBox) для выбора текстового файла с массивом.
   4. Текстовое окно (TextBox) для вывода пути к массиву из текстового файла.
   5. Кнопка (CommandButton) копирует путь к массиву из текстового окна и выводит его в текстовое окно главной формы.
   6. Элементы – FRAMEs –служат для объединения в группы элементов относящихся к одной логической группе.

1. Форма поиска массива

Глава 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. Математическая модель

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

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

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

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

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

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

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

1. Если известно, что в исходном массиве минимальный элемент равен – Min, а максимальный – Max, то вспомогательного массив достаточно создавать размером – Max-Min+1.
2. С помощью сортировки подсчетом можно сортировать знаковые типы. Например, при сортировке – 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