Spis treści
- Wstęp
- Co to jest sortowanie przez scalanie w C++
- Metoda dziel i rządź
- Algorytm sortowania przez scalanie
- Implementacja sortowania przez scalanie w C++
- Wniosek
1. Wstęp
Algorytmy sortowania w informatyce służą do porządkowania danych w porządku rosnącym lub malejącym. Dostępnych jest wiele algorytmów sortowania o różnych właściwościach. Sortowanie przez scalanie jest jedną z metod w C++, która może sortować tablice.
2. Czym jest sortowanie przez scalanie w C++
Sortowanie przez scalanie wykorzystuje technikę dziel i zwyciężaj, która umożliwia rozmieszczenie elementów tablicy. Może również sortować listę elementów w C++. Dzieli dane wejściowe na dwie połowy, sortuje każdą z nich niezależnie, a następnie łączy je we właściwej kolejności.
3. Metoda dziel i zwyciężaj
Algorytm sortowania stosuje strategię dziel i zwyciężaj, która polega na podzieleniu tablicy wejściowej na mniejsze podtablice, rozwiązaniu ich oddzielnie, a następnie połączeniu wyników w celu uzyskania posortowanego wyniku. W przypadku sortowania przez scalanie tablica jest rekurencyjnie dzielona na dwie połowy, aż w każdej połowie pozostanie tylko jeden element.
4. Scal algorytm sortowania
Algorytm sortowania przez scalanie składa się z dwóch głównych etapów: dzielenia i łączenia. Kroki są następujące:
4.1 Podziel
Algorytm sortowania przez scalanie jest zgodny ze strategią dziel i zwyciężaj w celu sortowania elementów w tablicy.
- Pierwszym krokiem algorytmu będzie sprawdzenie elementów tablicy. Jeśli zawiera jeden element, jest już uważany za posortowany, a algorytm zwróci tę samą tablicę bez żadnych zmian.
- Jeśli tablica zawiera więcej niż jeden element, algorytm dzieli ją na dwie połowy: lewą i prawą.
- Algorytm sortowania przez scalanie jest następnie stosowany rekurencyjnie do lewej i prawej połowy tablicy, skutecznie dzieląc je na mniejsze podtablice i sortując je indywidualnie.
- Ten rekurencyjny proces trwa, dopóki podtablice nie będą zawierały tylko jednego elementu (zgodnie z krokiem 1), w którym to momencie można je połączyć, aby utworzyć ostateczną, posortowaną tablicę wyjściową.
4.2 Połącz
Teraz zobaczymy kroki, aby scalić tablice:
- Pierwszym krokiem algorytmu sortowania przez scalanie jest utworzenie pustej tablicy.
- Następnie algorytm przechodzi do porównania pierwszych elementów lewej i prawej połowy tablicy wejściowej.
- Mniejszy z dwóch elementów jest dodawany do nowej tablicy, a następnie usuwany z odpowiedniej połowy tablicy wejściowej.
- Kroki 2-3 są następnie powtarzane, aż jedna z połówek zostanie opróżniona.
- Wszystkie pozostałe elementy w niepustej połowie są następnie dodawane do nowej tablicy.
- Wynikowa tablica jest teraz w pełni posortowana i reprezentuje ostateczny wynik algorytmu sortowania przez scalanie.
5. Implementacja sortowania przez scalanie w C++
Aby zaimplementować sortowanie przez scalanie w C++, stosuje się dwie różne metody. Złożoność czasowa obu metod jest równoważna, ale ich wykorzystanie tymczasowych podtablic jest różne.
Pierwsza metoda sortowania przez scalanie w C++ wykorzystuje dwie tymczasowe podtablice, podczas gdy druga wykorzystuje tylko jedną. Warto zauważyć, że całkowity rozmiar dwóch tymczasowych podtablic w pierwszej metodzie jest równy rozmiarowi oryginalnej tablicy w drugiej metodzie, więc złożoność przestrzenna pozostaje stała.
Metoda 1 — użycie dwóch podtablic tymczasowych
Oto przykładowy program do sortowania przez scalanie w C++ przy użyciu metody 1, która wykorzystuje dwie tymczasowe podtablice:
#includeprzy użyciu przestrzeni nazw std ;
próżnia łączyć ( int arr [ ] , int l , int M , int R )
{
int n1 = M - l + 1 ;
int n2 = R - M ;
int Ł [ n1 ] , R [ n2 ] ;
Do ( int I = 0 ; I < n1 ; I ++ )
Ł [ I ] = arr [ l + I ] ;
Do ( int J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
int I = 0 , J = 0 , k = l ;
chwila ( I < n1 && J < n2 ) {
Jeśli ( Ł [ I ] <= R [ J ] ) {
arr [ k ] = Ł [ I ] ;
I ++;
}
w przeciwnym razie {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
chwila ( I < n1 ) {
arr [ k ] = Ł [ I ] ;
I ++;
k ++;
}
chwila ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
próżnia Połącz Sortuj ( int arr [ ] , int l , int R )
{
Jeśli ( l < R ) {
int M = l + ( R - l ) / 2 ;
Połącz Sortuj ( arr , l , M ) ;
Połącz Sortuj ( arr , M + 1 , R ) ;
łączyć ( arr , l , M , R ) ;
}
}
int główny ( )
{
int arr [ ] = { 12 , jedenaście , 13 , 5 , 6 , 7 } ;
int arr_size = rozmiar ( arr ) / rozmiar ( arr [ 0 ] ) ;
cout << „Podana tablica to \N ' ;
Do ( int I = 0 ; I < arr_size ; I ++ )
cout << arr [ I ] << ' ' ;
Połącz Sortuj ( arr , 0 , arr_size - 1 ) ;
cout << ' \N Posortowana tablica to \N ' ;
Do ( int I = 0 ; I < arr_size ; I ++ )
cout << arr [ I ] << ' ' ;
powrót 0 ;
}
W tym programie funkcja scalania przyjmuje trzy argumenty arr, l i r, które reprezentują tablicę do posortowania i pokazują indeksy podtablicy, która ma zostać scalona. Funkcja najpierw znajduje rozmiary dwóch podtablic do połączenia, a następnie tworzy dwie tymczasowe podtablice L i R do przechowywania elementów tych podtablic. Następnie porównuje elementy w L i R i łączy je z oryginalną tablicą o nazwie arr w kolejności rosnącej.
Technika dziel i zwyciężaj jest wykorzystywana przez funkcję mergeSort do rekurencyjnego dzielenia tablicy na dwie połowy, aż w podtablicy pozostanie tylko jeden element. Następnie łączy te dwie podtablice w posortowaną podtablicę. Funkcja kontynuuje scalanie podtablic, chyba że posortuje całą tablicę.
W funkcji main definiujemy tablicę arr z 6 elementami i wywołujemy funkcję mergeSort, aby ją posortować. Na końcu kodu drukowana jest posortowana tablica.
Metoda 2 — użycie jednej podtablicy tymczasowej
Oto przykładowy program do sortowania przez scalanie w C++ przy użyciu metody 2, która wykorzystuje pojedynczą tymczasową podtablicę:
#includeprzy użyciu przestrzeni nazw std ;
próżnia łączyć ( int arr [ ] , int l , int M , int R )
{
int I , J , k ;
int n1 = M - l + 1 ;
int n2 = R - M ;
// Utwórz tymczasowe podtablice
int Ł [ n1 ] , R [ n2 ] ;
// Skopiuj dane do podtablic
Do ( I = 0 ; I < n1 ; I ++ )
Ł [ I ] = arr [ l + I ] ;
Do ( J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
// Scal tymczasowe podtablice z powrotem w oryginalną tablicę
I = 0 ;
J = 0 ;
k = l ;
chwila ( I < n1 && J < n2 ) {
Jeśli ( Ł [ I ] <= R [ J ] ) {
arr [ k ] = Ł [ I ] ;
I ++;
}
w przeciwnym razie {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
// Skopiuj pozostałe elementy L[]
chwila ( I < n1 ) {
arr [ k ] = Ł [ I ] ;
I ++;
k ++;
}
// Skopiuj pozostałe elementy R[]
chwila ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
próżnia Połącz Sortuj ( int arr [ ] , int l , int R )
{
Jeśli ( l < R ) {
int M = l + ( R - l ) / 2 ;
// Posortuj rekurencyjnie lewą i prawą połowę
Połącz Sortuj ( arr , l , M ) ;
Połącz Sortuj ( arr , M + 1 , R ) ;
// Połącz dwie posortowane połówki
łączyć ( arr , l , M , R ) ;
}
}
int główny ( )
{
int arr [ ] = { 12 , jedenaście , 13 , 5 , 6 , 7 } ;
int arr_size = rozmiar ( arr ) / rozmiar ( arr [ 0 ] ) ;
cout << „Podana tablica to \N ' ;
Do ( int I = 0 ; I < arr_size ; I ++ )
cout << arr [ I ] << ' ' ;
Połącz Sortuj ( arr , 0 , arr_size - 1 ) ;
cout << ' \N Posortowana tablica to \N ' ;
Do ( int I = 0 ; I < arr_size ; I ++ )
cout << arr [ I ] << ' ' ;
powrót 0 ;
}
Ten program jest podobny do poprzedniego, ale zamiast używać dwóch tymczasowych podtablic L i R, używa jednej tymczasowej podtablicy temp. Funkcja scalania działa w taki sam sposób jak poprzednio, ale zamiast kopiować dane do L i R, kopiuje je do temp. Następnie łączy elementy tablicy tymczasowej z powrotem w plik arr która jest oryginalną tablicą.
Funkcja mergeSort jest taka sama jak poprzednio, z tą różnicą, że używa temp zamiast L i R do przechowywania tymczasowej podtablicy.
W funkcji main definiujemy tablicę arr z 6 elementami i wywołujemy funkcję mergeSort, aby ją posortować. Wykonanie kodu kończy się wyświetleniem posortowanej tablicy na ekranie.
Wniosek
Sortowanie przez scalanie to algorytm, który sortuje elementy tablicy i wykorzystuje technikę dziel i zwyciężaj oraz dokonuje porównań między elementami. Sortowanie przez scalanie w C++ ma złożoność czasową O(n log n) i jest szczególnie skuteczne w przypadku sortowania dużych tablic. Chociaż wymaga dodatkowej pamięci do przechowywania połączonych podtablic, jego stabilność sprawia, że jest popularnym wyborem do sortowania.