Исследование методов сортировки массивов

Размещено на http://www.allbest.ru

ГОУ ВПО

Уфимский государственный авиационный технический университет

Кафедра Информатики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

«Исследование методов сортировки массивов»

Уфа 2014 г.



Введение

Целью работы является создание программы для исследования сортировки массивов методами пузырька и простых вставок. В ходе исследования должны быть построены графики, показывающие время сортировки массивов в зависимости от количества элементов в массиве для обоих методов. Результаты исследования должны сохраняться в текстовом файле. Исходные данные для исследования задаются с помощью генератора случайных чисел. В исследовании используются массивы с количеством элементов от 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.

Блок-схема метода простой вставки

Описание решения задачи

Для реализации проекта создано три формы:

Форма (рисунок 1), на которой изображен титульный лист, где представлены. С помощью меток ( Label) необходимые надписи оформления первого титульного листа курсовой работы. Кнопка (Command Button) для перехода к следующей форме проекта.

Титульный лист проекта

Форма (рисунок 2),с представлением сортировки массива методом пузырька и простых вставок, на которой расположены:

Графические окна (PictureBox) для вывода исходного и отсортированного массива, гистограммы и графика.

Текстовое окно (TextBox) для вывода пути к массиву.

Кнопки (CommandButton) для поиска массива, вывода, сортировки, построения графика и выхода из формы.

Кнопки (OptionButton) для выбора метода сортировки для построения графика.

Меню для поиска массива, сохранения результата эксперимента, сортировки методами пузырька и простых вставок и выхода из программы.

Элементы - FRAMEs -служат для объединения в группы элементов относящихся к одной логической группе.



сортировка массив программный

Главная форма программы

Форма (рисунок 3), которая позволяет выбрать нужный файл с массивом. На этой форме расположены:

Окно (DriveListBox) для выбора нужного диска.

Окно (DirListBox) для выбора нужной папки.

Окно (FieleListBox) для выбора текстового файла с массивом.

Текстовое окно (TextBox) для вывода пути к массиву из текстового файла.

Кнопка (CommandButton) копирует путь к массиву из текстового окна и выводит его в текстовое окно главной формы.

Элементы - FRAMEs -служат для объединения в группы элементов относящихся к одной логической группе.



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

Фрагмент программного кода

1.3 Метод пузырька

В фрагменте программного кода, представленного ниже, идет сортировка массива методом пузырька. Условием выполнения цикла является W(I)<W(J) (где W(I) - массив, состоящий из 10 элементов). Пока выполняется данное условие, элементы массива последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Если условие не выполняется, значит массив отсортирован.



1.4 Метод простых вставок

В фрагменте программного кода, представленного ниже, идет сортировка массива методом простых вставок.

При сортировке исходный массив разбивается на две части:

W[1], W[2], ..., W[I-1] - отсортированную часть

W[I], ...,W[n] - не отсортированную часть

На I - м шаге элемент W[I] включается в отсортированную часть, на соответствующее место. При этом часть элементов, меньших W[I], (если таковые есть) сдвигаются на одну позицию правее, чтобы освободить место для элемента W[I]. Прежде чем производить сдвиг элементов необходимо сохранить значение W[I] во временной переменной B. Сортировка завершается если набор входных данных исчерпан.



Программные коды

Форма 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

1.5 Описание работы приложения

Работа с созданным приложением начинается с запуска файла под названием «Курсовая работа» с расширением EXE. После того, как программа запущена, открывается титульный лист проекта, в котором представлена следующая информация: тема курсовой работы, разработчик и преподаватель. На первой форме присутствует кнопка (1)«Далее», которая позволяет перейти к главной форме проекта (Рисунок 4).

Титульный лист проекта

После нажатия на кнопку (1)«Далее» появляется главная форма программы (Рисунок 5).

