EN KÖTÜ BIRLEŞTIRME DURUMUNA NEDEN OLAN BIR PERMÜTASYON BULUN

Bir dizi element göz önüne alındığında, bu elemanların hangi permütasyonunun en kötü birleştirme türü ile sonuçlanacağını bulur.
Asimptotik olarak birleştirme sırası her zaman o (n log n) zaman alır, ancak daha fazla karşılaştırma gerektiren durumlar genellikle pratikte daha fazla zaman alır. Temel olarak, tipik bir birleştirme sıralama algoritması kullanılarak sıralandığında maksimum karşılaştırmaya yol açacak giriş elemanlarının bir permütasyonu bulmamız gerekir.

Örnek:

Consider the below set of elements   
{1 2 3 4 5 6 7 8 9 10 11 12   
 13 14 15 16}  
  
Below permutation of the set causes 153  
comparisons.  
{1 9 5 13 3 11 7 15 2 10 6   
 14 4 12 8 16}  
  
And an already sorted permutation causes  
30 comparisons.

Şimdi bir giriş seti için birleştirme sırası için en kötü durum girişi nasıl elde edilir?

Diziyi aşağıdan yukarıya doğru oluşturmaya çalışalım
Sıralı dizinin {12345678} olsun.

En kötü birleştirme durumunu oluşturmak için yukarıda sıralanan dizi ile sonuçlanan birleştirme işlemi maksimum karşılaştırmalarla sonuçlanmalıdır. Bunu yapmak için birleştirme işleminde yer alan sol ve sağ alt diz, sıralı dizi alternatif öğelerini saklamalıdır. yani sol alt payda {1357} ve sağ alt dizisi {2468} olmalıdır. Şimdi dizinin her unsuru bir kez olası karşılaştırılacak ve bu da maksimum karşılaştırmalarla sonuçlanacaktır. Sol ve sağ alt diziye de aynı mantığı uyguluyoruz. {1357} dizisi için en kötü durum sol ve sağ alt dizisi sırasıyla {15} ve {37} olduğunda ve {2468} dizisi için {24} ve {68} için en kötü durum olacaktır.

Tam Algoritma -
GenerateWorstcase (arr [])

Sol ve sağ iki yardımcı dizi oluşturun ve bunlarda alternatif dizi öğeleri saklayın.
Sol SubArray için GenerateWorstcase'yi arayın: GenerateWorstcase (sol)
Doğru SubArray için GenerateWorstcase'yi arayın: GenerateWorstcase (sağ)
Sol ve sağ alt öğelerin tüm öğelerini orijinal diziye geri kopyalayın.

Aşağıda fikrin uygulanması

C++

// C++ program to generate Worst Case // of Merge Sort #include    using namespace std; // Function to print an array void printArray(int A[] int size) {  for(int i = 0; i < size; i++)  {  cout << A[i] << ' ';  }  cout << endl; } // Function to join left and right subarray int join(int arr[] int left[] int right[]  int l int m int r) {  int i;  for(i = 0; i <= m - l; i++)  arr[i] = left[i];  for(int j = 0; j < r - m; j++)  {  arr[i + j] = right[j];  } } // Function to store alternate elements in // left and right subarray int split(int arr[] int left[] int right[]  int l int m int r) {  for(int i = 0; i <= m - l; i++)  left[i] = arr[i * 2];  for(int i = 0; i < r - m; i++)  right[i] = arr[i * 2 + 1]; } // Function to generate Worst Case  // of Merge Sort int generateWorstCase(int arr[] int l  int r) {  if (l < r)  {  int m = l + (r - l) / 2;  // Create two auxiliary arrays  int left[m - l + 1];  int right[r - m];  // Store alternate array elements   // in left and right subarray  split(arr left right l m r);  // Recurse first and second halves  generateWorstCase(left l m);  generateWorstCase(right m + 1 r);  // Join left and right subarray  join(arr left right l m r);  } } // Driver code int main() {    // Sorted array  int arr[] = { 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 };    int n = sizeof(arr) / sizeof(arr[0]);  cout << 'Sorted array is n';  printArray(arr n);  // Generate Worst Case of Merge Sort  generateWorstCase(arr 0 n - 1);  cout << 'nInput array that will result '  << 'in worst case of merge sort is n';    printArray(arr n);  return 0; } // This code is contributed by Mayank Tyagi

