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

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

Министерство образования и просвещения РФ

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

технический университет

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

Тема 1

Вариант 5

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

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

Выполнила:

Синявина К. А.

УФА

2005



Содержание

Введение

Сортировка

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

Метод сортировки бинарными вставками

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

Текст программы

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



Введение

Целью этой работы является исследование и сравнение методов сортировки массивов: метода простых вставок и метода бинарных вставок. Сортировка выполняется по убыванию.



Сортировка

Алгоритмы сортировки информации образуют основу для огромного большинства прикладных программ. Сортировка информации - это одна из стандартных функций, возникающих в процессе решения задач.

Сортировка данных - это процесс изменения порядка расположения элементов в некоторых упорядоченных структурах данных таким образом, чтобы обеспечить возрастание или убывание числового значения элемента данных или определенного числового параметра, связанного с каждым элементом данных, при переходе от предыдущего элемента к последующему. То есть, для любой пары чисел определены отношения "больше" или "меньше".

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

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

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

Этот метод часто используют при сортировке, например, карт: берем одну карту и вставляем ее в нужное место среди тех, что мы уже упорядочили. То есть, последовательно просматриваем a₁ , ..., a_n-1 и каждый новый элемент a_i вставляем на подходящее место в уже упорядоченную совокупность a₀ , ..., a_i-1 . Это место определяется последовательным сравнением a_i с упорядоченными элементами a₀ , ..., a_i-1 .Сортировка начинается со второго элемента.

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

Блок-схема (Метод сортировки простыми вставками).

Пример реализации программы в Visual Basic:

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 бинарный вставка массив basic

End If

Loop Until Not j<i

i = i+1

Loop Until Not i<=n

Метод сортировки бинарными вставками

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске места, на которое надо вставить элемент a_i в уже упорядоченную совокупность a₀ , ..., a_i-1 , определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимается как "вставка делением пополам").

Пример реализации программы в Visual Basic:

i = 2

Do

b = 1

e = i-1

c = (b+e)\2

Do While b<>c

If Arr(c-1)>Arr(i-1) then

e = c

Else

b = c

End If

c = (b+e)\2

Loop

If Arr(b-1)<Arr(i-1) then

If Arr(i-1)>Arr(e-1) then

b = e+1

Else

b = e

End If

End If

k = i

Tmp = Arr(i-1)

Do While k>b

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

k = k-1

Loop

Arr(b-1) = Tmp

i = i+1

Loop Until Not i<=n

Блок-схема (Метод сортировки бинарными вставками).



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

Форма № 1(Меню)

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

1 - нажатие этой кнопки позволяет перейти на форму № 2, с помощью которой

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

2 - нажатие этой кнопки позволяет перейти на форму № 4, с помощью которой

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

3 - нажатие этой кнопки позволяет перейти на форму № 5, с помощью которой

можно провести эксперимент: сравнить время сортировки методами простых и

бинарных ставок по времени, за которое проводится сортировка. Сортировка

проводится для массивов с количеством элементов от 500 до 5000 с шагом 500.

4 - нажатие этой кнопки позволяет выйти из программы.

5 - соответствует кнопкам, расположенным на форме, включая выход из программы

6 - содержит информацию о программе и ее разработчике.

Форма № 2(Метод простых вставок(соответствует также форме № 4, с помощью которой можно отсортировать массив, используя метод бинарных вставок))

1 - текстовое окно для ввода элементов массива.

2 - кнопка ввода данных.

3 - поле, отображающее состояние массива до и после сортировки выбранным

методом. До ввода данных - пустое.

4 - гистограмма, отображающая состояние массива до и после сортировки. До ввода

данных поле пустое.

5 - нажатие этой кнопки позволяет сортировать массив выбранным методом.

6 - отображение хода процесса.

7 - нажатие этой кнопки позволяет перейти на форму № 3 для сохранения данных,

полученных после сортировки.