Для задания массива из текстового файла нужно нажать кнопку (2)«Поиск» или в контекстном меню, во вкладке (3)«Файл» выбираем команду «Открыть», после чего откроется форма поиска массива (Риснок 6).

Главная форма программы

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

Указав путь к массиву, нужно нажать кнопку (4)«ОК» и, следовательно, откроется предыдущая форма.

Для вывода массива следует нажать кнопку (5)«Вывод массива», после чего на графическом поле в (6)«Picture1» появится неотсортированный массив, а также его визуализация в (7)«Picture3». Далее в контекстном меню, во вкладке (8)«Сортировать» выбираем нужный способ сортировки (Метод пузырька» или «Метод простых вставок») или на форме также выбираем нужный способ сортировки (9)(Метод пузырька» или «Метод простых вставок») и нажимаем на кнопку (10)«Сортировать массив». Затем на графическом поле в (11)«Picturе2» появится отсортированнный массив и его визуализация в (7)«Picture3». Исходный массив будет упорядочен по убыванию (Рисунок 7).

Работа программы

Чтобы построить график, нужно заранее указать путь и назначить название файлу, куда будет сохранятся результат исследования.Для этого, в контекстном меню во вкладке (3)«Файл» нужно выбрать (Файл сохранения результата).

После чего откроется окно «Сохранить как», в котором нужно ввести название и нажать кнопку «Сохранить» (Рисунок 8).

Окно сохранения результата

Затем можно приступить к построению графика.Для построения графика, на форме выбираем нужный способ сортировки (12)(Метод пузырька» или «Метод простых вставок») и нажимаем на кнопку (13)«Нарисовать график».График строится в (14)«Picturе4».(Рисунок 7).

Резуьтат исследования автоматически сохранится в указанном нами файле. Выход из программы осуществляется нажатием кнопки (15)«Выход» или в контекстном меню, во вкладке (3)«Файл» выбираем «Выход» или стандартным для всех Windows программ способом - нажатием крестика в верхнем правом углу окна.(Рисунок 7).

Результаты работы программы

Работа с графиком:



Визуализация

Результат сортировки

Метод пузырька Метод простых вставок

500 - 0,031 250 500 - 0,019 531

550 - 0,019 531 550 - 0,011 719

600 - 0,039 063 600 - 0,007 813

650 - 0,042 969 650 - 0,023 438

…. .………. …. ………...

…. ……….. …. ….…….

…. ……….. …. ……….

4850 - 2,089 844 4850 - 1,007 813

4900 - 2,121 094 4900 - 1,039 063

4950 - 2,160 156 4950 - 1,062 500

5000 - 2,191 406 5000 - 1,058 594



Заключение

В данной работе было разработано приложение на языке программирования Visual Basic 6.0, которое позволяет сортировать массив методами пузырька и простых вставок. Созданное приложение позволяет проводить исследование сортировки массивов методами пузырька и простых вставок. При этом результаты эксперимента отображаются в графическом виде (сравнительные графики), а также сохраняются в текстовом файле.

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

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



Список литературы

1. ГОСТ 19.701-90 Схемы алгоритмов программ, данных и систем. М., 1992. 22 с.

2. ГОСТ 2.105-95. Общие требования к текстовым документам. М., 1996. 31 с.

3. Форум программистов и сисадминов CyberForum.ru http://www.cyberforum.ru/visual-basic/thread141819.html (дата доступа 20.05.2013)

4. Интерактивный учебник по Visual Basic http://msdn.microsoft.com/ru-ru/library/2x7h1hfk(v=vs.90).aspx (дата доступа 18.05.2013)

5. Пособие-самоучитель on-line «Visual Basic с нуля» http://vbzero.narod.ru/page_7.htm (дата доступа 18.05.2013)

6. Система дистанционной поддержки учебного процесса кафедры информатики. URL: http://informatic.ugatu.ac.ru/kafedra/index.php (дата доступа 16.05.2013).

Размещено на Allbest.ru