Инициализация массива случайными числами
Министерство образования и науки РФ
Тверской государственный технический университет
Кафедра электронных вычислительных машин
Обработка одномерных массивов
Методические указания
к лабораторной работе № 3 по дисциплине
«Программирование на языках высокого уровня»
для студентов специальности 220100 (ВМКСС)
Тверь, 2009
Содержание
1. Цель работы.. 3
2. Теоретический материал. 3
Сортировка выбором. 4
Сортировка пузырьком. 3
Сортировка вставками. 5
Линейный поиск в массиве. 8
Двоичный поиск в массиве. 8
Инициализация массива случайными числами. 9
Измерение времени работы программы.. 10
3. Указание к работе. 11
4. Варианты индивидуальных заданий. 11
5. Оформление отчета. 24
Цель работы
Приобретение и закрепление навыков работы с одномерными массивами.
Теоретический материал
Сортировка пузырьком
Расположим массив сверху вниз, /от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию...
|
|
|
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Алгоритм сортировки «пузырьком» по убыванию представлен ниже:
i-цикл от 0 до size с шагом 1
j-цикл от 1 до size-i с шагом 1
если a[j] > a[j-1], то
x = a[j]
a[j] = a[j-1]
a[j] = x
все если
все j-цикл
все i-цикл
Среднее число сравнений и обменов имеют квадратичный порядок роста: O(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Сортировка выбором
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.
На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Алгоритм сортировки выбором представлен ниже:
|
|
|
i-цикл от 0 до size с шагом 1
k = i
x = a[i]
j-цикл от i + 1 до size с шагом 1
если a[j] < x, то
k = j
x = a[j]
все если
все j-цикл
a[k] = a[i]
a[i] = x
все i-цикл
Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = O(n2)
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.
Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Сортировка вставками
Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.
Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале «вырастает» отсортированная последовательность...
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.
|
|
|
Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].
На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.
Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.
В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы «просеиваем» элемент x к началу массива, останавливаясь в случае, когда
1. Найден элемент, меньший x
2. Достигнуто начало последовательности.
Алгоритм сортировки вставками представлен ниже:
i-цикл от 0 до size с шагом 1
x = a[i]
j-цикл от i-1 пока (j >= 0 И a[j] > x) с шагом -1
|
|
|
a[j+1] = a[j]
все j-цикл
a[j+1] = x
все i-цикл
Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как O(n2), дополнительная память при этом не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.
Сортировка подсчетом
Данный метод сортировки требует использования вспомогательного массива, по размеру совпадающего с исходным. В этот массив помещаются отсортированные элементы.
Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива надо записать очередной элемент исходного массива. Выглядит это так:
Для i = 0 До N-1
k = 0
Для j = 0 До N-1
Если A(i) > A(j) И ли A(i) = A(j) И j < i, То
k = k +1
Все-Если
Все-Для-j
B(k) = A(i)
Все-Для-i
Вычисление номера позиции, куда нужно поместить очередной элемент, реализуется, исходя из следующих соображений. Слева от B(k) должны стоять элементы, меньшие или равные B(k). Значит, число k складывается из количества элементов меньших A(i) и, возможно, некоторого числа элементов, равных A(i). Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A(i).
Сортировка слиянием
Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием. Поскольку данный метод имеет повышенную (по сравнению с уже рассмотренными) сложность, то алгоритм данного метода предлагается найти в литературе и реализовать самостоятельно.
Линейный поиск в массиве
Линейным поиском называется обычный просмотр всего массива на предмет нахождения отдельного элемента, отвечающего заданному условию.
Линейный поиск – простейшая разновидность алгоритмов поиска данных.
Например, если нам требуется найти число 5 в массиве из 15 элементов, то мы начинаем поиск с элемента с номером 0 и последовательно проверяем каждый элемент на равенство числу 5. Если совпадение найдено – необходимо запомнить номер элемента и завершить цикл поиска.
Ввиду простоты алгоритма его псевдокод и реализация не приводятся и предлагаются для самостоятельной работы.
Двоичный поиск в массиве
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.
Алгоритм двоичного поиска приведен ниже:
lowerBound = 0
upperBound = size
Повторять бесконечно
M = (lowerBound + upperBound) / 2
Если K < A[M], то
upperBound = M – 1
Иначе Если K > A[M], то
lowerBound = M + 1
Иначе
Сообщить «Элемент найден, его индекс: », M
Выход из цикла
Все если
Если lowerBound > upperBound, то
Сообщить «Элемент не найден»
Выход из цикла
Все если
Все повторять
В описанном выше алгоритме приняты следующие условия:
1. size – размер массива
2. K – число, которое нужно найти
3. М – индекс найденного элемента.
Инициализация массива случайными числами
Для выполнения лабораторной работы №3 придется пользоваться массивами большого размера. Размеры массивов в данной работе могут достигать 15 тысяч элементов, что не позволяет реализовать ввод данных с клавиатуры. Для решения этой задачи предлагается использовать инициализацию массива случайными числами.
Для работы с генератором случайных чисел необходимо создать объект стандартного класса Random:
Random Rnd = new Random();
Инициализация массива выполняется с помощью метода Next класса Random и может выглядеть следующим образом:
int maxValue = 100;
int[] a = new int[1000];
for (int i = 0; i < 1000; i++)
a[i] = Rnd.Next(0, maxValue); // Случайное число от 0 до 100
Дата добавления: 2020-01-07; просмотров: 317; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!