Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
MergeSort - ist ein effizienter Sortieralgorithmus, der das Prinzip "teile und herrsche" verwendet. Er basiert auf der Idee, das Eingangsarray in kleinere Teile zu zerlegen, jeden Teil separat zu sortieren und sie dann zu einem sortierten Array zusammenzuführen.
Die Hauptidee von MergeSort besteht darin, das Ausgangsarray in zwei Hälften zu teilen, bis der Basisfall erreicht ist, wenn im Array nur noch ein oder kein Element verbleibt. Dann beginnt der Merging-Prozess mit der Zusammenführung der beiden sortierten Teile zu einem neuen sortierten Array. Dieser Prozess wird rekursiv wiederholt, bis alle Teile zu einem sortierten Array zusammengeführt sind.
Ein Hauptvorteil von MergeSort ist, dass er immer mit einer zeitlichen Komplexität von O(n log n) arbeitet, wobei n die Anzahl der Elemente im Ausgangsarray ist. Dies macht ihn effizient für die Sortierung großer Datenmengen.
Wann und von wem wurde MergeSort entwickelt?
MergeSort wurde 1945 von John von Neumann entwickelt. Seine Veröffentlichung erfolgte jedoch später, 1948, als sein Kollege Hermann Goldstine die Arbeit von von Neumann während eines Vortrags auf einer Sitzung der American Mathematical Society beschrieb. So begann der Algorithmus MergeSort an Popularität zu gewinnen und wurde ein wichtiger Bestandteil des modernen algorithmischen Wissens und der Informatik.
Von Neumann war ein herausragender Mathematiker, Physiker, Informatiker und Elektrotechniker. Er leistete bedeutende Beiträge zur Entwicklung der Berechnungstheorie, der Computerarchitektur und der numerischen Methoden. MergeSort ist einer der Sortieralgorithmen, die er entwickelt hat, und wurde zur Grundlage für zahlreiche Varianten und Optimierungen, die bis heute verwendet werden.
Beispiel für den MergeSort-Algorithmus (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;
}
// Beispiel zur Verwendung
const arr = [8, 5, 2, 9, 1, 7, 6, 3];
const sortedArr = mergeSort(arr);
console.log(sortedArr);
Ergebnis:
[1, 2, 3, 5, 6, 7, 8, 9]
Die Funktion mergeSort() teilt das Eingangsarray rekursiv in zwei Hälften, sortiert jede Hälfte durch einen Aufruf von mergeSort() und führt sie dann mit der Funktion merge() zusammen. Die Funktion merge() fügt zwei sortierte Arrays zu einem sortierten Array zusammen, indem sie die Elemente aus beiden Arrays vergleicht.
Beispiel für den MergeSort-Algorithmus (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
# Beispiel zur Verwendung
arr = [8, 5, 2, 9, 1, 7, 6, 3]
sorted_arr = merge_sort(arr)
puts sorted_arr
Ergebnis:
[1, 2, 3, 5, 6, 7, 8, 9]
Die Funktion merge_sort() teilt das Eingangsarray rekursiv in zwei Hälften, sortiert jede Hälfte durch einen Aufruf von merge_sort() und führt sie dann mit der Funktion merge() zusammen. Die Funktion merge() fügt zwei sortierte Arrays zu einem sortierten Array zusammen, indem sie die Elemente aus beiden Arrays vergleicht.
Dieser Beitrag hat noch keine Ergänzungen vom Autor.
