logo

TechCodeview

Flet sortering – selvstudier om datastruktur og algoritmer

Flet sortering er en sorteringsalgoritme, der følger del-og-hersk nærme sig. Det fungerer ved rekursivt at opdele input-arrayet i mindre subarrays og sortere disse subarrays og derefter flette dem sammen igen for at opnå det sorterede array.

Enkelt sagt kan vi sige, at processen med flette sortering er at opdele arrayet i to halvdele, sortere hver halvdel og derefter flette de sorterede halvdele sammen igen. Denne proces gentages, indtil hele arrayet er sorteret.



Merge-Sort-Algorithm-(1)

Flet sorteringsalgoritme

Hvordan fungerer Merge Sort?

Merge sort er en populær sorteringsalgoritme kendt for sin effektivitet og stabilitet. Den følger del-og-hersk tilgang til at sortere et givet array af elementer.

Her er en trin-for-trin forklaring af, hvordan flettesortering fungerer:



  1. Dele: Del listen eller arrayet rekursivt i to halvdele, indtil det ikke længere kan opdeles.
  2. Erobre: Hvert subarray sorteres individuelt ved hjælp af flettesorteringsalgoritmen.
  3. Fusionere: De sorterede underarrays flettes sammen igen i sorteret rækkefølge. Processen fortsætter, indtil alle elementer fra begge underarrays er blevet flettet.

Illustration af Merge Sort:

Lad os sortere arrayet eller listen [38, 27, 43, 10] ved hjælp af Merge Sort

Lad os se på arbejdet i ovenstående eksempel:

Dele:



  • [38, 27, 43, 10] er opdelt i [38, 27 ] og [43, 10] .
  • [38, 27] er opdelt i [38] og [27] .
  • [43, 10] er opdelt i [43] og [10] .

Erobre:

  • [38] er allerede sorteret.
  • [27] er allerede sorteret.
  • [43] er allerede sorteret.
  • [10] er allerede sorteret.

Fusionere:

  • Fusionere [38] og [27] at få [27, 38] .
  • Fusionere [43] og [10] at få [10.43] .
  • Fusionere [27, 38] og [10.43] for at få den endelige sorterede liste [10, 27, 38, 43]

Derfor er den sorterede liste [10, 27, 38, 43] .

Anbefalet praksis Prøv det!

Implementering af Merge Sort:

