Читайте также:
|
С точки зрения удобства программирования, передавать значения, которые могут изменяться внутри функции, лучше всего через указатель (а не через ссылку).
Внутри функции перед переменной, которая является ссылкой, приходится ставить * для получения её значения. И при вызове функции приходится перед именем переменной ставить & для того, чтобы передать ссылку на переменную (по сути, адрес).
Видно, что никаких разыменовываний указателей в функции, и передачи адреса переменной в таком вызове функции не требуется.
Однако, следует помнить, что такая передача по указателю возможна только для базовых типов и стандартных объектов в C/C++. И не работает для передачи массивов!
Поэтому, если, к примеру, функция принимает:
одномерный массив block, элементы которого надо изменить внутри функции (сложный/составной тип)
целочислительную переменную shift, которую тоже надо изменить внутри функции (базовый тип)
12)Пузырьковая сортировка.Оценка сложгости пузырьковой сортировки.
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n^2).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент находится на N-1 месте. И так далее. Таким образом, на каждом следующем проходе число обрабатываемых элементов уменьшается на 1 и нет необходимости «обходить» весь массив от начала до конца каждый раз.
Так как подмассив из одного элемента не нуждается в сортировке, то для сортировки требуется делать не более N-1 итераций внешнего цикла. Поэтому в некоторых реализациях внешний цикл всегда выполняется ровно N-1 и не отслеживается, были или не были обмены на каждой итерации.
Введение индикатора (флажка F) действительно произошедших во внутреннем цикле обменов уменьшает число лишних проходов в случаях с частично отсортированными массивами на входе. Перед каждым проходом по внутреннему циклу флажок сбрасывается в 0, а после действительно произошедшего обмена устанавливается в 1. Если после выхода из внутреннего цикла флажок равен 0, то обменов не было, то есть массив отсортирован и можно досрочно выйти из программы сортировки.
Алгоритм можно немного улучшить, сделав следующее:
Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой. Сложность при этом O(n \cdot n) не уменьшается.
В сортировке пузырьком, при каждом проходе по внутреннему циклу, можно добавить определение очередного минимального элемента и помещение его в начало массива, то есть объединить алгоритмы сортировки пузырьком и сортировки выбором, при этом число проходов по внутреннему циклу сокращается вдвое, но более чем вдвое увеличивается число сравнений и добавляется один обмен после каждого прохода по внутреннему циклу.
Название “Пузырьковая Сортировка” происходит от образной интерпретации, по которой алгоритм заставляет “легкие” элементы мало-помалу всплывать на “поверхность”.
Этот алгоритм имеет минимальную сложность 0(n):если массив первоначально отсортирован, переменная инверсия никогда не примет значение истина. Напротив, максимальная сложность равна 0((n - 1)2) = 0(n2): в самом деле, если минимальный элемент имеет первоначально индекс n, потребуется, n - 1 выполнении внешнего цикла, чтобы дать ему индекс 1. Итак, внутренний цикл всегда выполняется n -1 раз при каждом выполнении внешнего цикла. Средняя сложность также равна 0(n2), если минимальный элемент исходно распределяется случайно между индексами 1,2,..., n.
Возможны различные усовершенствования; наиболее очевидное состоит в сохранении некоторой целой переменной, например последний, инициализируемой значением n — 1 и указывающей последний индекс, при котором была выполнена перестановка при последнем просмотре; тогда можно заменить n — 1 на последний в качестве верхней границы цикла для. Можно также просматривать массив во встречных направлениях, слева направо и справа налево.
Все это, однако, не меняет существенным образом сложность Пузырьковой Сортировки, которая в основе порочна своим “микроскопическим” подходом к массиву, когда каждый элемент всегда сравнивается только с непосредственно соседними. Пузырьковая Сортировка-это один из наихудших известных алгоритмов сортировки (и в то же время один из наиболее употребительных среди программистов). Заметим, например, что, если а[n] имеет минимальный ключ, а оставшаяся часть массива а[1: n — 1] исходно отсортирована, Пузырьковая Сортировка достигает своей максимальной сложности (n — 1)2! Когда необходим алгоритм простой сортировки, легко программируемый за несколько минут, следует обращаться к Сортировке Включением, которая всегда предпочтительнее Пузырьковой Сортировки.
Если желательно получить эффективный метод, оперирующий; обменами, нужно решительно отказаться от наивной идеи Пузырьковой Сортировки и обратиться к алгоритму Хоара, который дает один из лучших известных методов (если не наилучший). Его обычно называют Быстрой Сортировкой (Quicksort); этому алгоритму в той же мере хорошо подошло бы имя “Сортировки сегментацией”.
2.
Дата добавления: 2015-01-05; просмотров: 117 | Поможем написать вашу работу | Нарушение авторских прав |