8 - выход в меню (форма № 1).

Строго следуйте инструкции:

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

Шаг № 2. Нажмите кнопку (2). В поле (3) появляется столбец чисел, соответствующий элементам массива, который вы задали в текстовом окне (1). В поле (4) появится гистограмма, отображающая данное не отсортированное состояние массива.

Шаг № 3. Нажмите кнопку (5). Состояние полей (3) и (4) изменится. Поле (3) теперь будет содержать отсортированный по убыванию методом простых или бинарных вставок массив, состоящий из чисел.

Шаг № 4. Для сохранения полученных данных нажимаем кнопку (7)

Форма № 3 (Сохранение полученных результатов)

1 - выбор диска.

2 - выбор папки.

3 - содержание выбранной папки.

4 - ввод имени файла для сохранения результатов.

5 - сохранение результатов.

6 - выход в меню.

7 - выход из программы.

Инструкция:

Шаг № 1. Выбираем диск и папку, где будут сохранены результаты.

Шаг № 2. В текстовое окно вводим имя файла, в котором будут сохранены результаты (указание расширения ".txt" в конце имени файла обязательно).

Шаг № 3. Нажимаем кнопку (5).

Примечание: если текстового документа с набранным вами именем нет, то программа автоматически создаст его.

Форма № 5 (Эксперимент)

Главным показателем качества алгоритма сортировки является скорость сортировки. Выбор в пользу того или иного алгоритма может быть сделан при условии тщательного статистического анализа реальной задачи и это является достаточно важной проблемой в программировании. С помощью этого эксперимента можно наглядно при помощи графика увидеть и сравнить метод простых с методом бинарных вставок. На графике отражена зависимость времени сортировки от количества элементов в массиве (количество этих элементов изменяется от 500 до 5000 с шагом в 500 элементов). Программа произвольно задает элементы массива, в то время как количество самих массивов, участвующих в эксперименте, вы задаете сами (от 2 до 10), потом производит сортировку и определяет разницу во времени. В ходе проведения эксперимента на форму выводятся результаты.

1 - текстовое окно для ввода числа массивов.

2 - нажатие этой кнопки приводит к началу эксперимента.

3 - поле, отображающее время сортировки методом простых вставок.

4 - поле, отображающее время сортировки методом бинарных вставок.

5 - поле, на котором изображается график зависимости времени сортировки от

количества элементов в массиве.

6 - отображение хода процесса.

7 - условные обозначения, принятые на форме и используемые на графике.

8 - выход в меню.

9 - выход из программы.

10 - поле, отображающее разницу во времени.

11 - сохранение результатов эксперимента.

Примечание: поля 3, 4, 5, 10 до начала процесса - пустые.

Инструкция:

Шаг № 1. В текстовое окно (1) вводим число массивов (от 2 до 10), участвующих в сортировке.

Шаг № 2. Нажатие кнопки (2) приводит к началу эксперимента.

Шаг № 3. Сохраняем результаты, нажатием кнопки (11).

Форма № 6 (содержит информацию о программе и ее разработчике)

1 - выход в меню.

2 - сведения о системе.



Текст программы

Форма №1(Меню)

Private Sub Command1_Click()

Form1.Hide

Form2.Show

End Sub

Private Sub Command2_Click()

Form1.Hide

Form4.Show

End Sub

Private Sub Command3_Click()

Form1.Hide

Form5.Show

End Sub

Private Sub Command4_Click()

End

End Sub

Private Sub p_vst_Click()

Form1.Hide

Form2.Show

End Sub

Private Sub b_vst_Click()

Form1.Hide

Form4.Show

End Sub

Private Sub exp_Click()

Form1.Hide

Form5.Show

End Sub

Private Sub end_Click()

End

End Sub

Private Sub about_programm_Click()

frmAbout.Show

End Sub

Форма № 2(Метод простых вставок)

Private Sub Command1_Click()

Picture1.Cls

Picture2.Cls

