Алгоритмы и структуры данных на С++. Аксёнова Е.А - 61 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

5.4. Реализация быстрой сортировки 61
Рис. 5.2
образом. Иногда задают некоторую константу C так, чтобы массивы
длины меньше C сортировались простыми вставками.
5.4. Реализация быстрой сортировки
Рекурсивная реализация быстрой сортировки
Рассмотрим сначала параметризованную рекурсивную реализацию
быстрой сортировки. Тип элемента сортируемого массива stype пере-
дается в качестве параметра в функцию сортировки quick, которая
производит рекурсивный вызов функции qs(item,0,count-1), сорти-
рующей массив item, начиная с элемента с номером 0 до элемента с
номером count-1. В функции main сначала с помощью функции сор-
тировки quick сортируется массив символов и массив целых чисел, а
затем сортируется случайный массив целых чисел с помощью реализо-
ванной параметризованной функции quick и с помощью стандартной
функции qsort. Функция comp задает отношение порядка на множе-
стве сортируемых элементов массива. Сравнение времен сортировки
одного и того же массива чисел показывает, что параметризованная
функция выполняется намного быстрее, т. к. при вызове стандартной
функции qsort ей передается адрес функции comp, которая вызы-
вается большое количество раз. При параметризованной реализации
компилятор встраивает (inline) сравнение, получая выигрыш в ско-
рости.
#include<iostream.h>
#include<stdlib.h>
#include <stdio.h>
5.4.   Реализация быстрой сортировки                          61




                            Рис. 5.2


образом. Иногда задают некоторую константу C так, чтобы массивы
длины меньше C сортировались простыми вставками.


          5.4. Реализация быстрой сортировки
        Рекурсивная реализация быстрой сортировки
   Рассмотрим сначала параметризованную рекурсивную реализацию
быстрой сортировки. Тип элемента сортируемого массива stype пере-
дается в качестве параметра в функцию сортировки quick, которая
производит рекурсивный вызов функции qs(item,0,count-1), сорти-
рующей массив item, начиная с элемента с номером 0 до элемента с
номером count-1. В функции main сначала с помощью функции сор-
тировки quick сортируется массив символов и массив целых чисел, а
затем сортируется случайный массив целых чисел с помощью реализо-
ванной параметризованной функции quick и с помощью стандартной
функции qsort. Функция comp задает отношение порядка на множе-
стве сортируемых элементов массива. Сравнение времен сортировки
одного и того же массива чисел показывает, что параметризованная
функция выполняется намного быстрее, т. к. при вызове стандартной
функции qsort ей передается адрес функции comp, которая вызы-
вается большое количество раз. При параметризованной реализации
компилятор встраивает (inline) сравнение, получая выигрыш в ско-
рости.

#include
#include
#include

Страницы