Быстрая сортировка QuickSort в Java

Коротко: быстрая сортировка (quicksort) работает по принципу "разделяй и властвуй". В массиве выбирают опорный элемент, переставляют элементы так, чтобы меньшие оказались слева от него, а большие справа, и затем тем же способом сортируют обе половины. В среднем это O(n log n), в худшем случае O(n²). Массив сортируется на месте, но порядок равных элементов алгоритм не сохраняет. Алгоритмов сортировки в программировании придумали и реализовали огромное количество. Их главные отличия между собой это эффективность (то есть во времени исполнения и использовании памяти устройства) и простоте реализации. Есть и другие важные факторы, такие как стабильность сортировки (сохраняется ли порядок равных элементов), адаптивность (эффективность на частично отсортированных данных), и масштабируемость (эффективность на больших объемах данных). В этой статье мы рассмотрим алгоритм быстрой сортировки или Quick sort, а его главный соперник разобран в статье про сортировку слиянием.

Кратко

• Быстрая сортировка делит массив опорным элементом на две части и рекурсивно повторяет то же с каждой из них.
• Опорным может быть последний, средний, случайный элемент или медиана из трех: от этого выбора зависит, попадете вы в худший случай или нет.
• Средняя сложность O(n log n), худшая O(n²). Худший случай дает уже отсортированный массив с крайним опорным элементом.
• Отдельного массива алгоритму не нужно, память уходит только на стек рекурсии: в среднем O(log n), в худшем O(n).
• Сортировка нестабильная: равные элементы могут поменяться местами.
• Тот же алгоритм уже встроен в язык: Arrays.sort для примитивов это двухопорный quicksort.

Суть алгоритма

Quicksort это достаточно эффективный алгоритм. Его реализация новичку может показаться несколько сложной, хотя сам принцип, заложенный в его основу очень прост и стар, как мир. Это “разделяй и властвуй”. Вот как он работает.

1. Для начала нужно выбрать опорный элемент в массиве. Чаще всего это средний элемент, но также можно выбрать “опору” случайным образом. Проще всего просто выбрать первый или последний элемент.
2. Начинаем разделение. Делим массив на две части таким образом, что элементы, которые меньше опорного, перемещаются влево от него, а те, которые больше, вправо.
3. Повторение процесса разделения. Повторяем процесс рекурсивно для левой и правой части массива до тех пор, пока каждая часть не будет состоять из одного элемента.

Перед реализацией алгоритма

Прежде, чем начинать программировать, обратите внимание на пару важных моментов: Граничные условия. Будьте осторожны с границами массива во избежание ошибок выхода за пределы массива. Иными словами перед разделением или рекурсивным вызовом Quicksort убедитесь, что диапазон (верхний и нижний индексы, low и high) валиден. Это означает, что low должен быть меньше high, и оба индекса должны находиться в пределах границ массива. Стек переполнения. Из-за рекурсии есть риск переполнения стека вызовов, особенно на больших массивах. Как этого избежать? Например сначала рекурсивно обрабатывать меньший из двух подмассивов, полученных после разделения. Выбор опорного элемента (pivot) в алгоритме Quicksort существенно влияет на его производительность. Вот несколько распространенных способов выбора опорного элемента.

• Первый или последний элемент. Самый простой способ, но он может привести к худшей производительности, особенно если массив уже частично или полностью отсортирован.
• Выбор среднего элемента массива как опорного может помочь избежать худших сценариев производительности в некоторых случаях. Это метод вычисления индекса среднего элемента как (low + high) / 2.
• Еще один подход это медиана из трех элементов (обычно первый, средний и последний) массива. Этот метод обычно обеспечивает более сбалансированное разделение, чем простой выбор первого или последнего элемента.
• Выбор случайного элемента в качестве опорного может снизить вероятность худшего случая производительности, особенно для массивов, которые могут быть уже отсортированы или иметь определенную структуру.
• Для очень больших массивов может использоваться метод называемый "медиана медиан". Это сложный метод, по которому опорный элемент выбирается более сбалансировано, но он требует дополнительных вычислений.

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

Реализация алгоритма быстрой сортировки

Теперь давайте реализуем быструю сортировку на Java.

import java.util.Arrays;

public class QuickSort {
   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));
   }

   public static void quickSort(int[] arr, int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);

           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }

   private static int partition(int[] arr, int low, int high) {
       int pivot = arr[high];
       int i = (low - 1);
       for (int j = low; j < high; j++) {
           if (arr[j] < pivot) {
               i++;

               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }

       int temp = arr[i + 1];
       arr[i + 1] = arr[high];
       arr[high] = temp;

       return i + 1;
   }
}

Вывод программы следующий: Давайте разберемся, что тут происходит. Рекурсивный метод quickSort на вход принимает массив, а также нижний (low) и верхний (high) индексы. Если low меньше high, происходит разделение массива с помощью метода partition, а затем рекурсивно вызывается quickSort для левой и правой части. Метод partition определяет положение опорного элемента (здесь выбран последний элемент массива) и переставляет элементы так, чтобы элементы меньше опорного находились слева от него, а большие справа. Этот метод возвращает индекс опорного элемента после перестановки. Теперь давайте изменим реализацию алгоритма таким образом, чтобы в качестве опорного элемента был выбран средний элемент массива.

import java.util.Arrays;

