Ta treść została automatycznie przetłumaczona z ukraińskiego.
MergeSort - to efektywny algorytm sortowania, który wykorzystuje zasadę "dziel i rządź". Opiera się na pomyśle podziału wejściowej tablicy na mniejsze części, sortowania każdej części osobno, a następnie łączenia ich w posortowaną tablicę.
Główna idea MergeSort polega na podziale wyjściowej tablicy na pół, aż do osiągnięcia przypadku bazowego, gdy w tablicy pozostaje tylko jeden lub żaden element. Następnie proces scalania (merge) zaczyna się od połączenia dwóch posortowanych części w nową posortowaną tablicę. Proces ten powtarza się rekursywnie do całkowitego połączenia wszystkich części w jedną posortowaną tablicę.
Jedną z głównych zalet MergeSort jest to, że zawsze działa z złożonością czasową O(n log n), gdzie n to liczba elementów w wyjściowej tablicy. Czyni to go efektywnym do sortowania dużych zbiorów danych.
Kiedy i przez kogo stworzono MergeSort?
MergeSort został opracowany przez Johna von Neumanna w 1945 roku. Jednak jego publikacja miała miejsce później, w 1948 roku, kiedy jego kolega Hermann Goldstine opisał pracę von Neumanna podczas wykładu na posiedzeniu Matematycznego Towarzystwa Ameryki. W ten sposób algorytm MergeSort zaczął zyskiwać na popularności i stał się ważną częścią współczesnej wiedzy algorytmicznej i informatyki.
Von Neumann był wybitnym matematykiem, fizykiem, informatykiem i inżynierem elektrykiem. Wniósł znaczący wkład w rozwój teorii obliczeń, architektury komputerów oraz metod numerycznych. MergeSort jest jednym z algorytmów sortowania, które opracował i stał się podstawą dla licznych wariantów i optymalizacji, które są stosowane do dziś.
Przykład algorytmu MergeSort (JavaScript).
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const mergedArr = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
mergedArr.push(left[i]);
i++;
} else {
mergedArr.push(right[j]);
j++;
}
}
while (i < left.length) {
mergedArr.push(left[i]);
i++;
}
while (j < right.length) {
mergedArr.push(right[j]);
j++;
}
return mergedArr;
}
// Przykład użycia
const arr = [8, 5, 2, 9, 1, 7, 6, 3];
const sortedArr = mergeSort(arr);
console.log(sortedArr);
Wynik:
[1, 2, 3, 5, 6, 7, 8, 9]
Funkcja mergeSort() rekurencyjnie dzieli wejściową tablicę na pół, sortuje każdą połowę wywołując mergeSort(), a następnie łączy je za pomocą funkcji merge(). Funkcja merge() scala dwie posortowane tablice w jedną posortowaną tablicę, porównując elementy z obu tablic.
Przykład algorytmu MergeSort (Ruby).
def merge_sort(arr)
return arr if arr.length <= 1
mid = arr.length / 2
left = arr[0...mid]
right = arr[mid..-1]
merge(merge_sort(left), merge_sort(right))
end
def merge(left, right)
merged_arr = []
i = 0
j = 0
while i < left.length && j < right.length
if left[i] <= right[j]
merged_arr << left[i]
i += 1
else
merged_arr << right[j]
j += 1
end
end
while i < left.length
merged_arr << left[i]
i += 1
end
while j < right.length
merged_arr << right[j]
j += 1
end
merged_arr
end
# Przykład użycia
arr = [8, 5, 2, 9, 1, 7, 6, 3]
sorted_arr = merge_sort(arr)
puts sorted_arr
Wynik:
[1, 2, 3, 5, 6, 7, 8, 9]
Funkcja merge_sort() rekurencyjnie dzieli wejściową tablicę na pół, sortuje każdą połowę wywołując merge_sort(), a następnie łączy je za pomocą funkcji merge(). Funkcja merge() scala dwie posortowane tablice w jedną posortowaną tablicę, porównując elementy z obu tablic.
Ten post nie ma jeszcze żadnych dodatków od autora.