qw = Text1

av = Split(qw, " ") ` разбивает строку по разделителю

maxAm = 0

minAm = 0

For i = 1 To 10

Am(i) = Val(av(i - 1))

Picture2.Print Am(i)

If Am(i) > maxAm Then maxAm = Am(i)

Next i

`построение графика

For i = 1 To 10

If Am(i) > maxAm Then maxAm = Am(i)

If Am(i) < minAm Then minAm = Am(i)

Next i

Picture1.Scale (0, maxAm + maxAm / 10)-(10, minAm + minAm / 10)

i = 1

For x = 1 To 10

Picture1.Line (x - 1, 0)-(x, Am(i)), RGB(255 - x * 15, 150 - x * 15, 200 - x * 15), BF

i = i + 1

Next x

End Sub

Private Sub Command2_Click()

Form2.Hide

Form3.Show

End Sub

Private Sub Command3_Click()

Form2.Hide

Form1.Show

End Sub

Private Sub Command4_Click()

Picture1.Cls

Picture2.Cls

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

For K = 2 To 10

d = Am(K)

For i = 1 To K - 1

If Am(i) < d Then Exit For

Next i

For J = K - 1 To i Step -1

Am(J + 1) = Am(J)

Next J

Am(i) = d

Next K

For i = 1 To 10

Picture2.Print Am(i)

Next i

`построение графика

maxAm = 0

ProgressBar1.Max = 10

For i = 1 To 10

ProgressBar1.Value = i

If Am(i) > maxAm Then maxAm = Am(i)

Next i

i = 1

For x = 1 To 10

Picture1.Line (x - 1, 0)-(x, Am(i)), RGB(255 - x * 15, 150 - x * 15, 200 - x * 15), BF

i = i + 1

Next x

End Sub

Форма № 3(Сохранение полученных результатов)

Private Sub Command2_Click()

Form3.Hide

Form1.Show

End Sub

Private Sub Command3_Click()

End

End Sub

Private Sub Command4_Click()

Open File1.Path + "\" + Text1 For Output As #1

Print #1, "Массив после сортировки "

For i = 1 To 10

Print #1, am(i);

Next i

Close #1

End Sub

Private Sub Dir1_Change()

File1.Path = Dir1.Path

End Sub

Private Sub Drive1_Change()

Dir1.Path = Drive1.Drive

End Sub

Форма № 4(Метод бинарных вставок)

Dim n As Integer

Private Sub Command1_Click()

Picture1.Cls

Picture2.Cls

ProgressBar1.Value = 0

n = 10

qw = Text1

av = Split(qw, " ") ' разбивает строку по разделителю

maxam = 0

minam = 0

For i = 1 To 10

am(i) = Val(av(i - 1))

Picture2.Print am(i)

If am(i) > maxam Then maxam = am(i)

Next i

`построение графика

For i = 1 To 10

If am(i) > maxam Then maxam = am(i)

If am(i) < minam Then minam = am(i)

Next i

Picture1.Scale (0, maxam + maxam / 10)-(10, minam + minam / 10)

i = 1

For x = 1 To 10

Picture1.Line (x - 1, 0)-(x, am(i)), RGB(255 - x * 15, 150 - x * 15, 200 - x * 15), BF

i = i + 1

Next x

End Sub

Private Sub Command2_Click()

Form2.Hide

Form3.Show

End Sub

Private Sub Command3_Click()

Picture1.Cls

Picture2.Cls

