ПРИМЕР 8. Алгоритм быстрой сортировки

Ранее, был рассмотрен простой способ так называемой пузырьковой сортировки. В этом проекте предстоит реализовать один из самых лучших способов: быструю сортировку. Алгоритм быстрой сортировки был разработан Ч. Хоаром и назван его именем. На сегодняшний день это самый лучший универсальный алгоритм сортировки.

В данном проекте будет создана программа для сортировки символьного массива, но демонстрируемый подход может быть применен к сортировке любых объектов. Быстрая сортировка опирается на принцип разделения. Сначала выбирается опорное значение (так называемый компаранд), и массив разделяется на две части. Все элементы, которые больше или равны разделяемому компаранду, помещаются в одну часть массива, а те элементы, которые меньше компаранда, — в другую часть. Затем процесс рекурсивно повторяется для каждой оставшейся части до тех пор, пока массив не окажется отсортированным. Компаранд можно выбрать двумя способами: случайно либо вычислив среднее значение части элементов массива. Эффективность сортировки окажется оптимальной в том случае, когда компаранд выбран как раз посредине диапазона значений элементов, содержащихся в массиве, но зачастую выбрать такое значение непросто. Если же выбрать компаранд случайным образом, то вполне возможно, что он окажется на краю диапазона. Но и в этом случае алгоритм быстрой сортировки будет действовать правильно. В том варианте быстрой сортировки, который реализуется в данном проекте, в качестве компаранда выбирается элемент, находящийся посередине массива.

Последовательность действий

1. Создайте новый файл QSDemo.java.

2. Создайте сначала класс Quicksort, код которого приведен ниже.

// Простая версия класса Quicksort, реализующего быструю сортировку.

class Quicksort {

// организовать вызов конкретного метода быстрой сортировки

static void qsort(char items[]) {

qs(items, 0, items.length-1);

}

// Рекурсивная версия метода быстрой сортировки символов,

private static void qs(char items[], int left, int right) {

int i, j;

char X, y;

i = left; j = right;

X = items[(left+right)/2];

do {

while((items[i] < x) & & (i < right)) i++;

while((x < items[j]) & & (j > left)) j—;

if(i < = j) {

у = items[i];

items[i] = items[j];

items[j] = y;

i++; j—;

}

} while(i < = j);

if(left < j) qs(items, left, j);

if(i < right) qs(items, i, right);

}

}

Для упрощения интерфейса в классе Quicksort предоставляется метод qsort(), из которого вызывается метод qs(), фактически выполняющий сортировку. Такой подход позволяет выполнять сортировку, передавая методу лишь имя массива и не осуществляя первоначальное разделение. А поскольку метод qs() используется только в классе, он определяется как private.

3. Для того чтобы воспользоваться классом Quicksort, достаточно вызвать метод Quicksort.qsort(). Этот метод определен как static, и поэтому для его вызова достаточно указать имя класса, а создавать объект не обязательно. По завершении работы этого метода массив будет отсортирован. Данная версия программы работает только с символьными массивами, но вы можете адаптировать ее для сортировки массивов любого типа.

4. Ниже приведен весь исходный код программы, демонстрирующей применение класса Quicksort.

// Простая версия класса Quicksort, реализующего быструю сортировку,

class Quicksort {

// организовать вызов конкретного метода быстрой сортировки

static void qsort(char items[]) {

qs(items, 0, items.length-1);

}

// Рекурсивная версия метода быстрой сортировки символов,

private static void qs(char items[], int left, int right) {

int i, j;

char X, y;

i = left; j = right;

X = items[(left+right)/2];

do {

while((items[i] < x) & & (i < right)) i++;

while((x < items[j]) & & (j > left)) j—;

if(i < = j) {

у = items[i];

items[i] = items[j];

items[j] = y;

i++; j —;

}

} while (i < = j);

if(left < j) qs(items, left, j);

if(i < right) qs(items, i, right);

}

}

class QSDemo {

public static void main(String args[]) {

char a[] = { 'd', 'X', 'a', 'r', 'p', 'j', 'i' };

int i;

System.out.print(" Original array: ");

for(i=0; i < a.length; i++)

System, out.vprint (a [i]);

System.out.println();

// отсортировать массив

Quicksort.qsort(a);

System.out.print(" Sorted array: ");

for(i=0; i < a.length; i++)

System.out.print(a[i]);

}

}

Контрольные вопросы

1. В чем отличие класса от объекта?

2. Как определяется класс?

3. Чью собственную копию содержит каждый объект?

4. Покажите, как объявить объект counter класса MyCounter, используя два отдельных оператора.

5. Как должен быть объявлен метод myMeth, принимающий два параметра, а и b, типа int и возвращающий значение типа double?

6. Как должно завершаться выполнение метода, возвращающего некоторое значение?

7. Каким должно быть имя конструктора?

8. Какие действия выполняет оператор new?

9. Что такое «сборка мусора» и какие действия она выполняет? Зачем нужен метод finalize()?

10. Что означает ключевое слово this?

11. Может ли конструктор иметь один или несколько параметров?

12. Если метод не возвращает значения, то как следует объявить тип этого метода?

13. Покажите два способа объявления одномерного массива, состоящего из 12 элементов типа double.

14. Покажите, как инициализировать одномерный массив целочисленными значениями от 1 до 5.

15. В чем отличие методов indexOf () и lastlndexOf () из класса String?

16. Все символьные строки являются объектами типа String. Покажите, как вызываются методы length () и charAt () для строкового литерала " I like Java".

17. Можно ли применять поразрядные операторы к значениям типа double?

18. Перепишите приведенную ниже последовательность операторов, воспользовавшись оператором?.

if(x < 0) у = 10;

else у = 20;

19. В приведенном ниже фрагменте кода содержится знак &. Какой оператор он обозначает: поразрядный или логический? Обоснуйте свой ответ.

boolean а, b;

//...

if (а & b)...

20. Является ли ошибкой превышение верхней границы массива? Является ли ошибкой использование отрицательных значений для доступа к элементам массива?

21. Как обозначается оператор сдвига вправо без знака?

22. В примере №3 была реализована пузырьковая сортировка. Можно ли в программе из этого примера заменить обычный цикл for его разновидностью for-each? Если нельзя, то почему?

23. Можно ли управлять оператором switch с помощью объектов типа String?

24. Допустим, имеется следующий фрагмент кода:

class X {

private int count;

Является ли допустимым приведенный ниже фрагмент кода?

class Y {

public static void main(String args[]) {

X ob = new X ();

ob.count = 10;

25. Допустим, имеется следующий класс:

class Test {

int а;

Test(int i) { a = i; }

}

Напишите метод swap(), реализующий обмен содержимым между двумя объектами типа Test, на которые ссылаются две переменные данного типа.

26. Правильно ли написан следующий фрагмент кода?

class X {

int meth(int а, int b) {... }

String meth(int a, int b) {... }

27. Допустим, все объекты класса должны совместно пользоваться одной и той же переменной. Как объявить такую переменную?

28. Для чего может понадобиться статический блок?

29. Что такое внутренний класс?

30. Допустим, требуется член класса, к которому могут обращаться только другие члены этого же класса. Какой модификатор доступа следует использовать в его объявлении?

31. Можно ли перегружать метод с аргументами переменной длины?

32. Приведите пример неоднозначного вызова перегружаемого метода с переменным числом аргументов.