C++ 
// C++ program for Merge Sort #include  using namespace std; // Merges two subarrays of array[]. // First subarray is arr[begin..mid] // Second subarray is arr[mid+1..end] void merge(int array[], int const left, int const mid,  int const right) {  int const subArrayOne = mid - left + 1;  int const subArrayTwo = right - mid;  // Create temp arrays  auto *leftArray = new int[subArrayOne],  *rightArray = new int[subArrayTwo];  // Copy data to temp arrays leftArray[] and rightArray[]  for (auto i = 0; i < subArrayOne; i++)  leftArray[i] = array[left + i];  for (auto j = 0; j < subArrayTwo; j++)  rightArray[j] = array[mid + 1 + j];  auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;  int indexOfMergedArray = left;  // Merge the temp arrays back into array[left..right]  while (indexOfSubArrayOne < subArrayOne  && indexOfSubArrayTwo < subArrayTwo) {  if (leftArray[indexOfSubArrayOne]  <= rightArray[indexOfSubArrayTwo]) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  }  else {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  }  indexOfMergedArray++;  }  // Copy the remaining elements of  // left[], if there are any  while (indexOfSubArrayOne < subArrayOne) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  indexOfMergedArray++;  }  // Copy the remaining elements of  // right[], if there are any  while (indexOfSubArrayTwo < subArrayTwo) {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  indexOfMergedArray++;  }  delete[] leftArray;  delete[] rightArray; } // begin is for left index and end is right index // of the sub-array of arr to be sorted void mergeSort(int array[], int const begin, int const end) {  if (begin>= ende) returnere;  int mid = begynde + (slut - begynde) / 2;  mergeSort(array, start, mid);  mergeSort(array, mid + 1, end);  flette (array, begynde, midt, ende); } // UTILITY FUNCTIONS // Funktion til at udskrive et array void printArray(int A[], int size) { for (int i = 0; i< size; i++)  cout << A[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  cout << 'Given array is 
';  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  cout << '
Sorted array is 
';  printArray(arr, arr_size);  return 0; } // This code is contributed by Mayank Tyagi // This code was revised by Joshua Estes>
C 
// C program for Merge Sort #include  #include  // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] 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;  j = 0;  k = l;  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 right index of the // sub-array of arr to be sorted void mergeSort(int arr[], int l, int r) {  if (l < r) {  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);  } } // Function to print an array void printArray(int A[], int size) {  int i;  for (i = 0; i < size; i++)  printf('%d ', A[i]);  printf('
'); } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  printf('Given array is 
');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  printf('
Sorted array is 
');  printArray(arr, arr_size);  return 0; }>
Java 
// Java program for Merge Sort import java.io.*; class MergeSort {  // Merges two subarrays of arr[].  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int arr[], int l, int m, int r)  {  // Find sizes of two subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int L[] = new int[n1];  int R[] = new int[n2];  // Copy data to temp arrays  for (int i = 0; i < n1; ++i)  L[i] = arr[l + i];  for (int j = 0; j < n2; ++j)  R[j] = arr[m + 1 + j];  // Merge the temp arrays  // Initial indices of first and second subarrays  int i = 0, j = 0;  // Initial index of merged subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that sorts arr[l..r] using  // merge()  void sort(int arr[], int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to print array of size n  static void printArray(int arr[])  {  int n = arr.length;  for (int i = 0; i < n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  System.out.println('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.length - 1);  System.out.println('
Sorted array is');  printArray(arr);  } } /* This code is contributed by Rajat Mishra */>
Python 
# Merges two subarrays of array[]. # First subarray is arr[left..mid] # Second subarray is arr[mid+1..right] def merge(array, left, mid, right): subArrayOne = mid - left + 1 subArrayTwo = right - mid # Create temp arrays leftArray = [0] * subArrayOne rightArray = [0] * subArrayTwo # Copy data to temp arrays leftArray[] and rightArray[] for i in range(subArrayOne): leftArray[i] = array[left + i] for j in range(subArrayTwo): rightArray[j] = array[mid + 1 + j] indexOfSubArrayOne = 0 # Initial index of first sub-array indexOfSubArrayTwo = 0 # Initial index of second sub-array indexOfMergedArray = left # Initial index of merged array # Merge the temp arrays back into array[left..right] while indexOfSubArrayOne < subArrayOne and indexOfSubArrayTwo < subArrayTwo: if leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 else: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # Copy the remaining elements of left[], if any while indexOfSubArrayOne < subArrayOne: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 indexOfMergedArray += 1 # Copy the remaining elements of right[], if any while indexOfSubArrayTwo < subArrayTwo: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # begin is for left index and end is right index # of the sub-array of arr to be sorted def mergeSort(array, begin, end): if begin>= end: return mid = begin + (end - start) // 2 mergeSort(array, start, mid) mergeSort(array, mid + 1, end) merge(array, start, mid, end) # Funktion til at udskrive en matrix def printArray(array, størrelse): for i i område(størrelse): print(array[i], end=' ') print() # Driverkode hvis __navn__ == '__main__': arr = [12 , 11, 13, 5, 6, 7] arr_size = len(arr) print('Given array er') printArray(arr, arr_size) mergeSort(arr, 0, arr_size - 1) print('
Sorteret array er') printArray(arr, arr_size)>
C# 
// C# program for Merge Sort using System; class MergeSort {  // Merges two subarrays of []arr.  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int[] arr, int l, int m, int r)  {  // Find sizes of two  // subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int[] L = new int[n1];  int[] R = new int[n2];  int i, j;  // Copy data to temp arrays  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  // Initial indexes of first  // and second subarrays  i = 0;  j = 0;  // Initial index of merged  // subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements  // of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements  // of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that  // sorts arr[l..r] using  // merge()  void sort(int[] arr, int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to  // print array of size n  static void printArray(int[] arr)  {  int n = arr.Length;  for (int i = 0; i < n; ++i)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver code  public static void Main(String[] args)  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  Console.WriteLine('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.Length - 1);  Console.WriteLine('
Sorted array is');  printArray(arr);  } } // This code is contributed by Princi Singh>
Javascript 
// JavaScript program for Merge Sort // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(arr, l, m, r) {  var n1 = m - l + 1;  var n2 = r - m;  // Create temp arrays  var L = new Array(n1);   var R = new Array(n2);  // Copy data to temp arrays L[] and R[]  for (var i = 0; i < n1; i++)  L[i] = arr[l + i];  for (var j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  // Merge the temp arrays back into arr[l..r]  // Initial index of first subarray  var i = 0;  // Initial index of second subarray  var j = 0;  // Initial index of merged subarray  var k = l;  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 // right index of the sub-array // of arr to be sorted function mergeSort(arr,l, r){  if(l>=r){ return;  } var m =l+ parseInt((r-l)/2);  mergeSort(arr,l,m);  mergeSort(arr,m+1,r);  flette(arr,l,m,r); } // Funktion til at udskrive en matrixfunktion printArray( A, størrelse) { for (var i = 0; i< size; i++)  console.log( A[i] + ' '); } var arr = [ 12, 11, 13, 5, 6, 7 ];  var arr_size = arr.length;  console.log( 'Given array is ');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  console.log( 'Sorted array is ');  printArray(arr, arr_size); // This code is contributed by SoumikMondal>
PHP 
 /* PHP recursive program for Merge Sort */ // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(&$arr, $l, $m, $r) { $n1 = $m - $l + 1; $n2 = $r - $m; // Create temp arrays $L = array(); $R = array(); // 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; $j = 0; $k = $l; 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 right index of the // sub-array of arr to be sorted function mergeSort(&$arr, $l, $r) { if ($l < $r) { $m = $l + (int)(($r - $l) / 2); // Sort first and second halves mergeSort($arr, $l, $m); mergeSort($arr, $m + 1, $r); merge($arr, $l, $m, $r); } } // Function to print an array function printArray($A, $size) { for ($i = 0; $i < $size; $i++) echo $A[$i].' '; echo '
