Sortowanie przez scalanie (ang. merge sort) to wydajny, stabilny i rekurencyjny algorytm sortowania o złożoności czasowej O(n log n). Algorytm ten jest oparty na metodzie "dziel i zwyciężaj" (ang. divide and conquer), polegającej na podzieleniu tablicy na mniejsze podtablice, ich posortowaniu, a następnie scaleniu posortowanych podtablic w jedną, posortowaną tablicę.
Opis metody sortowania przez scalanie
Sortowanie przez scalanie działa w trzech głównych krokach
- Podziel - rekurencyjnie dziel tablicę na dwie równe (lub prawie równe) części, aż każda część będzie miała jeden element.
- Sortuj - każda z tych części (jednoelementowa) jest już posortowana z definicji.
- Scal - rekurencyjnie scalaj posortowane części w jedną większą posortowaną tablicę, aż do uzyskania całkowicie posortowanej tablicy.
Algorytm sortowania przez scalanie
- Jeśli długość tablicy jest mniejsza lub równa 1, zakończ (tablica jest już posortowana).
- Podziel tablicę na dwie równe części.
- Wywołaj rekursywnie sortowanie przez scalanie dla każdej z tych części.
- Scal dwie posortowane części w jedną posortowaną tablicę.
Przykład sortowania przez scalanie
Tablica do posortowania = [5, 3, 8, 4, 2]
Podział [5, 3, 8, 4, 2]
Podziel na [5, 3] i [8, 4, 2] [5, 3] -> Podziel na [5] i [3] [8, 4, 2] -> Podziel na [8] i [4, 2] [4, 2] -> Podziel na [4] i [2]
Sortowanie
[5] i [3] są już posortowane
[8], [4], [2] są już posortowane
[4] i [2] -> Scalanie: [2, 4]
Scalanie
Scal [5] i [3] -> [3, 5]
Scal [8] i [2, 4] -> [2, 4, 8]
Scal [3, 5] i [2, 4, 8] -> [2, 3, 4, 5, 8]
Złożoność obliczeniowa sortowania przez scalanie
Złożoność czasowa - O(n log n) w najgorszym, najlepszym i średnim przypadku, gdzie n to liczba elementów w tablicy.
Złożoność pamięciowa - O(n) dodatkowej pamięci, ponieważ wymaga pomocniczej tablicy do scalania.
Zalety i wady sortowania przez scalanie
Zalety
Stabilność: zachowuje kolejność elementów o tych samych kluczach.
Gwarantowana złożoność O(n log n).
Dobrze działa na dużych zbiorach danych i w przypadku plików o dużych rozmiarach.
Wady
Wymaga dodatkowej pamięci O(n) dla pomocniczej tablicy.
Może być wolniejszy niż inne algorytmy sortowania (np. quicksort) w przypadku małych tablic.
Implementacje algorytmu w różnych językach programowania
Sortowanie przez scalanie w języku C++
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Nieposortowana tablica: ";
printArray(arr, n);
mergeSort(arr, 0, n - 1);
cout << "Posortowana tablica: ";
printArray(arr, n);
return 0;
}
Sortowanie przez scalanie w języku Python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
def print_array(arr):
for i in arr:
print(i, end=" ")
print()
# Przykładowa tablica
arr = [5, 3, 8, 4, 2]
print("Nieposortowana tablica:", end=" ")
print_array(arr)
merge_sort(arr)
print("Posortowana tablica:", end=" ")
print_array(arr)
Sortowanie przez scalanie w języku Java
public class MergeSort {
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
int arr[] = {5, 3, 8, 4, 2};
System.out.println("Nieposortowana tablica:");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("Posortowana tablica:");
printArray(arr);
}
}
Sortowanie przez scalanie w języku JavaScript
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function printArray(arr) {
console.log(arr.join(" "));
}
// Przykładowa tablica
let arr = [5, 3, 8, 4, 2];
console.log("Nieposortowana tablica:");
printArray(arr);
arr = mergeSort(arr);
console.log("Posortowana tablica:");
printArray(arr);
Te implementacje pokazują, jak algorytm sortowania przez scalanie może być zaimplementowany w różnych językach programowania, działając zgodnie z opisanym wcześniej algorytmem.
Komentarze