Рисунок 8 – Сортировка с помощью прямого выбора

тельнее алгоритма прямого включения. Однако если элементы в начале упорядочены или почти упорядочены, алгоритм с прямым включением выполнит сортировку быстрее [18];

• с помощью обмена – в основе данной группы алгоритмов лежат операции сравнения и перестановки пар соседних элементов до тех пор, пока все элементы массива не будут упорядочены. Наиболее простым алгоритмом данной группы является пузырьковая сортировка, которая получила свое название по принципу «всплывающего пузырька» - на каждой итерации цикла наименьший элемент поднимается на нужную для него позицию. Полная сортировка массива данным методом приведена на рисунке 9.

Рисунок 9 – Пузырьковая сортировка

Очевидно, что в данном примере три последних итерации являются избыточными. Улучшенным алгоритмом сортировки с помощью обмена является шейкерная сортировка, при которой на каждой итерации цикла чередуется направление просмотра массива. Пример сортировки массива данным методом представлен на рисунке 10 [10].

Рисунок 10 – Шейкерная сортировка

2.3 Выводы

В рамках данной главы рассмотрены основные виды циклов, а также описаны элементарные структуры данных – массивы.

3 ПРАКТИЧЕСКАЯ ЧАСТЬ

3.1 Элементарные операции при работе с одномерными массивами

Для выполнения практической части используется язык программирования высокого уровня C# и среда разработки Microsoft Visual Studio 2013.

Для работы с массивом его необходимо объявить. В языке программирования C# объявления массива выглядит следующим образом [12]:

const int N = 10;

int[] array = new int[N];

Здесь целочисленная константа N определяет наибольший размер массива.

Для заполнения массива используется генератор случайных чисел, который объявляется следующим образом:

Random rnd = new Random();

Само заполнение массива реализовано циклом с предусловием:

int i = 0;

while (i < N)

{

array[i] = rnd.Next(100);

i++;

}

Для вывода сгенерированных элементов на экран используется цикл с постусловием:

i = 0;

do

{

Console.Write(array[i] + " ");

i++;

} while (i < N);

Результат выполнения представленного кода приведен на рисунке 11.

---

Рисунок 11 – Создание массива

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

Для реализации поиска некоторого элемента x методом полного перебора используется следующий код:

Console.Write("Введите элемент для поиска: ");

int x = Convert.ToInt32(Console.ReadLine());

bool f = false;

for (i = 0; i < N; i++)

{

if (array[i] == x)

{

Console.WriteLine("Позиция: " + (i + 1));

f = true;

break;

}

}

if (f == false)

Console.WriteLine("Элемент отсутствует!");

В данном случае логическая переменная f используется в качестве признака существования искомого элемента в массиве.

Результат выполнения модифицированной программы представлен на рисунках 12-13.

Рисунок 12 – Пример удачного поиска с использованием полного перебора

Рисунок 13 – Пример неудачного поиска с использованием полного перебора

Для реализации бинарного поиска используется специальная функция:

public static int BinarySearch(int[] array, int l, int r, int x)

{

if (l < r)

{

int found = l + (r - l) / 2;

if (array[found] > x) return BinarySearch(array, l, found - 1, x);

else if (array[found] < x) return BinarySearch(array, found + 1, r, x);

else return found+1;

}

else return -1;

}

Для сравнения результатов представленных алгоритмов по времени их исполнения используется специальная переменная типа Stopwatch. Алгоритм ее использования прост – она запускается до начала работы поиска методом sw.Start() и останавливается после его завершения методом sw.Stop().

Код полученной программы представлен в приложении 1, а результат ее выполнения - на рисунках 14-15.

Рисунок 14 – Пример удачного поиска

Рисунок 15 – Пример удачного поиска

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

3.2 Сортировка массивов

В качестве примеров сортировки массивов рассматриваются алгоритмы, описанные ранее.

Код алгоритма сортировки прямым включение выглядит следующим образом:

static void sort_vkl(int[] array)