// C program to generate Worst Case of Merge Sort  #include   #include   // Function to print an array  void printArray(int A[] int size)  {   for (int i = 0; i < size; i++)   printf('%d ' A[i]);   printf('n');  }  // Function to join left and right subarray  int join(int arr[] int left[] int right[]   int l int m int r)  {   int i; // Used in second loop   for (i = 0; i <= m - l; i++)   arr[i] = left[i];   for (int j = 0; j < r - m; j++)   arr[i + j] = right[j];  }  // Function to store alternate elements in left  // and right subarray  int split(int arr[] int left[] int right[]   int l int m int r)  {   for (int i = 0; i <= m - l; i++)   left[i] = arr[i * 2];   for (int i = 0; i < r - m; i++)   right[i] = arr[i * 2 + 1];  }  // Function to generate Worst Case of Merge Sort  int generateWorstCase(int arr[] int l int r)  {   if (l < r)   {   int m = l + (r - l) / 2;   // create two auxiliary arrays   int left[m - l + 1];   int right[r - m];   // Store alternate array elements in left   // and right subarray   split(arr left right l m r);   // Recurse first and second halves   generateWorstCase(left l m);   generateWorstCase(right m + 1 r);   // join left and right subarray   join(arr left right l m r);   }  }  // Driver code  int main()  {   // Sorted array   int arr[] = { 1 2 3 4 5 6 7 8 9   10 11 12 13 14 15 16 };   int n = sizeof(arr) / sizeof(arr[0]);   printf('Sorted array is n');   printArray(arr n);   // generate Worst Case of Merge Sort   generateWorstCase(arr 0 n - 1);   printf('nInput array that will result in '  'worst case of merge sort is n');   printArray(arr n);   return 0;  }

Java

// Java program to generate Worst Case of Merge Sort import java.util.Arrays; class GFG  {  // Function to join left and right subarray  static void join(int arr[] int left[] int right[]  int l int m int r)  {  int i;  for (i = 0; i <= m - l; i++)  arr[i] = left[i];    for (int j = 0; j < r - m; j++)  arr[i + j] = right[j];  }    // Function to store alternate elements in left  // and right subarray  static void split(int arr[] int left[] int right[]  int l int m int r)  {  for (int i = 0; i <= m - l; i++)  left[i] = arr[i * 2];    for (int i = 0; i < r - m; i++)  right[i] = arr[i * 2 + 1];  }    // Function to generate Worst Case of Merge Sort  static void generateWorstCase(int arr[] int l int r)  {  if (l < r)  {  int m = l + (r - l) / 2;    // create two auxiliary arrays  int[] left = new int[m - l + 1];  int[] right = new int[r - m];    // Store alternate array elements in left  // and right subarray  split(arr left right l m r);    // Recurse first and second halves  generateWorstCase(left l m);  generateWorstCase(right m + 1 r);    // join left and right subarray  join(arr left right l m r);  }  }    // driver program  public static void main (String[] args)   {  // sorted array  int arr[] = { 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 };  int n = arr.length;  System.out.println('Sorted array is');  System.out.println(Arrays.toString(arr));    // generate Worst Case of Merge Sort  generateWorstCase(arr 0 n - 1);    System.out.println('nInput array that will result in n'+  'worst case of merge sort is n');    System.out.println(Arrays.toString(arr));  } } // Contributed by Pramod Kumar

Python

# Python program to generate Worst Case of Merge Sort # Function to join left and right subarray def join(arr left right l m r): i = 0; for i in range(m-l+1): arr[i] = left[i]; i+=1; for j in range(r-m): arr[i + j] = right[j]; # Function to store alternate elements in left # and right subarray def split(arr left right l m r): for i in range(m-l+1): left[i] = arr[i * 2]; for i in range(r-m): right[i] = arr[i * 2 + 1]; # Function to generate Worst Case of Merge Sort def generateWorstCase(arr l r): if (l < r): m = l + (r - l) // 2; # create two auxiliary arrays left = [0 for i in range(m - l + 1)]; right = [0 for i in range(r-m)]; # Store alternate array elements in left # and right subarray split(arr left right l m r); # Recurse first and second halves generateWorstCase(left l m); generateWorstCase(right m + 1 r); # join left and right subarray join(arr left right l m r); # driver program if __name__ == '__main__': # sorted array arr = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]; n = len(arr); print('Sorted array is'); print(arr); # generate Worst Case of Merge Sort generateWorstCase(arr 0 n - 1); print('nInput array that will result in n' + 'worst case of merge sort is '); print(arr); # This code contributed by shikhasingrajput

