double arrow

QuickSort ( A, i, to ); // сортируем правую часть

}

Насколько эффективна такая сортировка? Все описанные ранее способы сортировки массивов имели порядок 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 проходов, общее число сравнений равно log n. В самом худшем случае (если мы каждый раз наибольшее значение из данного диапазона) он имеет скорость O(n2).

Кроме того, этот алгоритм, как и все усовершенствованные методы сортировки, неэффективен при малых n. Иногда для сортировки коротких отрезков в него включают прямые методы сортировки.Ниже приведены результаты теста – время сортировки в секундах для разных наборов данных тремя способами (для процессора Pentium 120).

Таким образом, для массива размером 15000 элементов метод Quicksort более чем в 500 раз эффективнее, чем прямые методы.

Структуры

Что такое структуры?

Очень часто при обработке информации приходится работать с блоками, в которых присутствуют разные типы данных. Например, информация о книге в каталоге библиотеки включает в себя автора (символьная строка), название книги (тоже строка), год издания (целое число),количество страниц (целое число) и т.п.

Для хранения этой информации в памяти не подходит обычный массив, так как в массиве

все элементы должны быть одного типа. Конечно, можно использовать несколько массивов разных типов, но это не совсем удобно (желательно, чтобы все данные о книге находились в памяти в одном месте).

В современных языках программирования существует особый тип данных, который может включать в себя несколько элементов более простых (причем разных!) типов.

Структура – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры).

Одно из применений структур – организация различных баз данных, списков и т.п.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: