Курсовой работе на тему Исследование методов сортировки массивов

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

Министерство образования и науки Российской Федерации

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

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

Пояснительная записка

К курсовой работе:

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

Выполнил: студент гр.

Проверил: преподаватель

УФА 2007

Содержание.

  1. Задание….………………………………………………………………………………..3
  2. Введение………………………………………………………………………………….4
  3. Метод простых вставок………………………………………………………………..4
  4. Метод бинарных деревьев…………………………………………………………..4-5
  5. Создание приложения………………………………………………………………6-12
  6. Список использованной литературы……………………………………………….13

Введение

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

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

Последовательно просматриваем a, …, an-1  и каждый новый элемент a вставляем на подходящее место в уже упорядоченную совокупность a, …, ai-1 . Это место определяется последовательным сравнением a с упорядоченными элементами a, …, ai-1 .

листинг данного метода в программе:

Public Sub InsertionSort(ByRef Arr() As Double, ByVal N As Long)

Dim I As Long

Dim J As Long

Dim K As Long

Dim Tmp As Double

N = N-1

i = 1

Do

j = 0

Do

If Arr(i)<=Arr(j) then

k = i

Tmp = Arr(i)

Do

Arr(k) = Arr(k-1)

k = k-1

Loop Until Not k>j

Arr(j) = Tmp

j = i

Else

j = j+1

End If

Loop Until Not j<i

i = i+1

Loop Until Not i<=n

End Sub

Метод бинарных деревьев

Алгоритм основан на представлении массива в виде бинарного дерева, обладающего особыми свойствами. В памяти компьютера все элементы массива расположены последовательно, структура же дерева определяется следующим образом: будем считать, что i-ый элемент массива (“предок”) имеет два элемента потомка с номерами 2i+1 и 2i+2. Дерево имеет нормальную форму, если любой элемент предок больше своих потомков.

Для понимания алгоритма рассмотрите приведенную блок-схему. Из свойств алгоритма стоит заметить, что он дает стабильно хорошую скорость упорядочивания (порядка n*log(n)), вне зависимости от того с каким массивом работает, и поэтому используется в случаях когда необходимо гарантировано упорядочить массив за короткое время.

листинг данного метода в программе:

Public Sub HeapSort(ByRef Arr() As Double, ByVal N As Long)

Dim I As Long

Dim J As Long

Dim K As Long

Dim T As Long

Dim Tmp As Double

If N=1 then

Exit Sub

End If

i = 2

Do

t = i

Do While t<>1

k = t\2

If Arr(k-1)>=Arr(t-1) then

t = 1

Else

Tmp = Arr(k-1)

Arr(k-1) = Arr(t-1)

Arr(t-1) = Tmp

t = k

End If

Loop

i = i+1

Loop Until Not i<=n

i = n-1

Do

Tmp = Arr(i)

Arr(i) = Arr(0)

Arr(0) = Tmp

t = 1

Do While t<>0

k = 2*t

If k>i then

t = 0

Else

If k<i then

If Arr(k)>Arr(k-1) then

k = k+1

End If

End If

If Arr(t-1)>=Arr(k-1) then

t = 0

Else

Tmp = Arr(k-1)

Arr(k-1) = Arr(t-1)

Arr(t-1) = Tmp

t = k

End If

End If

Loop

i = i-1

Loop Until Not i>=1

End Sub

Создание приложения

При запуске Microsoft Visual Basic 6.0 автоматически выскакивает окно с предложением создать новый проект Standard EXE. Нажимаем OK. Начнём создание проекта с титульного листа. Для этого в меню Project выберем команду Add Form. В появившемся диалоговом окне выберем Dialog и нажмем OK. В открывшейся форме расставим объекты: Label1, Label2, … , Label8, Image1

Присвоим свойству Caption значение “Титульный лист”. На кнопку Вход напишем следующий программный код:

__________

Private Sub EnterButton_Click()

