Javenue logo

Javenue

Программирование на Java

Информационные технологии

Быстрая сортировка на Java (quick sort)

Алгоритм Quick Sort является одним из самых быстрых алгоритмов сортировки. Его среднее время выполнения - O(n log n). Quick Sort реализуется с помощью рекурсии.

В этой статье представлен демонстрационный пример алгоритма быстрой сортировки на Java.

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

А вот собственно и реализация на Java:

import java.util.Random;

public class QuickSortExample {
    public static int ARRAY_LENGTH = 30;
    private static int[] array = new int[ARRAY_LENGTH];
    private static Random generator = new Random();

    public static void initArray() {
        for (int i=0; i<ARRAY_LENGTH; i++) {
            array[i] = generator.nextInt(100);
        }
    }

    public static void printArray() {
        for (int i=0; i<ARRAY_LENGTH-1; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println(array[ARRAY_LENGTH-1]);
    }

    public static void quickSort() {
        int startIndex = 0;
        int endIndex = ARRAY_LENGTH - 1;
        doSort(startIndex, endIndex);
    }

    private static void doSort(int start, int end) {
        if (start >= end)
            return;
        int i = start, j = end;
        int cur = i - (i - j) / 2;
        while (i < j) {
            while (i < cur && (array[i] <= array[cur])) {
                i++;
            }
            while (j > cur && (array[cur] <= array[j])) {
                j--;
            }
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                if (i == cur)
                    cur = j;
                else if (j == cur)
                    cur = i;
            }
        }
        doSort(start, cur);
        doSort(cur+1, end);
    }

    public static void main(String[] args) {
        initArray();
        printArray();
        quickSort();
        printArray();
    }
}

Для наглядности я распечатываю строковое представление массива до и после сортировки.

Данная программа работает правильно, но наверняка ее можно немного оптимизировать.

Если у вас есть замечания или вопросы по поводу моей реализации алгоритма, буду рад выслушать вас.


Комментариев: 6

  Выйти

  * для публикации комментариев нужно  

Asf:

В качестве учебного примера неплохо.

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

Это описано в Лорин “Сортировка и алгоритмы сортировки”. Есть ли это в Кнуте - не помню.

Alexander:

Вот что хотел сказать: Надо поменять местами условия выхода из вот этих циклов

while (i меньше cur && (array[i] меньше_или_равно array[cur]))

while (j больше cur && (array[cur] меньше_или_равно array[j]))

чтоб стало

while ((array[i] меньше_или_равно array[cur]) && i меньше cur)

while ((array[cur] меньше_или_равно array[j]) && j больше cur)

т.к. && - ленивый оператор получим прирост скорости процентов на 20-25, особенно для больших значений ARRAY_LENGTH, без ущерба понятности алгоритма.

Stas:

Чтото я непонял смысл строки

int cur = i - (i - j) / 2;

Если j&rt;i то в скобке будет -, следно все это эквивалентно:

int cur =i+(j-i)/2;

не так ли? или в этом есть своя хитрость?

c0nst:

i - (i - j)/2 = i - i/2 + j/2 = i/2 + j/2 = (i + j)/2

Смысл в том, что для больших i и j может быть overflow, если их сумма больше Integer.MAX_VALUE. Соответственно среднее арифметическое может быть посчитано неправильно. А нам это ну никак не надо :).

MiddleZwei:

public static void printArray() { for (int i=0; i<ARRAY_LENGTH-1; i++) { System.out.print(array[i] + ", "); } System.out.println(array[ARRAY_LENGTH-1]); } Почему здесь в цикле i<ARRAY_LENGTH-1, а не i<ARRAY_LENGTH либо i<=ARRAY_LENGTH-1? Должно же вывести 30 элементов, а я вижу 29(с 0 по 28). Программа понимает все правильно и выводит 30 элементов. А вот я не понимаю.

alexey antonov:

MiddleZwei, отдельный .println(), после цикла, выводит элемент с индексом 29 с новой строки: System.out.println(array[ARRAY_LENGTH-1]); Я так понимаю, чтобы в конце не осталось: ", ". Только вот зачем тогда println() с переносом на следующую строку - очепятка наверное, просто print() нужен.