Spis treściKliknij link, aby przejść do wybranego miejsca
Ta treść została automatycznie przetłumaczona z ukraińskiego.
QuickSort jest algorytmem sortowania, który wykorzystuje strategię "dziel i rządź". Szybko i efektywnie sortuje tablice poprzez porównywanie elementów i przenoszenie ich na odpowiednie pozycje.
Kiedy i przez kogo stworzono QuickSort?
QuickSort został opracowany przez brytyjskiego inżyniera i informatyka Tony'ego Hoare'a w 1959 roku. Tony Hoare stał się znany w dziedzinie informatyki dzięki swoim znaczącym wkładom, a QuickSort stał się jednym z jego najbardziej znanych wynalazków. Tony Hoare otrzymał nagrodę Turinga w 1980 roku za swoje prace w dziedzinie sortowania i analizy algorytmów.
Jak dokładnie działa sortowanie QuickSort?
- Wybierany jest element pivot (punkt odniesienia). Może to być dowolny element tablicy, na przykład pierwszy, ostatni lub środkowy element.
- Ustawiamy elementy tablicy w taki sposób, że wszystkie elementy mniejsze od pivot znajdują się przed nim, a wszystkie większe elementy - za nim. Element pivot trafia na swoją ostateczną pozycję.
- Rekurencyjnie stosujemy QuickSort do podtablicy znajdującej się przed elementem pivot (elementy mniejsze) oraz do podtablicy znajdującej się za elementem pivot (elementy większe).
- Powtarzamy kroki 1-3 dla każdej podtablicy, aż cała tablica będzie posortowana.
Ponieważ QuickSort stosuje strategię "dziel i rządź", wykazuje dobrą szybkość działania. Średnio jego złożoność wynosi O(n log n), gdzie n to liczba elementów w tablicy. Jednak najgorszy przypadek może mieć złożoność O(n^2), gdy element pivot zawsze wybierany jest jako największy lub najmniejszy element tablicy. Aby uniknąć najgorszego przypadku, można stosować różne strategie wyboru elementu pivot, na przykład losowy wybór lub medianę trzech elementów.
Przykład algorytmu QuickSort (JavaScript).
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const less = [];
const greater = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
less.push(arr[i]);
} else if (arr[i] > pivot) {
greater.push(arr[i]);
}
}
return [...quickSort(less), pivot, ...quickSort(greater)];
}
// Przykład użycia:
const array = [5, 3, 1, 6, 2, 4];
const sortedArray = quickSort(array);
console.log(sortedArray);
Funkcja quickSort przyjmuje tablicę arr jako parametr wejściowy i zwraca posortowaną tablicę.
Algorytm QuickSort rekurencyjnie dzieli wejściową tablicę na mniejsze i większe podtablice w odniesieniu do wybranego elementu pivot (pivot). Elementy mniejsze od pivot są przechowywane w less, a większe - w greater. Następnie wywoływana jest rekurencyjna funkcja quickSort dla podtablic less i greater, a wyniki są łączone z elementem pivot pivot, aby utworzyć końcową posortowaną tablicę.
Wynik:
[1, 2, 3, 4, 5, 6]
Przykład algorytmu QuickSort (Ruby).
def quick_sort(arr)
return arr if arr.length <= 1
pivot = arr[arr.length / 2]
less = []
greater = []
arr.each do |element|
if element < pivot
less << element
elsif element > pivot
greater << element
end
end
return [*quick_sort(less), pivot, *quick_sort(greater)]
end
# Przykład użycia:
array = [5, 3, 1, 6, 2, 4]
sorted_array = quick_sort(array)
puts sorted_array
Tak samo jak w przykładzie z JavaScript - funkcja quick_sort przyjmuje tablicę arr jako parametr wejściowy i zwraca posortowaną tablicę.
Algorytm QuickSort rekurencyjnie dzieli wejściową tablicę na mniejsze i większe podtablice w odniesieniu do wybranego elementu pivot (pivot). Elementy mniejsze od pivot są przechowywane w tablicy less, a większe - w tablicy greater. Następnie rekurencyjnie wywoływana jest quick_sort dla podtablic less i greater, a wyniki są łączone z elementem pivot pivot za pomocą operatora rozpakowania *, aby utworzyć końcową posortowaną tablicę.
Wynik:
[1, 2, 3, 4, 5, 6]
Czy algorytm QuickSort jest używany w standardowych metodach JavaScript lub Ruby?
W standardowych metodach języków Ruby i JavaScript, które odpowiadają za sortowanie, zazwyczaj nie stosuje się dokładnie algorytmu QuickSort. Może to się różnić w zależności od konkretnej implementacji języka i jego wersji, a także od unikalnych wymagań i optymalizacji, które są stosowane.
W Ruby do sortowania tablic domyślnie używany jest algorytm, który łączy metody QuickSort, InsertionSort i HeapSort. Ten algorytm nazywa się Timsort, który został opracowany do optymalnego sortowania różnych typów danych.
W JavaScript sortowanie tablic zazwyczaj wykonuje się za pomocą metody Array.prototype.sort(). Implementacja tej metody może się różnić między różnymi implementacjami JavaScript (na przykład silnikami V8 w Node.js lub Chrome i SpiderMonkey w Firefox). W większości przypadków do sortowania używany jest szybki i zoptymalizowany algorytm, który łączy QuickSort z InsertionSort lub MergeSort, w zależności od implementacji.
Zatem, chociaż QuickSort może być używany jako jeden z komponentów lub podstawowych algorytmów w metodach sortowania tablic Ruby i JavaScript, sam w sobie QuickSort nie jest jedynym algorytmem stosowanym w tych językach do sortowania domyślnie. Zazwyczaj stosowane są bardziej złożone algorytmy, takie jak Timsort lub jego warianty, które łączą różne algorytmy sortowania w celu zapewnienia optymalności i szerokiego zakresu przypadków użycia.
Ten post nie ma jeszcze żadnych dodatków od autora.