Unload Dialog

Form1.Show

End Sub

__________

При щелчке на кнопке OK из памяти выгружается форма Dialog и загружается базовая форма, служащая начальной точкой для всех операций с программой, форма Form1. Для того, чтобы создать форму Form1, в меню Project выполним команду Add Form. В появившемся диалоговом окне выберем Form и нажмем OK. Присвоим свойству Caption формы Form1 значение “ Курсовой проект – Тема 1 вариант 6”.

рис. Главная форма

Создадим меню для проекта. Для этого в меню Tools выполним команду Menu Editor. В появившемся диалоговом окне напишем названия пунктов меню и названия процедур, которые будут запускаться при выполнении команд меню. Редактор меню с введёнными именами представлен на рисунке (см. рис. №4).

Рисунок №4

Опишем какие процедуры выполняются в каждом пункте меню.

1. MnuFileSave_rez – осуществляет сохранение результата эксперимента. Результат сохраняется в файле log.txt, куда записывается система линейных уравнений, полученные результаты.

__________

Private Sub MnuFileSave_rez_Click()

Open App.Path & “\log.txt” For Output As #1

Print #1, “Ðåçóëüòàòû ñîðòèðîâêè” & Chr(13) & Chr(10) & “(êîë-âî ýëåìåíòîâ – âðåìÿ)” & Chr(13) & Chr(10) & Text1.Text

Close #1

End Sub

__________

3. MnuFileLook_rez – осуществляет вывод на экран ранее сохранённого результата, если предварительно его сохранили.

___________

Private Sub MnuFileLook_rez_Click()

Load Dialog3

Dialog3.Show

End Sub

­­­­­­­­­­­­­­­­­­­­­­­____________

При выполнении этой процедуры загружается форма Dialog3, на которой находится объект Text1, в который выводится сохраненный отчет. Отчет загружается при загрузке формы. Программный код Dialog3:

__________

Private Sub Form_Load()

Open App.Path & “\log.txt” For Input As #2

Do Until EOF(2)

Line Input #2, LineOfText$

Text1.Text = Text1.Text & LineOfText$ & Chr(13) & Chr(10)

Loop

Close #2

End Sub

Private Sub OKButton_Click()

Dialog3.Hide

Unload Dialog3

End Sub

__________

В процедуре Form_Load (), открывает файл, производит построчное считывание из него и вывод в объект Text1. Готовая форма Dialog3 изображена на рисунке (см. рис. №8). При щелчке на кнопке OK происходит выгрузка формы Dialog3 из оперативной памяти.

Рисунок №8

4. MnuHelpAbout – выводит на экран информацию о программе. Вывод осуществляется с помощью формы Dialog2.

__________

Private Sub MnuHelpAbout_Click()

Dialog2.Show

End Sub

__________

При щелчке на кнопке OK (объект Command1) происходит выгрузка формы Dialog2 из оперативной памяти.

Программный код формы Dialog2:

__________

Private Sub OKButton_Click()

Unload Dialog2

End Sub

__________

5. MnuFileExit– производит выход из приложения.

__________

Private Sub MnuFileExit ()

End

End Sub

__________

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

Код модуля:

Public countz

Public Sub ShellSort(ByRef Arr() As Double, ByVal N As Long)

Dim C As Boolean

Dim E As Long

Dim G As Long

Dim I As Long

Dim J As Long

Dim Tmp As Double

N = N – 1

G = (N + 1) \ 2

Do

I = G

Do

J = I – G

C = True

Do

If Arr(J) <= Arr(J + G) Then

C = False

Else

Tmp = Arr(J)

Arr(J) = Arr(J + G)

Arr(J + G) = Tmp

End If

J = J – 1

Loop Until Not (J >= 0 And C)

I = I + 1

Loop Until Not I <= N

G = G \ 2

Loop Until Not G > 0

End Sub

Public Sub Binar(ByRef Arr() As Double, ByVal N As Long)

