Быстрая сортировка — самая быстрая из известных сортировок для массивов. В довершение всего, это можно сделать на месте для массивов. Для связанных списков сортировка слиянием может быть лучшим вариантом. Кроме того, поскольку быстрая сортировка повышает производительность благодаря использованию случайных чисел, она также становится примером алгоритма, называемого «рандомизированные алгоритмы» .
Наивная версия Алгоритма выглядит так:
1) Start with list I of n items
2) Choose pivot v from I
3) Partition I into 2 unsorted lists I1 and I2 such that
I1 : all keys smaller than pivot
I2 : all keys larger than pivot
Items same as pivot goes to either list
4) Sort I1 recursively, yielding sorted list S1
5) Sort I2 recursively, yielding sorted list S2
6) Concatenate S1,v,S2 yielding sorted list S
Псевдокод в видео
Сколько времени занимает быстрая сортировка?
Интересно, что Quicksort имеет худшее время выполнения 0 (n 2). Однако при тщательной реализации n 2 никогда не происходит и почти всегда выполняется в 0 (n log n) . По сравнению с Heapsort, чей лучший и наихудший случай гарантированно равен n log n , Quicksort превосходит Heapsort по времени по двум причинам:
1) Постоянный коэффициент, окружающий 0 (nlogn), меньше, чем Heapsort из-за очень тонкой логики ядра. Детальное сравнение и обмен механизма кучи внутри циклов увеличивает постоянный коэффициент.
2) Быстрая сортировка может использовать преимущества ссылочного местоположения (и, следовательно, доступа к памяти), обеспечиваемые аппаратным обеспечением и операционной системой.
Как войти?
Если вы выберете правильную опору, то в среднем вы получите 1/4, 3/4 сплит, что дает среднее время пробега 0 (n log n)
Источник: Гудрич и Тамассия
Pivot Выбор стратегии:
Есть много способов выбрать опору
1) First Item 2) Last item 3) Median 4) Median of k (generally of 3) 5) Random item
Выбор случайного ключа в качестве шарнира является предпочтительным способом из-за гарантированной худшим случай возможности с другими методами отбора с следующими видами последовательностей:
1) Presorted list
when chosing first item as your pivot in case of natural order
last item as your pivot in case of reverse order
2) Repeated elements
3) Unimodal sequences* (when median is chosen as pivot)
Итог : когда вы выбираете пивот таким образом, что одна часть вашего разделения (или I1 или I2) становится пустой И если вы делаете все это по списку, то вы по сути делаете разделение N раз.
Быстрая сортировка на Java
package me.rerun;
import java.util.Arrays;
public class QuickSort {
public static void quickSort (Comparable comparableArray[], int lowIndex, int highIndex){
//at least one item must exist in the array
if (lowIndex>=highIndex){
return;
}
int pivotIndex=getMedianIndexAsPivotIndex(lowIndex, highIndex);
//1) Choose pivot from the sublist
Comparable pivot=comparableArray[pivotIndex];
System.out.println("Pivot : "+pivot);
//2) Swap the pivot to the last item in the array
swapItemsWithIndices(comparableArray, pivotIndex, highIndex);
/*
Get the border indices sandwiching the unsorted items alone (ignore pivot (now, in the highIndex))
set 'i' to point to the item before the first Index
set 'j' to point to the item before pivot
Notice that this way, the following invariant gets maintained
all through the sorting procedure
a. All items left of Index 'i' have a value <=pivot
b. All items right of Index 'j' have a value >=pivot
*/
int i=lowIndex-1;
int j=highIndex;
do{ //Notice the <j (pivot item is ignored). We stop when both the counters cross
//compareTo will return 0 when it reaches the pivot - will exit loop
do {i++;} while (comparableArray[i].compareTo(pivot)<0);
//we dont have the protection as the previous loop.
//So, add extra condition to prevent 'j' from overflowing outside the current sub array
do {j--;} while (comparableArray[j].compareTo(pivot)>0 &&(j>lowIndex));
if (i<j){
swapItemsWithIndices(comparableArray, i, j);
}
System.out.println("I :"+i + " J :"+j);
} while (i<j);
swapItemsWithIndices(comparableArray, highIndex, i);//bring pivot to i's position
System.out.println("Comparable array : "+Arrays.asList(comparableArray));
//the big subarray is partially sorted (agrees to invariant). Let's recurse and bring in more hands
quickSort(comparableArray, lowIndex, i-1); //sort subarray between low index and one before the pivot
quickSort(comparableArray, i+1, highIndex); //sort subarray between low index and one before the pivot
}
//... since swapping with array is the easiest way to swap two objects
private static void swapItemsWithIndices(Comparable[] comparableArray, int firstItem, int secondItem) {
System.out.println("Swapping "+comparableArray[firstItem] +" and "+comparableArray[secondItem]);
final Comparable tempItem=comparableArray[firstItem];
comparableArray[firstItem]=comparableArray[secondItem];
comparableArray[secondItem]=tempItem;
System.out.println("After swap array : "+Arrays.asList(comparableArray));
}
//Variation 1 - chose median as pivot
private static int getMedianIndexAsPivotIndex(int lowIndex, int highIndex) {
return lowIndex+((highIndex-lowIndex)/2);
}
public static void main(String[] args) {
//Integer[] unsortedArray=new Integer[]{1,32,121,1424,2,1214,121214,3535,754,343};
//Integer[] unsortedArray=new Integer[]{4,4,8,0,8,9,7,3,7,6};
Integer[] unsortedArray=new Integer[]{5,5,5,5,5,5,5,5,5,5};
long startTime = System.nanoTime();
System.out.println("Original array : "+Arrays.asList(unsortedArray));
quickSort(unsortedArray, 0, unsortedArray.length-1);
System.out.println("Sorted array : "+Arrays.asList(unsortedArray));
System.out.println(System.nanoTime()-startTime);
}
}
Рекомендации
Гудрич и Тамассия
Три прекрасных быстрых
сортировки Быстрая сортировка — оптимальные
унимодальные последовательности