Читайте также:
|
Написать программу, которая упорядочивает вещественный массив методом быстрой сортировки.
Идея алгоритма состоит в следующем. Применим к массиву так называемую процедуру разделения относительно среднего элемента. Вообще-то, в качестве «среднего» можно выбрать любой элемент массива, но для наглядности мы будем выбирать действительно, по возможности, средний по своему номеру элемент.
Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие, чем элемент, выбранный в качестве среднего, а в правой — бóльшие. Это достигается путем просмотра массива попеременно с обоих концов, при этом каждый элемент сравнивается с выбранным средним, и элементы, находящиеся в «неподходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте, т. е. его «судьба» определена и мы можем про него забыть. Далее процедуру разделения необходимо повторить отдельно для левой и правой части: в каждой части выбирается среднее, относительно которого она делится на две, и так далее.
Понятно, что одновременно процедура не может заниматься и левой, и правой частями, поэтому необходимо каким-то образом запомнить запрос на обработку одной из двух частей (например, правой), и заняться оставшейся частью (например, левой). Так продолжается до тех пор, пока не окажется, что очередная обрабатываемая часть содержит ровно один элемент. Тогда нужно вернуться к последнему из необработанных запросов, применить к нему все ту же процедуру разделения и так далее... В конце концов массив окажется полностью упорядочен.
Для хранения границ еще не упорядоченных частей массива более всего подходит структура данных, называемая стеком. Мы будем рассматривать «настоящие» стеки на девятом семинаре, а пока просто уловите идею. Представьте себе автобус, в котором не работают все двери, кроме передней. Все сидячие места сломаны, а в проходе между ними помещается только по одному человеку в ряд. Человек, который имел несчастье первым войти в этот автобус, сможет покинуть его только самым последним. Вот это и есть стек — «первым пришел, последним ушел». В качестве упражнения придумайте более привлекательные примеры стеков.
ПРИМЕЧАНИЕ Существует более простая реализация метода быстрой сортировки, основанная на рекурсии. Мы рассмотрим ее на седьмом семинаре.
В приведенной ниже программе стек реализуется в виде двух массивов stackr и stackl и одной переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива). Для этого алгоритма количество элементов в стеке не может превышать n, поэтому размер массивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке — уменьшается. Про данный способ реализации стека рассказывается в Учебнике на с. 126.
Ниже приведена программа, реализующая этот алгоритм.
#include <iostream.h>
#include <math.h>
int main(){
const int n = 20;
float arr[n], middle, temp;
int *stackl = new int [n], *stackr = new int [n], sp = 0;
int i, j, left, right;
cout << “Введите элементы массива: “;
for (i = 0; i < n; i++) cin >> arr[i]; // Сортировка
sp = 1; stackl[1] = 0; stackr[1] = n - 1; II 1
while (sp > 0) { //2
// Выборка из стека последнего запроса
left = stackl[sp]; // 3
right = stackr[sp]; // 4
sp--; // 5
while (left < right) { // 6
// Разделение {arr[left].. arr[right]}
i = left; j = right; // 7
middle = arr[(left + right) / 2]; // 8
while, (i < j) { // 9
while (arr[i] < middle) i++; // 10
while (middle < arr[j]) j--: // 11
if (i <= j) {
temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
i++: j--;
}
}
if (i < right) { // 12
// Запись в стек запроса из правой части sp++;
stackr[sp] = right;
}
right = j; //13
// Теперь left и right ограничивают левую часть
}
}
// Вывод результата
for (i = 0; i < n; i++) cout << arr[i] << ' ';
cout << endl;
return 0;
}
На каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, правая — в переменной right. Сначала фрагмент устанавливается размером с массив целиком (строка 1). В операторе 8 выбирается «средний» элемент фрагмента.
Для продвижения по массиву слева направо в цикле 10 используется переменная i, справа налево — переменная j (в цикле 11). Их начальные значения устанавливаются в операторе 7. После того, как оба счетчика «сойдутся» где-то в средней части массива, происходит выход из цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые границы левой части для сортировки на следующем шаге.
Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла 6, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3,4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.
Добавьте в программу подсчет количества итераций основного цикла. Прогоните программу несколько раз для массивов с большим количеством элементов[7] и сравните с аналогичной программой, реализующей метод выбора. Сделайте выводы.
Метод быстрой сортировки был предложен Ч. Хоаром. Впоследствии дотошный исследователь этого и других методов сортировки Д. Кнут (D. Knuth) установил, что размер стека может быть уменьшен до величины log2n, если после каждого появления двух частей, подлежащих дальнейшей обработке, более длинную часть откладывать на потом (помещать в стек), а более короткую обрабатывать немедленно. В качестве дополнительного упражнения напишите улучшенную версию программы, в которой реализована эта идея и размер стека уменьшен до log2n.
Быстрая сортировка является одним из лучших методов упорядочивания, однако существует целый ряд алгоритмов, которые предпочтительнее применять для данных, отвечающих определенным критериям. Советуем вам на досуге ознакомиться с этими алгоритмами. Выбор наиболее подходящего для каждого случая метода сортировки данных — показатель класса программиста.
Давайте повторим основные моменты этого лабораторного занятия.
1. Размерность не динамического массива может быть только константой или константным выражением. Рекомендуется задавать размерность с помощью именованной константы.
2. Элементы массивов нумеруются с нуля, поэтому максимальный номер элемента всегда на единицу меньше размерности.
3. Автоматический контроль выхода индекса за границы массива не производится, поэтому программист должен следить за этим самостоятельно.
4. Указатель — это переменная, в которой хранится адрес области памяти.
5. Имя массива является указателем на его нулевой элемент.
6. Обнуления динамической памяти при ее выделении не происходит. Инициализировать динамический массив нельзя.
7. Освобождение памяти, выделенной посредством new[ ], выполняется с помощью операции delete[].
8. Перед выходом локального указателя из области его действия необходимо освобождать связанную с ним динамическую память.
9. Если количество элементов, которые должны быть введены в программу, известно до ее выполнения, определяйте массив в операторе описания переменных (причем лучше как локальную переменную, чем как глобальную); если количество можно задать во время выполнения программы, но до ввода элементов, создавайте динамический массив; если нет, используйте линейный список или другую, динамическую структуру.
10. Алгоритмы сортировки массивов различаются по быстродействию, занимаемой памяти и области применения.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Для чего предназначены указатели?
2. Перечислите виды указателей в С++.
3. Является ли указатель самостоятельным типом?
4. Что содержит указатель на функцию и как он используется?
5. Что содержит указатель на объект?
6. В каких случаях применяется указатель на void?
7. Какие операции можно выполнить с указателями?
8. Для чего предназначены арифметические операции с указателями инкремент (++) и декремент (--)?
9. Что представляет собой ссылка?
10. Что называется массивом?
11. В чем состоит преимущество динамических массивов?
12. Какой может быть размерность динамического массива?
13. Как различаются алгоритмы сортировки массивов?
Дата добавления: 2015-07-11; просмотров: 94 | Нарушение авторских прав