}
Насколько эффективна такая сортировка? Все описанные ранее способы сортировки массивов имели порядок O(n2), то есть при увеличении в 10 раз длины массива время сортировки увеличивается в 100 раз. Можно показать, что Quicksort имеет в среднем порядок O(n · log n), что значительно лучше.
Чтобы почувствовать, что такое O(n · log n) и O(n2), посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.
Если считать, что числа в таблице соответствуют микросекундам, то для задачи с 1048476
элементами алгоритму со временем работы O(log n) потребуется 20 микросекунд, а алгоритму с временем работы O(n2) – более 12 дней.Однако, этому алгоритму присущи и недостатки. Все зависит от того, насколько удачным будет на каждом шаге выбор x. В идеальном случае мы должны всегда выбирать в качестве x медиану – такой элемент, что в данном диапазоне есть равное количество меньших и больших элементов. При этом каждый раз зона сортировки сокращается в два раза и требуется всего log n проходов, общее число сравнений равно n· log n. В самом худшем случае (если мы каждый раз наибольшее значение из данного диапазона) он имеет скорость O(n2).
|
|
Кроме того, этот алгоритм, как и все усовершенствованные методы сортировки, неэффективен при малых n. Иногда для сортировки коротких отрезков в него включают прямые методы сортировки.Ниже приведены результаты теста – время сортировки в секундах для разных наборов данных тремя способами (для процессора Pentium 120).
Таким образом, для массива размером 15000 элементов метод Quicksort более чем в 500 раз эффективнее, чем прямые методы.
Структуры
Что такое структуры?
Очень часто при обработке информации приходится работать с блоками, в которых присутствуют разные типы данных. Например, информация о книге в каталоге библиотеки включает в себя автора (символьная строка), название книги (тоже строка), год издания (целое число),количество страниц (целое число) и т.п.
Для хранения этой информации в памяти не подходит обычный массив, так как в массиве
все элементы должны быть одного типа. Конечно, можно использовать несколько массивов разных типов, но это не совсем удобно (желательно, чтобы все данные о книге находились в памяти в одном месте).
В современных языках программирования существует особый тип данных, который может включать в себя несколько элементов более простых (причем разных!) типов.
Структура – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры).
Одно из применений структур – организация различных баз данных, списков и т.п.