Dim C As Boolean

Dim E As Long

Dim G As Long

Dim I As Long

Dim J As Long

Dim Tmp As Double

N = N – 1

G = (N + 1) \ 2

Do

I = G

Do

J = I – G

C = True

Do

If Arr(J) <= Arr(J + G) Then

C = False

Else

Tmp = Arr(J)

Arr(J) = Arr(J + G)

Arr(J + G) = Tmp

End If

J = J – 1

Loop Until Not (J >= 0 And C)

I = I + 1

Loop Until Not I <= N

G = G \ 2

Loop Until Not G > 0

End Sub

Программный код формы Form1:

__________

Dim Arr() As Double

Dim arTime(100) As Double

Dim FRST

Dim p As Long

Private Sub Command1_Click()

Command3.Enabled = True

Text1.Text = “”

For I = 0 To 5000 Step 50

p = 5000 – I

ReDim Arr(p)

For J = 0 To p

Randomize

Arr(J) = Rnd(10) * 1000

Next J

c1 = Timer

If Option1.Value = True Then Call ShellSort(Arr, p) Else Call Binar(Arr, p)

 

c2 = Timer

tt = c2 – c1

arTime(I / 50) = tt

Text1.Text = Text1.Text & p & ” – ” & tt & Chr(13) & Chr(10)

Next I

End Sub

Private Sub Command2_Click()

End

End Sub

Private Sub Command3_Click()

Max = arTime(0)

For I = 1 To 100

If arTime(I) > Max Then Max = arTime(I)

Next

picG.Cls

Lgran = -50

Rgran = 5050

YY = Max + 0.1

XX = -0.05

picG.Scale (Lgran, YY)-(Rgran, XX)

picG.Line (Lgran, 0)-(Rgran, 0)

picG.Line (0, YY)-(0, XX)

picG.Line (0, YY)-(-20, YY – 0.01)

picG.Line (0, YY)-(20, YY – 0.01)

picG.Line (Rgran, 0)-(Rgran – 40, 0.01)

picG.Line (Rgran, 0)-(Rgran – 40, -0.01)

For I = 0 To 5000 Step 250

picG.Line (I, 0)-(I, -(YY – XX) * 0.008)

picG.CurrentX = I + 5

picG.CurrentY = -(YY – XX) * 0.012

picG.Print I

Next

For I = 1 To 50

II = I * 0.1

picG.Line (0, II)-(5, II)

picG.CurrentX = 6

picG.CurrentY = II

picG.Print II

Next

For J = 0 To 99

lin = arTime(100 – J)

lin2 = arTime(100 – J – 1)

picG.Line (J * 50, lin)-((J + 1) * 50, lin)

picG.Line ((J + 1) * 50, lin)-((J + 1) * 50, lin2)

Next

End Sub

Private Sub MnuFileExit_Click()

End

End Sub

Private Sub MnuFileLook_rez_Click()

Load Dialog3

Dialog3.Show

End Sub

Private Sub MnuFileSave_rez_Click()

Open App.Path & “\log.txt” For Output As #1

Print #1, “Ðåçóëüòàòû ñîðòèðîâêè” & Chr(13) & Chr(10) & “(êîë-âî ýëåìåíòîâ – âðåìÿ)” & Chr(13) & Chr(10) & Text1.Text

Close #1

End Sub

Список использованной литературы:

1. Мастер – Самоучитель по Visual Basic 6.0 AlexSoft 1997-2001 г.

2. Информатика. Высшая школа. Острейковский В. А. 2000 г.

3. www.informatic.ugatu.ic.ru – официальный сайт кафедры информатики УГАТУ, отдел дистанционной помощи студентам по написанию курсовых работ.

О Main Aditor

Здравствуйте! Если у Вас возникнут вопросы, напишите нам на почту help@allinweb.ru

Добавить комментарий

Ваш адрес email не будет опубликован.