Быстрая сортировка. Метод предложен Ч. Э. Р. Хоаром в 1962 году. Эффективность метода достаточно высокая, кроме специально подобранных данных, поэтому автор назвал его «быстрой сортировкой».
Идея метода. В исходном массиве А выбирается некоторый элемент X (барьерный элемент). Нашей целью является запись X «на свое место» в массиве, пусть это будет место k, такое, что слева от X были элементы массива, меньшие или равные X, а справа – элементы массива, большие X, т.е. массив А будет иметь вид: (A[1], A[2], …, A[k-1]), A[k] (X), (A[k+1], …, A[n]).
В результате элемент A[k] находится на своем месте и исходный массив А разделен на две неупорядоченные части, барьером между которыми является элемент A[k]. Дальнейшие действия очевидны- независимо сортировать полученные части по той же логике до тех пор, пока не останутся части массива, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.
Пример. Исходный массив состоит из 8 элементов: 8 12 3 7 19 11 4 16. В качестве барьерного элемента возьмем средний элемент массива (7). Произведя необходимые перестановки, получим: (4 3) 7 (12 19 11 8 16), элемент 7 находится на своем месте. Продолжаем сортировку.
Левая часть: (3) 4 7 (12 19 11 8 16)
3 4 7 (12 19 11 8 16)
Правая часть:
3 4 7 (8) 11 (19 12 16)
3 4 7 8 11 (19 12 16)
3 4 7 8 11 12 (19 16)
3 4 7 8 11 12 (16) 19
3 4 7 8 11 12 16 19
Из вышеизложенного описания явно просматривается рекурсивная схема реализации, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.
4. Практические указания:
4.1 Создайте консольное приложение с реализацией всех видов сортировок.
4.2 Напишите программу для решения задачи:
1 вариант. Массив М, состоящий из 30 элементов, переформировать так, чтобы вначале стояли все положительные а равные нулю элементы в порядке убывания их значений, а затем все отрицательные элементы в порядке возрастания их значений.
2 вариант. Дан массив целых чисел осуществить сортировку четных элементов массива.
3 вариант. Дан массив целых чисел осуществить сортировку элементов массива записанных на нечетных местах.
4 вариант. Дан массив целых чисел осуществить сортировку отрицательных элементов массива.
5 вариант. Дан массив целых чисел осуществить сортировку положительных элементов массива.
6 вариант. В упорядоченный по возрастанию значений элементов массив М, состоящий из целых чисел, необходимо вставить число, не нарушив упорядоченности исходного массива.
7 вариант. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все нечетные аргументы, а после них все четные.
8 вариант. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все четные аргументы, а после них все нечетные.
9 вариант. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все положительные аргументы, а после них все отрицательные.
10 вариант. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все отрицательные аргументы, а после них все положительные.
5. Контрольные вопросы
5.1 Какие методы сортировки вы знаете?
5.2 В чем суть их различий?
6. Список рекомендуемой литературы:
Основная литература:
1. Немцова Т.И. Програмиирование на языке выского уровня. Программирование на языке Object Pascal: учеб. пособие /Т.И. Немцова, С.Ю. Голова, И.В. Абрамова. – М.: ФОРУМ: ИНФРА – М, 2012. – 496 с.
2. Овечкин Г.В. Компьютерное моделирование: учебник для студ. учреждений сред. проф. образования / Г.В. Овечкин.- М.: Издательский центр «Академия», 2015.-224с.
3. Немцова, Т. И. Программирование на языке высокого уровня. Программирование на языке С++: учеб. пособие / Т. И. Немцова, С. Ю. Голова, А. И. Терентьев. - М.: ФОРУМ: ИНФРА-М, 2012. - 512 с.: ил. + CD.
4. Гуриков, С. Р. Введение в программирование на языке Visual C#: учеб. пособие / С. Р. Гуриков. - М.: ФОРУМ: ИНФРА-М, 2013. - 448 с.
Дополнительная литература:
5. Рао Сиддхартха Освой самостоятельно С++ за 21 день, 7 изд.: Пер с англ.-М.: ООО «И.Д.Вильямс», 2013 – 688 с.: ил. – Парал.тит.англ.
6. Голицына О.Л. Программное обеспечение: учеб. пособие для среднего профессионального образования-М.:ФОРУМ;ИНФРА-М,2006.-432 с.
7. Виллемер А. Программирование на С++/А. Виллемер;[пер. с нем. М.А.Райтман].-М.:Эксмо,2013.-528с.+CD.-(Мировой компьютерный бестселлер).
8. Культин Н.Б. Microsoft Visual C++ в задачах и примерах.- СПб.: БХВ-Петербург,2010.-272 с.:ил.+CD-ROM.
9. Партыка Т.Л. Операционные системы, среды и оболочки: учеб. пособие для студ. учреждений сред. проф. Образования/ Т.Л. Партыка, И.И. Попов. – 3-е изд., перераб. и доп. – М.: ФОРУМ, 2010. – 543 с.
10. Окулов С.М. Основы программирования: учебное пособие.- М.:БИНОМ. Лаборатория знаний, 2010.- 440 с.
11. Голицына О.Л. Основы алгоритмизации и программирования: учеб. пособие для сред. проф. образования.- М: ФОРУМ; ИНФРА-М,2005.-432 с.
12. Рихтер Дж. Программирование приложений для Microsoft Windows /Пер. с англ. – M.: Microsoft Press, 2003. – C.48-313.