{

for (int i = 2; i < array.Length; i++)

{

int tmp = array[i];

int j;

for (j = i - 1; j >= 0 && array[j] > tmp; j--)

array[j + 1] = array[j];

array[j + 1] = tmp;

for (int p = 0; p < array.Length; p++)

Console.Write(array[p] + " ");

Console.WriteLine();

}

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 16.

---

Рисунок 16 – Сортировка методом прямого включения

Код алгоритма сортировки прямым выбором выглядит следующим образом:

static void sort_vyb(int[] array)

{

for (int i = 0; i < array.Length - 1; i++)

{

int min = i;

for (int j = i + 1; j < array.Length; j++)

{

if (array[j] < array[min])

min = j;

}

int temp = array[min];

array[min] = array[i];

array[i] = temp;

}

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 17.

Рисунок 17 – Сортировка методом прямого выбора

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

Следующий алгоритм сортировки – пузырьковая. Код данного метода на языке C# записывается следующим орабзом:

static void sort_puz(int[] array)

{

for (int i = 0; i < array.Length - 1; i++)

{

for (int j = i + 1; j < array.Length; j++)

{

if (array[j] < array[i])

{

int temp = array[j];

array[j] = array[i];

array[i] = temp;

}

}

for (int p = 0; p < array.Length; p++)

Console.Write(array[p] + " ");

Console.WriteLine();

}

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 18.

Рисунок 18 – Сортировка методом пузырька

Для сравнения – код шейкерной сортировки:

static void sort_shaker(int[] array)

{

int l = 1;

int r = array.Length - 1;

while (l <= r)

{

for (int i = r; i >= l; i--)

if (array[i - 1] > array[i])

{

int temp = array[i-1];

array[i-1] = array[i];

array[i] = temp;

}

l++;

for (int i = l; i <= r; i++)

if (array[i - 1] > array[i])

{

int temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

}

r--;

}

}

Результат работы программы, использующей данный алгоритм, представлен на рисунке 19.

Рисунок 19 – Шейкерная сортировка

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

Полный листинг программы с различными функциями сортировки приведен в приложении 2.

3.3 Выводы

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

ЗАКЛЮЧЕНИЕ

В рамках выполнения данной работы была рассмотрена тема «Особенности и примеры использования массивов при разработке программ».

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

---

• машинные;
• машинно-ориентированные.

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

• процедурно-ориентированные;
• проблемно-ориентированные.

Отдельное внимание в первой главе уделяется этапам решения задачи на компьютере. При этом принято выделять следующие этапы:

• постановка задачи;
• форрмализация и выбор метода решения;
• разработка алгоритма;
• составление программы;
• отладка и исполнение.

Кроме того, в первой главе приводится описание термина «алгоритм». Алгоритм представляет собой точное предписание некоторому вычислительному процессу, представленное в виде конечной последовательности элементарных действий.

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

Принято выделять три вида циклических алгоритмов:

• с предусловием («пока»);
• с постусловием («до»);
• с параметром.

Массивом называется проиндексированный набор однотипных элементов. В некоторых языках программирования индекс элементов массива может изменяться лишь в диапазоне от единицы до N (например, BASIC) или от нуля до N–1 (например, C).

Массивы бывают статические и динамические. При работе со статическими массивами программисты заранее определяют длину массива. Если же это нельзя сделать на начальном этапе, рекомендуется использовать размер с запасом. Размер динамического массива может изменяться во время выполнения программы.

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

В рамках практической части рассмотрено решение нескольких задач с массивами на языке программирования высокого уровня C#:

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Албахари Дж. C# 5.0 и платформа .NET 4.5 / Дж.Албахари, Б. Албахари. – М.: «Вильямс», 2013. – 590 с.
2. Босуэлл Д. Читаемый код, или Программирование как искусство / Д. Босуэлл, Т. Фаучер. – СПб.: Питер, 2012 – 208 с.
3. Вайсфельд М. Объектно-ориентированное мышление. – СПб.: Питер, 2014. – 304 с.
4. Громов Ю.Ю. Технология программирования / Ю.Ю. Громов, О.Г. Иванова, М.П. Беляев, Ю.В. Минин – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2013. – 172 с.
5. Иванова Г.С. Технология программирования. – Москва: Изд-во МГТУ им. Н.Э. Баумана, 2012. – 241 с.
6. Каширина Н.В. Сопоставительный анализ подготовки специалистов по информационным технология в вузах России и за рубежом / Н.В. Каширина, М.М. Маран. – Москва: Изд-во журнала «Науковедение», 2015. – 20 с.
7. Макконнелл С. Совершенный код. Мастер-класс / Пер. с англ. – М.: Издательство «Русская редакция», 2012. – 896 с.
8. Марченко А.Л. C#. Введение в программирование. – М.: Изд-во МГУ, 2015. - 258 с.
9. Мирошниченко Е.А. Технологии программирования. – Томск: Изд-во ТПУ, 2013. – 124 с.
10. Нейгел К. C# 5.0 и платформа .NET 4.5 для профессионалов - Professional C# 5.0 and .NET 4.5. — М.: «Диалектика», 2013 – 457 с.
11. Рихтер Дж. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.0 на языке C#, 3-е издание. – СПб.: Питер, 2012. – 375 с.
12. Скит Дж. C# для профессионалов: тонкости программирования, 3-е изд.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2014. – 608 с.
13. Стиллмен Э. Изучаем C#. 3-е изд. / Э. Стиллмэн, Дж. Грин. — СПб.: Питер, 2014. — 816 с.
14. Терехов А.Н. Технология программирования. – Москва: Изд-во УИТ, 2016. – 77 с.
15. Троелсен Э. Язык программирования C# 5.0 и платформа .NET 4.5, 6-е изд. : Пер. с англ. — М. : «Вильямс», 2013. — 1312 с.
16. Цветкова М.С. Информатика и ИКТ / М.С. Цветкова, Л.С. Великович. – М.: Издательский центр «Академия», 2012. – 352 с.
17. Цехоня В.И. Технология программирования / В.И. Цехоня, В.Ф. Гузик. – Таганрог: изд-во ТТИ ЮФУ, 2011. – 144 с.
18. Шамшев А.Б. Основы языка C#. – Ульяновск: УлГТУ, 2015. – 132 с.
19. Шаповаленко В.А. Технологии программирования / В.А. Шаповаленко, И.Г. Швайко. – Одесса: Изд-во ОНА им. А.С. Попова, 2011. – 120 с.
20. Шилдт Г. C# Полное руководство. – М.: «Вильямс», 2015. – 1056 с.

---

Смотрите также файлы

• Договора и их виды как одна из форм организации коммерческой деятельности по работе с контрагентами (на примере конкретной организации)(Понятие и сущность договора в коммерческой деятельности).pdf

• Современные политические режимы (Типы политических режимов. Тоталитарный, авторитарный и демократический режимы).pdf

• Организация работы предприятия быстрого обслуживания..pdf

• Коммерческие риски и способы их уменьшения (на примере конкретной организации)».pdf

• Оценка качества рыбных товаров (ОКП 926000) на примере рыбы соленой.pdf