Wprowadzenie do algorytmu sortowania przez scalanie

Sortowanie przez scalanie to algorytm sortowania oparty na technice „dziel i zwyciężaj”. To jeden z najbardziej wydajnych algorytmów sortowania.

W tym artykule dowiesz się, jak działa algorytm sortowania przez scalanie, algorytm sortowania przez scalanie, its złożoność czasowa i przestrzenna oraz jej implementacja w różnych językach programowania, takich jak C++, Python i JavaScript.

Jak działa algorytm sortowania przez scalanie?

Sortowanie przez scalanie działa na zasadzie dziel i rządź. Sortowanie przez scalanie wielokrotnie dzieli tablicę na dwie równe podtablice, aż każda podtablica składa się z jednego elementu. Na koniec wszystkie te podtablice są scalane w taki sposób, że wynikowa tablica jest sortowana.

Koncepcję tę można skuteczniej wyjaśnić za pomocą przykładu. Rozważ nieposortowaną tablicę z następującymi elementami: {16, 12, 15, 13, 19, 17, 11, 18}.

Tutaj algorytm sortowania przez scalanie dzieli tablicę na dwie połowy, wywołuje siebie dla dwóch połówek, a następnie scala dwie posortowane połówki.

Algorytm sortowania scalającego

Poniżej algorytm sortowania przez scalanie:

MergeSort (arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
powrót
jeszcze
Znajdź środkowy indeks, który dzieli tablicę na dwie połowy: 
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Wywołaj mergeSort() dla pierwszej połowy: 
Call mergeSort (arr, leftIndex, middleIndex)
Wywołaj mergeSort() dla drugiej połowy:
Call mergeSort (arr, middleIndex+1, rightIndex)
Połącz dwie połówki posortowane w kroku 2 i 3:
Scalenie połączeń (arr, leftIndex, middleIndex, rightIndex)

Związane z: Co to jest rekurencja i jak z niej korzystać?

Złożoność czasowo-przestrzenna algorytmu sortowania przez scalanie

Algorytm sortowania przez scalanie może być wyrażony w postaci następującej relacji rekurencyjnej:

T(n) = 2T(n/2) + O(n)

Po rozwiązaniu tej relacji rekurencyjnej za pomocą twierdzenia mistrza lub metody drzewa rekurencyjnego otrzymasz rozwiązanie jako O(n logn). Zatem złożoność czasowa algorytmu sortowania przez scalanie wynosi O(po zalogowaniu).

Najlepsza złożoność czasowa sortowania przez scalanie: O(po zalogowaniu)

Średnia złożoność czasowa sortowania przez scalanie: O(po zalogowaniu)

Najgorsza złożoność czasowa sortowania przez scalanie: O(po zalogowaniu)

Związane z: Co to jest notacja Big-O?

Złożoność przestrzeni pomocniczej algorytmu sortowania przez scalanie jest Na) tak jak nie W implementacji sortowania przez scalanie wymagana jest przestrzeń pomocnicza.

Implementacja w C++ algorytmu sortowania przez scalanie

Poniżej znajduje się implementacja algorytmu sortowania przez scalanie w C++:

// Implementacja C++
// algorytm sortowania przez scalanie
#zawierać 
używając standardowej przestrzeni nazw;
// Ta funkcja łączy dwie podtablice arr[]
// Lewa podtablica: arr[leftIndex..middleIndex]
// Prawa podtablica: arr[middleIndex+1..rightIndex]
void merge (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Utwórz tymczasowe tablice
int L[RozmiarLewejPodtablicy], R[RozmiarPrawejPodtablicy];
// Kopiowanie danych do tymczasowych tablic L[] i R[]
dla (int i = 0; i < leftSubarraySize; i++)
L[i] = przyp[lewyIndeks + i];
dla (int j = 0; j < prawaRozmiarPodtablicy; j++)
R[j] = przyp[średni indeks + 1 + j];
// Połącz tymczasowe tablice z powrotem w arr[leftIndex..rightIndex]
// Początkowy indeks lewej podtablicy
int i = 0;
// Początkowy indeks prawej podtablicy
intj = 0;
// Początkowy indeks połączonej podtablicy
int k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
jeśli (L[i] <= R[j])
{
przyp[k] = L[i];
i++;
}
jeszcze
{
arr[k] = R[j];
j++;
}
k++;
}
// Jeśli są jakieś pozostałe elementy w L[]
// Skopiuj do arr[]
while (i < leftSubarraySize)
{
przyp[k] = L[i];
i++;
k++;
}
// Jeśli są jakieś pozostałe elementy w R[]
// Skopiuj do arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (lewyIndex >= rightIndex)
{
powrót;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
scalanie (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcja do drukowania elementów
// tablicy
void printArray (int arr[], int rozmiar)
{
dla (int i = 0; ja < rozmiar; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
// Kod kierowcy
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int rozmiar = rozmiar (arr) / rozmiar (arr[0]);
cout << "Tablica nieposortowana:" << endl;
printArray (arr, rozmiar);
mergeSort (arr, 0, rozmiar - 1);
cout << "Tablica posortowana:" << endl;
printArray (arr, rozmiar);
zwróć 0;
}

Wynik:

Tablica nieposortowana:
16 12 15 13 19 17 11 18 
Posortowana tablica:
11 12 13 15 16 17 18 19

Implementacja JavaScript algorytmu sortowania przez scalanie JavaScript

Poniżej znajduje się implementacja JavaScript algorytmu sortowania przez scalanie:

// Implementacja JavaScript
// algorytm sortowania przez scalanie
// Ta funkcja łączy dwie podtablice arr[]
// Lewa podtablica: arr[leftIndex..middleIndex]
// Prawa podtablica: arr[middleIndex+1..rightIndex]
scalanie funkcji (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Utwórz tymczasowe tablice
var L = new Array (leftSubarraySize);
var R = new Array (rightSubarraySize);
// Kopiowanie danych do tymczasowych tablic L[] i R[]
dla (niech i = 0; jaL[i] = przyp[lewyIndeks + i];
}
dla (niech j = 0; jotR[j] = przyp[średni indeks + 1 + j];
}
// Połącz tymczasowe tablice z powrotem w arr[leftIndex..rightIndex]
// Początkowy indeks lewej podtablicy
zmienna i = 0;
// Początkowy indeks prawej podtablicy
zmienna j = 0;
// Początkowy indeks połączonej podtablicy
var k = leftIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
jeśli (L[i] <= R[j])
{
przyp[k] = L[i];
i++;
}
jeszcze
{
arr[k] = R[j];
j++;
}
k++;
}
// Jeśli są jakieś pozostałe elementy w L[]
// Skopiuj do arr[]
while (i < leftSubarraySize)
{
przyp[k] = L[i];
i++;
k++;
}
// Jeśli są jakieś pozostałe elementy w R[]
// Skopiuj do arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex >= rightIndex) {
powrót
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
scalanie (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcja do drukowania elementów
// tablicy
funkcja printArray (arr, rozmiar) {
dla (niech i = 0; jadocument.write (arr[i] + " ");
}
dokument.zapis("
");
}
// Kod kierowcy:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var rozmiar = arr.długość;
document.write("Nieposortowana tablica:
");
printArray (arr, rozmiar);
mergeSort (arr, 0, rozmiar - 1);
document.write("Posortowana tablica:
");
printArray (arr, rozmiar);

Wynik:

Tablica nieposortowana:
16 12 15 13 19 17 11 18
Posortowana tablica:
11 12 13 15 16 17 18 19

Związane z: Programowanie dynamiczne: przykłady, typowe problemy i rozwiązania

Implementacja algorytmu sortowania przez scalanie w Pythonie

Poniżej znajduje się implementacja algorytmu sortowania przez scalanie w Pythonie:

# Implementacja w Pythonie
# algorytm sortowania przez scalanie
def scal Sortuj (arr):
jeśli len (arr) > 1:
# Znajdowanie środkowego indeksu tablicy
middleIndex = len (arr)//2
# Lewa połowa tablicy
L = przyp[:średni indeks]
# Prawa połowa tablicy
R = tab[indeks środkowy:]
# Sortowanie pierwszej połowy tablicy
scalanieSortowanie (L)
# Sortowanie drugiej połowy tablicy
połączSortuj (R)
# Początkowy indeks lewej podtablicy
ja = 0
# Początkowy indeks prawej podtablicy
j = 0
# Początkowy indeks połączonej podtablicy
k = 0
# Skopiuj dane do tymczasowych tablic L[] i R[]
podczas gdy i < len (L) oraz j < len (R):
jeśli L[i] < R[j]:
przyp[k] = L[i]
ja = ja + 1
jeszcze:
przyp[k] = R[j]
j = j + 1
k = k + 1
# Sprawdzenie, czy zostały jeszcze jakieś elementy
podczas gdy ja < len (L):
przyp[k] = L[i]
ja = ja + 1
k = k + 1
podczas gdy j < len (R):
przyp[k] = R[j]
j = j + 1
k = k + 1
# Funkcja drukowania elementów
# tablicy
def printArray (arr, rozmiar):
dla mnie w zakresie (rozmiar):
drukuj (arr[i], end=" ")
wydrukować()
# Kod kierowcy
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
rozmiar = len (arr)
print("Tablica nieposortowana:")
printArray (arr, rozmiar)
sortowanie scalania (arr)
print("Posortowana tablica:")
printArray (arr, rozmiar)

Wynik:

Tablica nieposortowana:
16 12 15 13 19 17 11 18
Posortowana tablica:
11 12 13 15 16 17 18 19

Zrozumienie innych algorytmów sortowania

Sortowanie jest jednym z najczęściej używanych algorytmów w programowaniu. Możesz sortować elementy w różnych językach programowania przy użyciu różnych algorytmów sortowania, takich jak szybkie sortowanie, sortowanie bąbelkowe, sortowanie przez scalanie, sortowanie przez wstawianie itp.

Sortowanie bąbelkowe to najlepszy wybór, jeśli chcesz poznać najprostszy algorytm sortowania.

Wprowadzenie do algorytmu sortowania bąbelkowego

Algorytm Bubble Sort: doskonałe wprowadzenie do sortowania tablic.

Czytaj dalej

O autorze