Въведение в алгоритъма за сортиране на сливане

Въведение в алгоритъма за сортиране на сливане

Merge sort е алгоритъм за сортиране, базиран на техниката „разделяй и владей“. Това е един от най -ефективните алгоритми за сортиране.





компютърът няма да се свърже с wifi windows 10

В тази статия ще научите за работата на алгоритъма за сортиране на сливане, алгоритъма за сортиране на сливането, сложността му по време и пространство и неговото прилагане в различни езици за програмиране като C ++, Python и JavaScript.



Как работи алгоритъмът за сортиране на сливане?

Сортирането с обединяване работи на принципа на разделяй и владей. Сортирането при обединяване многократно разбива масив на два равни подмасива, докато всеки подмасив се състои от един елемент. И накрая, всички тези подмасиви се обединяват така, че полученият масив се сортира.





Тази концепция може да бъде обяснена по -ефективно с помощта на пример. Помислете за несортиран масив със следните елементи: {16, 12, 15, 13, 19, 17, 11, 18}.

Тук алгоритъмът за сортиране на сливане разделя масива на две половини, извиква себе си за двете половини и след това обединява двете сортирани половини.



Обединяване на алгоритъма за сортиране

По -долу е алгоритъмът за сортиране на сливане:

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)

Свързани: Какво е рекурсия и как я използвате?



Времево -пространствена сложност на алгоритъма за сортиране на сливане

Алгоритъмът за сортиране на сливане може да бъде изразен под формата на следната рекурентна връзка:

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



След като решите тази рецидивираща връзка, използвайки теоремата на главния или метода на рекурсивното дърво, ще получите решението като O (n logn). По този начин времевата сложност на алгоритъма за сортиране на сливане е O (n вход) .

Най-добрата времева сложност на сорта на сливане: O (n вход)

Сложността на средната продължителност на случая при сортирането на сливане: O (n вход)

Най-лошата времева сложност на сорта на сливане: O (n вход)

Свързани: Какво е Big-O нотация?

Сложността на спомагателното пространство на алгоритъма за сортиране на сливане е На) като н допълнително пространство е необходимо при реализацията на сортиране на сливане.

C ++ Прилагане на алгоритъма за сортиране на сливане

По -долу е 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;
}

Изход:

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

JavaScript внедряване на алгоритъма за сортиране на обединяване

По -долу е JavaScript реализацията на алгоритъма за сортиране на сливане:

// 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);

Изход:

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

Свързани: Динамично програмиране: Примери, често срещани проблеми и решения

Python внедряване на алгоритъма за сортиране на сливане

По -долу е Python реализацията на алгоритъма за сортиране на сливане:

# 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)

Изход:

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

Разберете други алгоритми за сортиране

Сортирането е един от най -използваните алгоритми в програмирането. Можете да сортирате елементи на различни езици за програмиране, като използвате различни алгоритми за сортиране като бързо сортиране, сортиране с балончета, сортиране с обединяване, сортиране на вмъкване и т.н.

Сортирането на балончета е най -добрият избор, ако искате да научите за най -простия алгоритъм за сортиране.

Дял Дял Туит електронна поща Въведение в алгоритъма за сортиране на балончета

Алгоритъмът за сортиране на балончета: отлично въведение в сортиращите масиви.

Прочетете Напред Свързани теми
  • Програмиране
  • JavaScript
  • Python
  • Уроци по кодиране
За автора Юврадж Чандра(60 статии са публикувани)

Юврадж е студент по компютърни науки в Университета в Делхи, Индия. Той е страстен за Full Stack Web Development. Когато не пише, той изследва дълбочината на различните технологии.

Още от Yuvraj Chandra

Абонирайте се за нашия бюлетин

Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и изключителни оферти!

Щракнете тук, за да се абонирате