Wprowadzenie do algorytmu sortowania przez scalanie

Sortowanie przez scalanie to algorytm sortowania oparty na technice „dziel i rządź”. To jeden z najbardziej wydajnych algorytmów sortowania.

jak stworzyć nowy adres e-mail

W tym artykule dowiesz się o działaniu algorytmu sortowania przez scalanie, algorytmie sortowania przez scalanie, jego złożoności czasowej i przestrzennej oraz jego implementacji 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
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)

Powiązane: 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 (n zaloguj) .

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

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

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

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

Złożoność przestrzeni pomocniczej algorytmu sortowania przez scalanie jest Na) jak n 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++:

// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}

// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
}

Wyjście:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Implementacja JavaScript algorytmu sortowania przez scalanie

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

// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size);

Wyjście:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Powiązane: 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:

# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()

# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)


Wyjście:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
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.

Udział Udział Ćwierkać E-mail Wprowadzenie do algorytmu sortowania bąbelkowego

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

Czytaj dalej Powiązane tematy

• Programowanie
• JavaScript
• Pyton
• Poradniki kodowania

O autorze Yuvraj Chandra(60 opublikowanych artykułów)

Yuvraj jest studentem informatyki na Uniwersytecie w Delhi w Indiach. Jest pasjonatem Full Stack Web Development. Kiedy nie pisze, bada głębię różnych technologii.

Więcej od Yuvraja Chandra

Zapisz się do naszego newslettera

Dołącz do naszego newslettera, aby otrzymywać porady techniczne, recenzje, bezpłatne e-booki i ekskluzywne oferty!

Kliknij tutaj, aby zasubskrybować