public class QuickSort {
   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));
   }

   public static void quickSort(int[] arr, int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);

           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }

   private static int partition(int[] arr, int low, int high) {
       // Выбор среднего элемента в качестве опорного
       int middle = low + (high - low) / 2;
       int pivot = arr[middle];

       // Обмен опорного элемента с последним, чтобы использовать существующую логику
       int temp = arr[middle];
       arr[middle] = arr[high];
       arr[high] = temp;

       int i = (low - 1);
       for (int j = low; j < high; j++) {
           if (arr[j] < pivot) {
               i++;

               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }

       temp = arr[i + 1];
       arr[i + 1] = arr[high];
       arr[high] = temp;

       return i + 1;
   }
}

Метод, реализованный таким образом может работать быстрее, чем такой же метод, но с последним элементом в качестве опорного на определенных наборах данных, особенно на частично отсортированных массивах.

Итеративная реализация алгоритма быстрой сортировки

Быстрая сортировка в Java-реализации может быть не только рекурсивной, но и итеративной. Давайте попробуем реализовать такой вариант метода. В этой реализации используется стек для отслеживания индексов подмассивов, которые нужно отсортировать.

import java.util.Arrays;
import java.util.Stack;

public class QuickSort {
   static void quickSort(int[] arr, int l, int h) {
       if (arr == null || arr.length == 0)
           return;

       if (l >= h)
           return;

       Stack<Integer> stack = new Stack<>();
       stack.push(l);
       stack.push(h);

       while (!stack.isEmpty()) {
           h = stack.pop();
           l = stack.pop();

           int pivotIndex = partition(arr, l, h);

           if (pivotIndex - 1 > l) {
               stack.push(l);
               stack.push(pivotIndex - 1);
           }

           if (pivotIndex + 1 < h) {
               stack.push(pivotIndex + 1);
               stack.push(h);
           }
       }
   }

   private static int partition(int[] arr, int low, int high) {
       int pivot = arr[high];
       int i = low;
       for (int j = low; j < high; j++) {
           if (arr[j] <= pivot) {
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               i++;
           }
       }

       int temp = arr[i];
       arr[i] = arr[high];
       arr[high] = temp;
       return i;
   }

   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));
   }
}

Вывод программы будет такой же, как и в предыдущих случаях.

Сложность алгоритма быстрой сортировки

Сложность алгоритма это мера оценки его эффективности. Сложность часто выражается в терминах "O-нотации" (Big O notation), которая описывает худший случай поведения алгоритма с увеличением размера входных данных. Она предоставляет общее представление о том, как масштабируется производительность алгоритма при увеличении размера входных данных. Важно понимать, что O-нотация не дает точных временных значений выполнения, а скорее показывает тенденцию изменения производительности. Сложность алгоритма Quicksort зависит от многих факторов, включая выбор опорного элемента и распределение входных данных. В общем случае свойства быстрой сортировки такие: Писать quicksort вручную приходится в основном ради учебы и собеседований: в стандартной библиотеке он уже есть. В документации класса Arrays прямо сказано, что Arrays.sort для массивов примитивов это двухопорный quicksort авторства Владимира Ярославского, Джона Бентли и Джошуа Блоха, который на реальных данных обычно быстрее классической однопорной реализации. А вот массивы объектов тот же класс сортирует уже не quicksort, а TimSort: там нужна стабильность.

Вопросы и ответы

Как работает быстрая сортировка?

В массиве выбирается опорный элемент. Дальше элементы переставляются так, чтобы все меньшие опорного оказались слева от него, а все большие справа: после этого опорный элемент стоит на своем окончательном месте. Затем та же процедура рекурсивно повторяется для левой и правой частей, пока в части не останется один элемент.

Какая сложность у быстрой сортировки и когда наступает худший случай?

В среднем и в лучшем случае O(n log n), в худшем O(n²). Худший случай наступает, когда разделение раз за разом отсекает всего один элемент: типичный пример это уже отсортированный массив, в котором опорным берут первый или последний элемент. Проверить легко: на отсортированном массиве из 200 элементов глубина рекурсии доходит до 199, тогда как на случайном остается около 14.

Сохраняет ли quicksort порядок равных элементов?

Нет, быстрая сортировка нестабильна. При разделении элемент может перескочить через весь массив, и две записи с одинаковым ключом легко меняются местами. Если сортируете объекты и порядок одинаковых записей важен, берите стабильный алгоритм, например сортировку слиянием. Именно поэтому массивы объектов в Java сортируются не quicksort, а TimSort.

Сколько дополнительной памяти нужно быстрой сортировке?

Под сами данные нисколько: массив переставляется на месте, копия не создается. Память расходуется на стек вызовов и равна глубине рекурсии, то есть O(log n) при удачном разделении и O(n) в худшем случае. Поэтому на больших массивах и возникает риск переполнения стека, о котором говорится выше.

Зачем писать quicksort самому, если в Java есть Arrays.sort?

Для рабочего кода не нужно: Arrays.sort для примитивов уже реализован как двухопорный quicksort и почти всегда будет быстрее ручной версии. Своя реализация нужна, чтобы понять алгоритм, пройти собеседование и научиться видеть, откуда берется худший случай.

Чем быстрая сортировка отличается от сортировки слиянием?

Тремя вещами. Quicksort работает на месте и не требует второго массива, а слияние требует O(n) дополнительной памяти. Quicksort нестабилен, слияние стабильно. И у quicksort есть худший случай O(n²), а слияние дает O(n log n) всегда. На практике quicksort обычно быстрее за счет работы с памятью, поэтому его и выбрали для примитивов в стандартной библиотеке. Читайте также:

• Алгоритмы сортировки в теории и на практике
• Сортировка вставками
• Итерация vs. Рекурсия