Merge Sort Algorithm - Java, C dhe Python Implementation
Renditja e bashkimit është një nga algoritmet më efikase të renditjes. Ai funksionon në parimin e Përça dhe sundo bazuar në idenë e zbërthimit të një liste në disa nën-lista derisa secila nënlistë të përbëhet nga një element i vetëm dhe t'i bashkojë ato nënlista në një mënyrë që rezulton në një renditje listë.
Rregulli i punës së renditjes së bashkimit
Koncepti Divide and Conquer përfshin tre hapa:
- Ndajeni problemin në nënprobleme të shumta.
- Zgjidhni nënproblemet. Ideja është të zbërthehet problemi në nënprobleme atomike, ku ato zgjidhen në të vërtetë.
- Kombinoni zgjidhjet e nënproblemave për të gjetur zgjidhjen e problemit aktual.
Pra, rregulli i punës së renditjes së bashkimit përfshin hapat e mëposhtëm:
- Ndani grupin e pazbërthyer në nëngrup, secila përmban një element të vetëm.
- Merrni çifte ngjitur me dy vargje me një element dhe bashkojini për të formuar një grup prej 2 elementësh.
- Përsëriteni procesin derisa të merret një grup i vetëm i renditur.
Një grup i madhësisë 'N' ndahet në dy pjesë me madhësinë 'N/2' të secilës. atëherë ato vargje ndahen më tej derisa të arrijmë në një element të vetëm. Rasti bazë këtu po arrin një element të vetëm. Kur rasti bazë goditet, fillojmë të bashkojmë pjesën e majtë dhe të djathtën dhe marrim një grup të renditur në fund. Renditja e bashkimit zbërthen në mënyrë të përsëritur një grup në disa nëngarkesa derisa secila nëngarkesa përbëhet nga një element i vetëm dhe bashkon ato nëngarkesa në një mënyrë që rezulton në një grup të renditur.
Merge Sort Algorithm Flow
Grup={70,50,30,10,20,40,60}
Ne e ndajmë në mënyrë të përsëritur grupin në dy pjesë, pjesën e majtë dhe pjesën e djathtë. ndarja bëhet nga elementi i mesit. Ndajmë derisa të arrijmë një element të vetëm dhe më pas fillojmë t'i kombinojmë për të formuar një varg të sortuar.
Zbatimet e renditjes së bashkimit
Ne do të zbatojmë algoritmin e renditjes së bashkimit në Java, C dhe Python.
1. Implementimi Java
package com.journaldev.ds;
public class MergeSort {
public static void main(String[] args) {
int[] arr = { 70, 50, 30, 10, 20, 40, 60 };
int[] merged = mergeSort(arr, 0, arr.length - 1);
for (int val : merged) {
System.out.print(val + " ");
}
}
public static int[] mergeTwoSortedArrays(int[] one, int[] two) {
int[] sorted = new int[one.length + two.length];
int i = 0;
int j = 0;
int k = 0;
while (i < one.length && j < two.length) {
if (one[i] < two[j]) {
sorted[k] = one[i];
k++;
i++;
} else {
sorted[k] = two[j];
k++;
j++;
}
}
if (i == one.length) {
while (j < two.length) {
sorted[k] = two[j];
k++;
j++;
}
}
if (j == two.length) {
while (i < one.length) {
sorted[k] = one[i];
k++;
i++;
}
}
return sorted;
}
public static int[] mergeSort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] br = new int[1];
br[0] = arr[lo];
return br;
}
int mid = (lo + hi) / 2;
int[] fh = mergeSort(arr, lo, mid);
int[] sh = mergeSort(arr, mid + 1, hi);
int[] merged = mergeTwoSortedArrays(fh, sh);
return merged;
}
}
OUTPUT
2. C Zbatimi
#include <stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is the right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {70, 50, 30, 10, 20, 40,60};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
OUTPUT
3. Zbatimi i Python
def merge_sort(unsorted_array):
if len(unsorted_array) > 1:
mid = len(unsorted_array) // 2 # Finding the mid of the array
left = unsorted_array[:mid] # Dividing the array elements
right = unsorted_array[mid:] # into 2 halves
merge_sort(left)
merge_sort(right)
i = j = k = 0
# data to temp arrays L[] and R[]
while i < len(left) and j < len(right):
if left[i] < right[j]:
unsorted_array[k] = left[i]
i += 1
else:
unsorted_array[k] = right[j]
j += 1
k += 1
# Checking if any element was left
while i < len(left):
unsorted_array[k] = left[i]
i += 1
k += 1
while j < len(right):
unsorted_array[k] = right[j]
j += 1
k += 1
# Code to print the list
def print_list(array1):
for i in range(len(array1)):
print(array1[i], end=" ")
print()
# driver code to test the above code
if __name__ == '__main__':
array = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
print_list(array)
merge_sort(array)
print("Sorted array is: ", end="\n")
print_list(array)
OUTPUT
Kompleksiteti i Kompleksitetit të Kohës dhe Hapësirës së Renditimit
1. Kompleksiteti i hapësirës
Hapësira ndihmëse: O(n) Renditja në vend: Pa algoritëm: Përça dhe sundo
2. Kompleksiteti i kohës
Merge Sort është një algoritëm rekurziv dhe kompleksiteti kohor mund të shprehet si relacioni vijues i përsëritjes. T(n)=2T(n/2) + O(n) Zgjidhja e përsëritjes së mësipërme është O(nLogn). Lista e madhësisë N ndahet në një maksimum pjesësh Logn, dhe bashkimi i të gjitha nënlistave në një listë të vetme kërkon kohë O(N), koha më e keqe e ekzekutimit të këtij algoritmi është O(nLogn) Kompleksiteti i kohës më të mirë të rastit: O(n*log n) Kompleksiteti kohor i rastit më të keq: O(n*log n) Kompleksiteti mesatar i kohës: O(n*log n) Kompleksiteti kohor i MergeSort është O(n*Log n) në të 3 rastet (më e keqja, mesatare dhe më e mira) pasi bashkimi gjithmonë e ndan grupin në dy gjysma dhe kërkon kohë lineare për të bashkuar dy gjysma. Lexime të mëtejshme:
- Shkrija e renditjes së faqes së Wikipedia-s
- Renditja me flluska në Java
- Renditja e futjes në Java