adminhq

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

Компьютерные науки
quick sort algorithm

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

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

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

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

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

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

алгоритм быстрой сортировки

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

1 шаг

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

2 шаг

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

3 шаг

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

4 шаг

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

5 шаг

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

6 шаг

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

7 шаг

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

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

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

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

Код   
  1. import java.util.Arrays;
  2.  
  3. public class QuickSort {
  4.  
  5.     public static void quickSort(int[] array, int low, int high) {
  6.         if (array.length == 0)
  7.             return;//завершить выполнение если длина массива равна 0
  8.  
  9.         if (low >= high)
  10.             return;//завершить выполнение если уже нечего делить
  11.  
  12.         // выбрать опорный элемент
  13.         int middle = low + (high - low) / 2;
  14.         int opora = array[middle];
  15.  
  16.         // разделить на подмассивы, который больше и меньше опорного элемента
  17.         int i = low, j = high;
  18.         while (i <= j) {
  19.             while (array[i] < opora) {
  20.                 i++;
  21.             }
  22.  
  23.             while (array[j] > opora) {
  24.                 j--;
  25.             }
  26.  
  27.             if (i <= j) {//меняем местами
  28.                 int temp = array[i];
  29.                 array[i] = array[j];
  30.                 array[j] = temp;
  31.                 i++;
  32.                 j--;
  33.             }
  34.         }
  35.  
  36.         // вызов рекурсии для сортировки левой и правой части
  37.         if (low < j)
  38.             quickSort(array, low, j);
  39.  
  40.         if (high > i)
  41.             quickSort(array, i, high);
  42.     }
  43.     public static void main(String[] args) {
  44.         int[] x = { 8, 0, 4, 7, 3, 7, 10, 12, -3 };
  45.         System.out.println("Было");
  46.         System.out.println(Arrays.toString(x));
  47.  
  48.         int low = 0;
  49.         int high = x.length - 1;
  50.  
  51.         quickSort(x, low, high);
  52.         System.out.println("Стало");
  53.         System.out.println(Arrays.toString(x));
  54.     }
  55. }

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

Еще по теме

5

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

    if (i <= j) {//меняем местами — ага, когда i == j многое поменяем?

    quickSort(array, low, j);
    quickSort(array, i, high); — не лишка ли с i-того то начинать? вообще с j+1

    Ответить

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *