Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Исследование времени сортировки методом пузырька и методом быстрой сортировки - файл Пояснительная записка.doc


Исследование времени сортировки методом пузырька и методом быстрой сортировки
скачать (186.2 kb.)

Доступные файлы (14):

data.txt1kb.29.05.2009 19:52скачать
Form1.frm
Form2.frm
Form3.frm
Form3.frx
Form4.frm
Form5.frm
Form5.frx
MSSCCPRJ.SCC
Project1.exe
Project1.vbp
Project1.vbw
result.txt6kb.29.05.2009 19:56скачать
Пояснительная записка.doc91kb.29.05.2009 19:51скачать

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

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

КУРСОВАЯ РАБОТА
«Методы исследования сортировки массива»
Выполнил: Кудряшова Е.Д.

студент гр. СМ-109

Проверил:

Уфа 2009г.

Содержание

1. Теоретическая часть.................................................................................................3
2. Описание программы...............................................................................................4
3. Список литературы.................................................................................................10
1. Теоретическая часть
Метод пузырька

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка.
^ Метод быстрой сортировки

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

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

2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:

1) два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;

2) вычисляется опорный элемент m;

3) индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;

4) индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;

5) если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;

6) если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

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


^ 2. Описание программы




рис 1. Сортировка методом пузырька



рис 2. Метод быстрой сортировки


рис 3. Графический результат исследования времени сортировки
Option Explicit

Dim a(1 To 5000) As Integer, bb(1 To 5000) As Integer

Dim n As Integer

Private Sub About_Click()

Form2.Show (1)

End Sub
Private Sub Author_Click()

Form4.Show (1)

End Sub

Sub Bubbl()

Dim i, j As Integer, tmp As Integer

For i = 1 To n - 1

For j = i + 1 To n

If bb(i) < bb(j) Then

tmp = bb(i)

bb(i) = bb(j)

bb(j) = tmp

End If

Next j

Next i

End Sub

Function FastSort(a0 As Integer, b0 As Integer) As Boolean

Dim i, j, x, temp As Integer

Dim flag As Boolean

i = a0

j = b0

flag = False

x = bb((a0 + b0) / 2)

Do

Do While (bb(i) > x)

i = i + 1

Loop

Do While (bb(j) < x)

j = j - 1

Loop

If i <= j Then

If i < j Then

temp = bb(i)

bb(i) = bb(j)

bb(j) = temp

End If

i = i + 1

j = j - 1

End If

Loop Until i >= j

If i < b0 Then

temp = i

flag = FastSort(temp, b0)

Else: flag = True

End If

If a0 < j Then

temp = j

flag = FastSort(a0, temp)

Else: flag = True

End If

FastSort = flag

End Function


Private Sub Bubble_Click()

Dim i As Integer, j As Integer, k As Integer, c As Integer, t As Integer

Dim e As Integer, b As Integer

Dim s, s2() As String

Open "data.txt" For Input As #1

n = 0

While Not EOF(1)

n = n + 1

Line Input #1, s

s2 = Split(s)

bb(n) = Val(s2(0))

a(n) = Val(s2(0))

Wend

Close #1

Bubbl

Open "data.txt" For Output As #1

For i = 1 To n

Print #1, a(i) & " " & bb(i)

Next i

Close #1

Form5.MSChart1.chartType = VtChChartType2dBar

Form5.MSChart1.AllowSelections = False

Form5.MSChart1.ColumnCount = n

Form5.MSChart1.RowCount = 1

Form5.MSChart1.RowLabel = ""

For i = 1 To n

Form5.MSChart1.Column = i

Form5.MSChart1.Data = bb(i)

Next i

Form5.Show (1)

End Sub
Private Sub Exit_Click()

End

End Sub
Private Sub Fast_Click()

Dim i As Integer, j As Integer, k As Integer, c As Integer, t As Integer

Dim e As Integer, b As Integer

Dim s, s2() As String

Dim flag As Boolean

Open "data.txt" For Input As #1

n = 0

While Not EOF(1)

n = n + 1

Line Input #1, s

s2 = Split(s)

bb(n) = Val(s2(0))

a(n) = Val(s2(0))

Wend

Close #1

flag = FastSort(1, n)

Open "data.txt" For Output As #1

For i = 1 To n

Print #1, a(i) & " " & bb(i)

Next i

Close #1

Form5.MSChart1.chartType = VtChChartType2dBar

Form5.MSChart1.AllowSelections = False

Form5.MSChart1.ColumnCount = n

Form5.MSChart1.RowCount = 1

Form5.MSChart1.RowLabel = ""

For i = 1 To n

Form5.MSChart1.Column = i

Form5.MSChart1.Data = bb(i)

Next i

Form5.Show (1)

End Sub
Private Sub Researh_Click()

Dim i As Integer, j As Integer, k As Integer, t As Integer

Dim g As Integer, b As Integer, e As Integer, c As Integer

Dim c2, flag As Boolean

Dim tmp As Double, tstart As Double, tfin As Double

Dim sh As Double

Dim yt As Double, yt1 As Double, yb As Double, yb1 As Double ', max As Single

sh = 5

Form1.Picture1.ScaleWidth = 5000

Form1.Picture1.ScaleHeight = sh

For i = 0 To 5000 Step 500

Form1.Picture1.Line (i, sh)-(i, sh - sh / 40)

Form1.Picture1.CurrentX = i

Form1.Picture1.CurrentY = sh - sh / 20

Form1.Picture1.Print i

Next i

For tmp = 0 To sh Step sh / 10

Form1.Picture1.Line (0, sh - tmp)-(5000 / 40, sh - tmp)

Form1.Picture1.CurrentX = 5000 / 40

Form1.Picture1.CurrentY = sh - tmp

Form1.Picture1.Print tmp

Next tmp

yb1 = 0

yt1 = 0

Randomize

For i = 1 To 5000

a(i) = (1000 * Rnd)

Next i

Open "result.txt" For Output As #1

For n = 500 To 5000 Step 50

For i = 1 To n

bb(i) = a(i)

Next i

tstart = Timer

'пузырек

Bubbl

tfin = Timer

yt = tfin - tstart

'Быстрая сортировка

For i = 1 To n

bb(i) = a(i)

Next i

tstart = Timer

flag = FastSort(1, n)

tfin = Timer

yb = tfin - tstart

Form1.Picture1.Line (n - 50, sh - yb1)-(n, sh - yb), &HC00000

Form1.Picture1.Line (n - 50, sh - yt1)-(n, sh - yt), &HC0&

yt1 = yt

yb1 = yb

Print #1, n, yt, yb

Next n

Close #1

Form1.Show (1)

End Sub

3. Литература
Бабак Л.И. Черкашин М.В. «Вычислительные методы. (Учебное пособие)»


Скачать файл (186.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации