Отсортировать по возрастанию числовой массив обменами, выбором, вставками, пузырьком и быстрой сортировкой. Получить зависимости временных затрат от размера массива. Временные затраты оценивать количеством сравнений и количеством обменов элементов массива. Сортировку выполнять на месте исходного массива.
СОРТИРОВКА ОБМЕНАМИ
Выполняется за n-1 проходов, где n – размер массива. В первом проходе первый элемент массива (с индексом 0) сравнивается с остальными элементами массива (с индексами 1…n-1) и, если предшествующий элемент больше последующего, они меняются местами. В последнем проходе сравниваются предпоследний и последний элементы массива. Следовательно, в каждом проходе количество сравнений фиксировано. Общее количество сравнений за сортировку равно n(n-1)/2.
Количество обменов зависит от состояния исходного массива. Если массив уже отсортирован, то обменов не будет. Это наилучший случай с точки зрения затрат машинного времени. Наихудший случай – при пересортировке массива, когда исходный массив отсортирован по убыванию. В этом случае каждое сравнение сопровождается обменом и, следовательно, количество обменов за сортировку равно n(n-1)/2.
СОРТИРОВКА ВЫБОРОМ
Эта сортировка требует также n-1 проходов. В первом проходе сравнениями первого элемента с остальными находят минимальный элемент и обменом помещают его на место первого элемента. В последнем проходе сравниваются предпоследний и последний элементы массива. Следовательно, в каждом проходе количество сравнений фиксировано. Общее количество сравнений за сортировку равно n(n-1)/2.
Число обменов всегда один на проход, следовательно, сортировка требует n-1 обменов. Наилучшего и наихудшего случаев не существует.
СОРТИРОВКА ВСТАВКАМИ
Выполняется за n-1 проходов. В первом проходе второй элемент массива (с индексом 1) сравнивается с первым элементом массива и, если второй оказывается меньше первого, первый сдвигается на место второго, а второй вставляется на место первого. В последнем проходе последний элемент массива сравнивается с предшествующими, начиная с предпоследнего, и вставляется между элементами, предыдущий из которых меньше, а последующий – больше последнего элемента. Среднее количество сравнений за сортировку - n(n-1)/4. Наилучший случай соответствует уже отсортированному массиву, когда количество сравнений равно n-1. Наихудший случай имеет место при пересортировке массива, при этом количество сравнений равно n(n-1)/2.
Обменов при сортировке вставками нет.
СОРТИРОВКА ПУЗЫРЬКОМ
В отличие от сортировки обменами, здесь сравниваются только соседние элементы и, если они стоят неправильно, меняются местами. В первом проходе сравниваются с соседним справа элементы с первого до предпоследнего. При этом сохраняется индекс первого из участвующих в последнем обмене элементов, что исключает избыточные просмотры массива. В следующем проходе просматривается часть массива с первого элемента по элемент с сохраненным индексом. Наилучший случай – массив уже отсортирован и нужен всего один проход с n-1 сравнениями. Наихудший случай – при пересортировке, когда потребуется n-1 проход с n(n-1)/2 сравнениями и n(n-1)/2 обменами.
БЫСТРАЯ СОРТИРОВКА
Быстрая сортировка содержит две фазы: сканирования и рекурсивную. На фазе сканирования в исходном массиве находят центральный по индексу элемент и массив разбивается на два подмассива – нижний и верхний. В нижний помещают элементы, меньшие или равные центральному, а в верхний – большие. Для этого нижний подмассив сканируют в направлении увеличения, а верхний – в направлении уменьшения индекса. Элементы, оказавшиеся не в своих подмассивах, меняются местами. Затем переходят к рекурсивной фазе, где описанным выше способом обрабатывают получаемые подмассивы, пока в них не окажется по одному элементу.
Наилучший случай соответствует отсортированному массиву с четным количеством элементов, когда число сравнений равно . При пересортировке число сравнений практически такое же.
В наихудшем случае центральный элемент все время попадает в одноэлементный подмассив, а все остальные элементы остаются во втором подмассиве. Это происходит тогда, когда центральным всегда оказывается наименьший элемент. Здесь общее число сравнений равно n(n+1)/2-1. Однако этот случай маловероятен на практике.
РЕКУРСИВНЫЕ ФУНКЦИИ
В программировании рекурсия – вызов функции из этой же функции (простая рекурсия) или через другие функции (сложная рекурсия). Количество вложенных вызовов рекурсивной функции называют глубиной рекурсии. Рекурсивные функции реализуют рекурсивные алгоритмы.
Из вышеизложенного следует, что алгоритмы сортировок по существу являются рекурсивными алгоритмами, и поэтому сортировки естественно кодировать рекурсивными функциями. Однако большая глубина рекурсии приводит к переполнению стека, что является основным недостатком рекурсивных алгоритмов. Поэтому рекурсивные функции годятся для сортировок небольших по размеру массивов. Поскольку на практике обычно требуется сортировать данные больших объемов, то переходят к использованию итерационных алгоритмов, реализуемых циклами.
Приведем рекурсивные функции для указанных выше сортировок по возрастанию массива a длиной n. В приводимых функциях: swap() – вызов функции обмена, obm и sr – количество обменов и сравнений соответственно.
int get_sr() const; //получение количества сравнений
int get_obm() const; //получение количества обменов
~array() {delete [] a;} //деструктор
private:
int* a; //указатель для формирования массива
int n; //размер массива
int sr; //количество сравнений
int obm; //количество обменов
};
Проектирование приложения.
Выбор, размещение и задание свойств компонентов.
Коды классов, функций и обработчиков событий
1.Сохраните модуль формы под именем LR_3, а проект – под именем PR_LR_3.По окончании проектирования все визуальные и невизуальные компоненты, имеющиеся в приложении, будут отображены в Дереве Объектов, представленном на рис.3.1,2,3,4. Дерево Объектов показывает самые различные связи между компонентами, например: соотношение родительских и дочерних компонентов, связь компонентов через их свойства и т.п.
2.Расположение компонентов на форме, а также значения некоторых свойств, устанавливаемых в компонентах по умолчанию, показаны на рис.3.5,6,7. Использование новых компонентов сопровождается необходимыми пояснениями.
3.Следовательно, на форму нужно перенести:
· со страницы Стандарт - компонент MainMenu1 - главное меню, пять компонентов PopupMenu1,.,5 – контекстных всплывающих меню, три панели общего назначения GroupBox1,2,3 (в свойство Caption впишите соответственно параметры массивов, размеры, диапазон чисел), причем на панели GroupBox1 нужно разместить панели GroupBox2 и GroupBox3, на панели GroupBox2 – три метки Label1,2,3 (мин, макс, шаг(d)), на панели GroupBox3 – две метки Label4,5 (мин, макс) и на форму - две метки Label6,7 (размер выводимого массива, шаг(t) вывода в таблицы), ниже - панель Panel1;
Рис.3.1 – 1-я часть дерева объектов Рис.3.2 – 2-я часть дерева объектов
· со страницы Примеры – семь компонентов ввода целых чисел – CSpinEdit1,.,7, из них три компонента (CSpinEdit1,2,3) помещаются на панель GroupBox2, два (CSpinEdit4,5) – на панель GroupBox3, и еще два (CSpinEdit4,5) – непосредственно на форму;
· со страницы Дополнительно - управляющую кнопку с пиктограммой BitBtn1;
· со страницы Win32 - многостраничную панель – компонент PageControl1 и задать на ней семь страниц с надписями массивы,
Рис.3.3 – 3-я часть дерева объектов Рис.3.4 – 4-я часть дерева объектов
· на страницу массивы панели PageControl1 со страницы Стандарт перенесите компонент Memo1;
· на страницу таблицы панели PageControl1 со страницы Дополнительно перенесите два компонента StringGrid1,2 а над ними расположите две метки Label8,9 (со страницы Стандарт) с надписями сравнения, обмены, а на каждую из остальных пяти страниц панели PageControl1 со страниц Additional и Дополнительно перенесите по компоненту Chart и Image; со страницы Win32 - компонент ProgressBar1.
4.Первым из новых компонентов является главное меню MainMenu – необходимый компонент интерфейса. Компонент MainMenu является невизуальным компонентом, т.е. место его размещения на форме в процессе проектирования не имеет значения для пользователя – во время выполнения он увидит не сам компонент, а только меню, сгенерированное компонентом. Главное меню для разрабатываемого приложения во время проектирования видно на форме (рис.3.5,6,7), а во время выполнения - представлено на рис.3.8. Основное свойство компонента MainMenu – Items. Его заполнение производится с помощью Конструктора Меню, вызываемого двойным щелчком на компоненте или нажатием кнопки с многоточием рядом со свойством Items в окне Инспектора Объектов. При работе в окне Конструктора Меню вводят новые разделы (подразделы) и помещают их в нужное место. При выборе нужного раздела (щелчком на нем) в Инспекторе Объектов появится множество свойств данного раздела. Свойство Caption обозначает надпись раздела (файл, сортировки и т. д.) или подраздела (открыть все графики,…, циклами). Свойство Name задает имя объекта, соответствующее разделу меню. Среда задает имена по умолчанию – N1, N2, N3 и т.д. Рекомендуется давать этим объектам осмысленные имена – здесь: file, sort, rec, rep, help, exit. Для каждого раздела (в нашем случае – для раздела сортировки) может быть установлено во время проектирования или программно во время выполнения свойство Enabled (доступен). Установите Enabled=false (недоступен), тогда раздел будет изображаться серой надписью и не будет реагировать на щелчок пользователя. Основное событие раздела – OnClick, возникающее при щелчке пользователя на разделе. В проектируемом приложении в обработчиках щелчков размещены алгоритмы, соответствующие названиям разделов (подразделов). Что же касается подраздела циклами, то здесь студент должен самостоятельно разработать алгоритмы сортировок с помощью циклов (кроме быстрой сортировки) и написать код с последующей отладкой и получением графически представляемых зависимостей.
5.Вторым новым компонентом является панель общего назначения GroupBox, которая имеет встроенную рамку с надписью (параметры массивов, размеры, диапазон чисел) и используется для выделения на форме группы функционально объединенных компонентов.
6.Третьим новым компонентом является управляющая кнопка BitBtn1 с пиктограммой. Изображение на этой кнопке задается свойством Glyph. Выделите кнопку BitBtn1. При нажатии кнопки с многоточием в строке свойства Glyph в Инспекторе Объектов вызывается окно Редактор картинки. Нажав в нем кнопку Загрузить, переходят в окно открытия файла рисунка Загрузить картинку и выбирают файл битовой матрицы .bmp, содержащей желаемое изображение. Большое количество изображений для кнопок расположено в папке …Program Files\Common Files\Borland Shared\Images\Buttons. Выбрав файл vcrplay, нажмите кнопку Открыть, а в окне Редактор картинки нажмите кнопку OK. Выбранное изображение появится на кнопке BitBtn1 левее надписи НАЧАТЬ (значение свойства Caption). В обработчике щелчка на кнопке НАЧАТЬ (BitBtn1Click - см. код файла реализации) выполняется ряд подготовительных операций для выполнения сортировок и представления результатов. Перечислим эти операции.
· Очистка окна редактирования Memo1, в которое выводятся исходные и отсортированные массивы задаваемого размера.
· Очистка расположенной выше кнопки панели Panel1, в которую выводятся сообщения о некоторых исключительных ситуациях.
· Очистка таблиц StringGrid1,2 и вывод в таблицу названий столбцов.
· Очистка графиков Chart1,..,5.
· Установка начального значения позиции компонента ProgressBar1 – индикатора хода процесса сортировок.
Рис.3.5 – форма по окончании проектирования (вид 1)
Рис.3.6 – форма по окончании проектирования (вид 2)
· Считывание во вспомогательные переменные параметров сортируемых массивов, задаваемых как значения свойств компонентов CSpinEdit1,..,7.
6.Теперь остановимся на компоненте PageControl1 – многостраничной панели. Здесь она имеет 7 страниц: на первую – выводятся массивы, на вторую – таблицы, на остальные пять – графики, по способу сортировки. На каждой из пяти последних страниц размещены по одному компоненту Chart и Image, причем в первый компонент (Chart) график выводится в процессе сортировки, а во второй (Image)– из файла. Размеры компонентов – равные.
7.Для удобства работы с приложением предусмотрены два способа сохранения графиков в файле и вывода графиков из файла: всех сразу, через разделы главного меню открыть все графики, сохранить все графики, и отдельно, по способам сортировки, с помощью пяти компонентов PopupMenu – контекстных всплывающих меню. Они имеют по два раздела, например, сохранить графики (обменами), открыть графики (обменами). В свойство PopupMenu компонента Chart, которое по умолчанию пусто, заносится имя того компонента PopupMenu1,..,5, с которым он будет связан.
Рис.3.7 – форма по окончании проектирования (вид 3)
Рис.3.8 – главное меню
Тестирование и использование приложения
1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.
2.Для тестирования приложения с параметрами массива, заданными по умолчанию (рис.3.5), щелкните на кнопке НАЧАТЬ, а затем – в главном меню на разделе сортировки и подразделе рекурсивными функциями. Проанализируйте полученные результаты, выведенные на страницы массивы, таблицы, графики многостраничной панели. Убедитесь в выполнении команд файл/сохранить все графики и файл/открыть все графики.
3.По коду обработчика щелчка на кнопке НАЧАТЬ установите исключительные ситуации, обрабатываемые приложением. Смоделируйте эти ситуации.
4.Убедитесь в действенности контекстных всплывающих меню.
5.Увеличивая размер исходного массива, получите сообщение о переполнении стека: ……‘Stack overflow’…… . Для выхода из режима выполнения введите команду Запуск/Сброс программы. Затем увеличьте размер стека до максимально возможного последовательностью действий Проект/Опции/Компоновщик/Макс.размер_стека. После указания максимально возможного размера стека в поле Макс. размер стека можно будет сортировать всеми методами массивы размерами до 1000. Убедитесь в этом. Проанализируйте полученные результаты.
6.Разработайте алгоритмы сортировок с помощью циклов (кроме быстрой сортировки) и напишите код для подраздела циклами с последующей отладкой и получением графически представляемых зависимостей, увеличив не менее чем на порядок размер сортируемых массивов и диапазон значений элементов массивов. Объясните полученные результаты.
7.Для завершения работы щелкните на разделе меню выход и выйдите из среды Builder.
. При пересортировке число сравнений практически такое же.
