Иллюстрированный самоучитель по практике программирования

Быстрая сортировка на языке Java

Наиболее существенное изменение – это использование индексов left и right, поскольку в Java нет указателей на массивы.

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Быстрая сортировка на языке Java

Quicksort.sort использует cmp для сравнения двух объектов, как и раньше, вызывает swap для их обмена.

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Быстрая сортировка на языке Java

Генерация случайного номера происходит в функции rand, которая а возвращает случайное число в диапазоне с left по right включительно:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Быстрая сортировка на языке Java

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Быстрая сортировка на языке Java

Мы вычисляем абсолютное значение (используя функцию Math.abs), поскольку в Java генератор случайных чисел возвращает как положительные, так и отрицательные значения.

Функции sort, swap и rand, а также объект-генератор случайных чисел rgen являются членами класса Quicksort.

Наконец мы готовы написать вызов Quicksort.sort для сортировки массива типа String:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Быстрая сортировка на языке Java

Так вызывается sort с объектом сравнения строк, созданным для этой цели.

Упражнение 2.2
Наша реализация быстрой сортировки в Java делает несколько преобразований типов, сначала переводя исходные данные из их первоначального типа (вроде Integer) в Object, а затем обратно. Поэкспериментируйте с версией Quicksort.sort, которая использует конкретный тип при сортировке, и попробуйте вычислить, какие потери производительности вызываются преобразованием типов.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.