'; } // Driver code $arr = array(12, 11, 13, 5, 6, 7); $arr_size = sizeof($arr); echo 'Given array is 
'; printArray($arr, $arr_size); mergeSort($arr, 0, $arr_size - 1); echo '
Sorted array is 
'; printArray($arr, $arr_size); return 0; //This code is contributed by Susobhan Akhuli ?>>
Produktion 
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13>

Kompleksitetsanalyse af fletningssortering:

Tidskompleksitet:

  • Bedste tilfælde: O(n log n), Når arrayet allerede er sorteret eller næsten sorteret.
  • Gennemsnitligt tilfælde: O(n log n), Når arrayet er tilfældigt ordnet.
  • Worst Case: O(n log n), Når arrayet er sorteret i omvendt rækkefølge.

Rumkompleksitet: O(n), Der kræves yderligere plads til det midlertidige array, der bruges under fletning.

Fordele ved Merge Sort:

  • Stabilitet : Merge sort er en stabil sorteringsalgoritme, hvilket betyder, at den bevarer den relative rækkefølge af lige store elementer i input-arrayet.
  • Garanteret worst-case ydeevne: Merge sort har en worst-case tidskompleksitet på O(N logN) , hvilket betyder, at den fungerer godt selv på store datasæt.
  • Enkel at implementere: Del-og-hersk tilgangen er ligetil.

Ulempen ved Merge Sort:

  • Rumkompleksitet: Merge sort kræver yderligere hukommelse til at gemme de flettede underarrays under sorteringsprocessen.
  • Ikke på plads: Merge sort er ikke en in-place sorteringsalgoritme, hvilket betyder, at det kræver yderligere hukommelse til at gemme de sorterede data. Dette kan være en ulempe i applikationer, hvor hukommelsesbrug er et problem.

Anvendelser af Merge Sort:

  • Sortering af store datasæt
  • Ekstern sortering (når datasættet er for stort til at passe i hukommelsen)
  • Inversionstælling (tæller antallet af inversioner i en matrix)
  • Find medianen af ​​et array

Hurtige links:

  • Seneste artikler om Merge Sort
  • Topsortering af interviewspørgsmål og -problemer
  • Øv problemer med sorteringsalgoritme
  • Quiz om Merge Sort