`метод бинарных вставок

i = 2

For i = 2 To n

B = 1

E = i - 1

C = Int((B + E) / 2)

Do Until B = C

If am(C) < am(i) Then E = C

If am(C) >= am(i) Then B = C

C = Int((B + E) / 2)

Loop

If am(C) >= am(i) And am(C + 1) < am(i) Then

z = Val(am(i))

For J = i - 1 To C + 1 Step -1

am(J + 1) = am(J)

Next J

am(C + 1) = z

End If

If am(C) <= am(i) Then

z = Val(am(i))

For J = i - 1 To C Step -1

am(J + 1) = am(J)

Next J

am(C) = z

End If

Next i

ProgressBar1.Max = n

For i = 1 To n

Picture2.Print am(i)

Picture1.Line (i - 1, 0)-(i, am(i)), RGB(255 - i * 15, 150 - i * 15, 200 - i * 15), BF

ProgressBar1.Value = i

Next i

End Sub

Private Sub Command4_Click()

Form4.Hide

Form1.Show

End Sub

Форма № 5 (Эксперимент)

Private Sub Command1_Click()

Form5.Hide

Form1.Show

End Sub

Private Sub Command2_Click()

End

End Sub

Private Sub Command3_Click()

Picture1.Cls

Picture2.Cls

Picture3.Cls

Picture4.Cls

ProgressBar1.Value = 0

qw = Text1 `количество массивов с числом элементов от 500 до 5000

ProgressBar1.Max = qw * 2

For M = 1 To qw

Randomize

For i = 1 To 500 * M

am(i) = Int(Rnd * 100 + -10)

Next i

t1 = Timer

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

For K = 2 To 500 * M

d = am(K)

For i = 1 To K - 1

If am(i) < d Then Exit For

Next i

For J = K - 1 To i Step -1

am(J + 1) = am(J)

Next J

am(i) = d

Next K

t2 = Timer

Tp(M) = t2 - t1

Picture2.Print Tp(M)

ProgressBar1.Value = M

Next M

For M = 1 To qw

Randomize

For i = 1 To 500 * M

am(i) = Int(Rnd * 100 + -10)

Next i

t1 = Timer

`метод бинарных вставок

i = 2

For i = 2 To 500 * M

B = 1

E = i - 1

C = Int((B + E) / 2)

Do Until B = C

If am(C) < am(i) Then E = C

If am(C) >= am(i) Then B = C

C = Int((B + E) / 2)

Loop

If am(C) >= am(i) And am(C + 1) < am(i) Then

z = Val(am(i))

For J = i - 1 To C + 1 Step -1

am(J + 1) = am(J)

Next J

am(C + 1) = z

End If

If am(C) <= am(i) Then

z = Val(am(i))

For J = i - 1 To C Step -1

am(J + 1) = am(J)

Next J

am(C) = z

End If

Next i

t2 = Timer

Tb(M) = t2 - t1

Picture3.Print Tb(M)

ProgressBar1.Value = qw + M

Next M

minx = 500

maxx = qw * 500

miny = Tp(1)

maxy = Tp(qw)

Picture1.Scale (-maxx / 10, maxy)-(maxx, -maxy / 10)

Picture1.Line (-maxx, 0)-(maxx, 0)

Picture1.Line (0, maxy)-(0, -maxy)

For i = 1 To qw

Picture1.Line (500 * i, Tp(i))-(500 * (i + 1), Tp(i + 1)), RGB(0, 0, 255)

Picture1.Line (500 * i, Tb(i))-(500 * (i + 1), Tb(i + 1)), RGB(255, 0, 0)

Next i

Sp = 0

Sb = 0

delta = 0

For i = 1 To qw

Sp = Sp + Tp(i)

Sb = Sb + Tb(i)

Next i

delta = (Sp - Sb) / qw

Picture4.Print delta

End Sub

Private Sub Command4_Click()

Open "результаты эксперимента.txt" For Output As #1

Print #1, "метод бинарных вставок выполняется быстрее на "; delta

Close #1

End Sub

Модуль1.

Option Base 1

Public am(100000), Tp(100), Tb(100), delta As Double



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

1. Браун С., Visual Basic 6.0: учебный курс. С-Пб, "Питер", 1999 ,322с

2. Браун К., Введение в Visual Basic для программистов, М,"Мир", 1993, 415с

3. www.alglib.sources.ru

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

...