Внедряване на алгоритъм за бърз сорт в Java

1. Общ преглед

В този урок ще разгледаме подробно алгоритъма QuickSort, фокусирайки се върху неговото изпълнение на Java.

Също така ще обсъдим неговите предимства и недостатъци и след това ще анализираме неговата сложност във времето.

2. Алгоритъм за бързо сортиране

Quicksort е алгоритъм за сортиране, който използва принципа на разделяй и владей. Той има средна сложност на O (n log n) и е един от най-използваните алгоритми за сортиране, особено за големи обеми данни.

Важно е да запомните, че Quicksort не е стабилен алгоритъм. Стабилен алгоритъм за сортиране е алгоритъм, при който елементите с еднакви стойности се показват в същия ред в сортирания изход, както се появяват в списъка за въвеждане.

Входният списък е разделен на два под-списъка от елемент, наречен pivot; един под-списък с елементи, по-малки от ос, и друг с елементи, по-големи от ос. Този процес се повтаря за всеки под-списък.

И накрая, всички сортирани под-списъци се сливат, за да образуват крайния изход.

2.1. Стъпки на алгоритъма

  1. Избираме елемент от списъка, наречен pivot. Ще го използваме, за да разделим списъка на два под-списъка.
  2. Пренареждаме всички елементи около пивота - тези с по-малка стойност се поставят преди него и всички елементи, по-големи от пивота след него. След тази стъпка пивотът е в крайната си позиция. Това е важната стъпка за разделяне.
  3. Прилагаме горните стъпки рекурсивно към двата под-списъка отляво и отдясно на ос.

Както виждаме, quicksort е естествено рекурсивен алгоритъм, както всеки подход за разделяне и завладяване.

Нека вземем прост пример, за да разберем по-добре този алгоритъм.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Да предположим, че избираме 5 като опора за простота
  2. Първо ще поставим всички елементи под 5 на първо място в масива: {3, 4, 5, 6, 5, 9}
  3. След това ще го повторим за левия подмасив {3,4}, като вземем 3 като ос
  4. Няма елементи по-малко от 3
  5. Прилагаме бърза сортировка върху под-масива вдясно на ос, т.е. {4}
  6. Този подмасив се състои само от един сортиран елемент
  7. Продължаваме с дясната част на оригиналния масив, {6, 5, 9}, докато получим окончателния подреден масив

2.2. Избор на оптимален Pivot

Решаващият момент в QuickSort е да изберете най-добрия пивот. Средният елемент е, разбира се, най-добрият, тъй като ще раздели списъка на два равни под-списъка.

Но намирането на средния елемент от неподреден списък е трудно и отнема много време, поради което приемаме за въртене първия елемент, последния елемент, медианата или всеки друг случаен елемент.

3. Внедряване в Java

Първият метод е quickSort (), който взема за параметри масива, който трябва да бъде сортиран, първия и последния индекс. Първо проверяваме индексите и продължаваме само ако все още има елементи за сортиране.

Получаваме индекса на сортираната ос и го използваме за рекурсивно извикване на метод partition () със същите параметри като метода quickSort () , но с различни индекси:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Нека продължим с метода partition () . За по-голяма простота тази функция приема последния елемент като опорна точка. След това проверява всеки елемент и го разменя преди ос, ако стойността му е по-малка.

До края на разделянето всички елементи по-малко от въртенето са вляво от него, а всички елементи, по-големи от въртенето, са вдясно от него. Осевата точка е в крайната си сортирана позиция и функцията връща тази позиция:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Анализ на алгоритъма

4.1. Сложност във времето

В най-добрия случай алгоритъмът ще раздели списъка на два еднакви по размер под-списъци. И така, първата итерация на пълния списък с размер n се нуждае от O (n) . Сортирането на останалите два под-списъка с n / 2 елемента отнема 2 * O (n / 2) всеки. В резултат на това алгоритъмът QuickSort има сложността на O (n log n) .

В най-лошия случай алгоритъмът ще избере само един елемент във всяка итерация, така че O (n) + O (n-1) + ... + O (1) , което е равно на O (n2) .

Средно QuickSort има сложност O (n log n) , което го прави подходящ за големи обеми данни.

4.2. QuickSort срещу MergeSort

Нека обсъдим в кои случаи трябва да изберем QuickSort пред MergeSort.

Въпреки че и Quicksort, и Mergesort имат средна времева сложност на O (n log n) , Quicksort е предпочитаният алгоритъм, тъй като има O (log (n)) пространствена сложност. Mergesort, от друга страна, изисква O (n) допълнително съхранение, което го прави доста скъпо за масиви.

Quicksort изисква достъп до различни индекси за своите операции, но този достъп не е пряко възможен в свързани списъци, тъй като няма непрекъснати блокове; следователно за достъп до елемент трябва да извършим итерация през всеки възел от началото на свързания списък. Също така Mergesort се прилага без допълнително място за LinkedLists.

В такъв случай обикновено се предпочита увеличаване на режийните разходи за Quicksort и Mergesort.

5. Заключение

Quicksort е елегантен алгоритъм за сортиране, който е много полезен в повечето случаи.

Обикновено това е алгоритъм „на място“ със средна времева сложност на O (n log n).

Друг интересен момент, който трябва да се спомене, е, че методът на Java Arrays.sort () използва Quicksort за сортиране на масиви от примитиви. Внедряването използва два пивота и се представя много по-добре от нашето просто решение, затова за производствения код обикновено е по-добре да се използват библиотечни методи.

Както винаги, кодът за внедряване на този алгоритъм може да бъде намерен в нашето хранилище GitHub.