// C# program to generate Worst Case of // Merge Sort using System; class GFG {    // Function to join left and right subarray  static void join(int []arr int []left   int []right int l int m int r)  {  int i;  for (i = 0; i <= m - l; i++)  arr[i] = left[i];  for (int j = 0; j < r - m; j++)  arr[i + j] = right[j];  }  // Function to store alternate elements in  // left and right subarray  static void split(int []arr int []left  int []right int l int m int r)  {  for (int i = 0; i <= m - l; i++)  left[i] = arr[i * 2];  for (int i = 0; i < r - m; i++)  right[i] = arr[i * 2 + 1];  }    // Function to generate Worst Case of   // Merge Sort  static void generateWorstCase(int []arr   int l int r)  {  if (l < r)  {  int m = l + (r - l) / 2;  // create two auxiliary arrays  int[] left = new int[m - l + 1];  int[] right = new int[r - m];  // Store alternate array elements  // in left and right subarray  split(arr left right l m r);  // Recurse first and second halves  generateWorstCase(left l m);  generateWorstCase(right m + 1 r);  // join left and right subarray  join(arr left right l m r);  }  }    // driver program  public static void Main ()   {    // sorted array  int []arr = { 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 };    int n = arr.Length;  Console.Write('Sorted array isn');    for(int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');    // generate Worst Case of Merge Sort  generateWorstCase(arr 0 n - 1);  Console.Write('nInput array that will '  + 'result in n worst case of'  + ' merge sort is n');    for(int i = 0; i < n; i++)  Console.Write(arr[i] + ' ');  } } // This code is contributed by Smitha

JavaScript

<script>  // javascript program to generate Worst Case  // of Merge Sort  // Function to print an array  function printArray(Asize)  {  for(let i = 0; i < size; i++)  {  document.write(A[i] + ' ');  }  }  // Function to join left and right subarray  function join(arrleftrightlmr)  {  let i;  for(i = 0; i <= m - l; i++)  arr[i] = left[i];  for(let j = 0; j < r - m; j++)  {  arr[i + j] = right[j];  }  }  // Function to store alternate elements in  // left and right subarray  function split(arrleftrightlmr)  {  for(let i = 0; i <= m - l; i++)  left[i] = arr[i * 2];  for(let i = 0; i < r - m; i++)  right[i] = arr[i * 2 + 1];  }  // Function to generate Worst Case  // of Merge Sort  function generateWorstCase(arrlr)  {  if (l < r)  {  let m = l + parseInt((r - l) / 2 10);  // Create two auxiliary arrays  let left = new Array(m - l + 1);  let right = new Array(r - m);  left.fill(0);  right.fill(0);  // Store alternate array elements  // in left and right subarray  split(arr left right l m r);  // Recurse first and second halves  generateWorstCase(left l m);  generateWorstCase(right m + 1 r);  // Join left and right subarray  join(arr left right l m r);  }  }    let arr = [1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16 ];   let n = arr.length;  document.write('Sorted array is' + '
');  printArray(arr n);  // Generate Worst Case of Merge Sort  generateWorstCase(arr 0 n - 1);  document.write('
' + 'Input array that will result '  + 'in worst case of merge sort is' + '
');    printArray(arr n);    // This code is contributed by vaibhavrabadiya117. </script>

Çıktı:

Sorted array is   
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16   
  
Input array that will result in worst   
case of merge sort is   
1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16

Zaman karmaşıklığı: o (n logn)
Yardımcı Alan: O (N)
Referanslar - Stack Taşma

TechCodeview

En kötü birleştirme durumuna neden olan bir permütasyon bulun