Алгоритм быстрой сортировки (Quick sort) в Java

Алгоритм быстрой сортировки – это один из самых быстрых существующих алгоритмов сортировки (на момент написания данной статьи), который является примером стратегии “разделяй и властвуй”. Большинство готовых библиотек и методов по сортировке используют quick sort алгоритм как основу.

Перед тем, как мы перейдем к написанию кода сначала разберемся как именно работает данный алгоритм. К стати говоря, алгоритм быстрой сортировки как и алгоритм сортировки пузырьком в худшем случае работает за время O() что довольно медленно. Но не торопитесь делать поспешные выводы. В среднем алгоритм быстрой сортировки выполняется за время O(n logn); причем время сортировки очень зависит от выбора опорного элемента, о котором Вы узнаете далее.

Алгоритм быстрой сортировки – это рекурсивный алгоритм. Как уже было сказано выше quick sort использует стратегию “разделяй и властвуй”. Ее суть заключается в том, что задача разбивается на подзадачи до тех пор, пока не будет элементарной единицы. Так и с алгоритмом: массив делится на несколько массивов, каждый из который сортируется по отдельности и потом объединяется в один массив.

Пошаговое описание работы алгоритма быстрой сортировки

1. Выбрать опорный элемент из массива. Обычно опорным элементом является средний элемент.
2. Разделить массив на два подмассива: элементы, меньше опорного и элементы, больше опорного.
3. Рекурсивно применить сортировку к двум подмассивам.

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

Подробный анализ алгоритма быстрой сортировки

Исходный массив

Выбор опорного элемента. В данном случае мы взяли первый элемент 3

Разбиваем массив на подмассивы: те, что больше 3 и те, что меньше 3

Проделаем то же самое с левый подмассивом

Выбор опорного элемента

Разбиение на подмассивы

Выбор опорного и разбиение на подмассивы. Не забываем, что мы проделываем эти шаги пока не будет один элемент в подмассиве.

Как видим, левая часть отсортирована. То же самое проделывается и для правой части от опорного элемента 3.

Эти картинки я взял вот отсюда: http://me.dt.in.th/page/Quicksort/. Там Вы найдете завершение для этого массива. Главное, что суть понятна.

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

Код

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] array, int low, int high) {
        if (array.length == 0)
            return;//завершить выполнение если длина массива равна 0
 
        if (low >= high)
            return;//завершить выполнение если уже нечего делить
 
        // выбрать опорный элемент
        int middle = low + (high - low) / 2;
        int opora = array[middle];
 
        // разделить на подмассивы, который больше и меньше опорного элемента
        int i = low, j = high;
        while (i <= j) {
            while (array[i] < opora) {
                i++;
            }
 
            while (array[j] > opora) {
                j--;
            }
 
            if (i <= j) {//меняем местами
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
 
        // вызов рекурсии для сортировки левой и правой части
        if (low < j)
            quickSort(array, low, j);
 
        if (high > i)
            quickSort(array, i, high);
    }
    public static void main(String[] args) {
        int[] x = { 8, 0, 4, 7, 3, 7, 10, 12, -3 };
        System.out.println("Было");
        System.out.println(Arrays.toString(x));
 
        int low = 0;
        int high = x.length - 1;
 
        quickSort(x, low, high);
        System.out.println("Стало");
        System.out.println(Arrays.toString(x));
    }
}

Это все об алгоритме быстрой сортировки. Это очень быстрый и эффективный алгоритм, который идеально подходит для сортировки больших массивов. Он может быть немного сложным к восприятию и реализации. Не переживайте, если не поняли его с первого раза. Перечитайте статью еще раз и главное поймите смысл работы, а реализацию всегда можно найти в сети.