Heim > Backend-Entwicklung > C++ > Hauptteil

C/C++-Programm, das mit dem Merge-Sort-Algorithmus geschrieben wurde, um umgekehrte Zahlen in einem Array zu berechnen

PHPz
Freigeben: 2023-08-25 19:33:28
nach vorne
1064 Leute haben es durchsucht

C/C++-Programm, das mit dem Merge-Sort-Algorithmus geschrieben wurde, um umgekehrte Zahlen in einem Array zu berechnen

Die invertierte Darstellung eines Arrays; wie viele Änderungen sind erforderlich, um das Array in seine sortierte Form umzuwandeln. Wenn das Array bereits sortiert ist, sind 0 Umkehrungen erforderlich, während in anderen Fällen, wenn das Array umgekehrt ist, die maximale Anzahl an Umkehrungen erreicht wird.

Um dieses Problem zu lösen, folgen wir der Merge-Sortier-Methode, um die zeitliche Komplexität zu reduzieren, und verwenden den Divide-and-Conquer-Algorithmus.

Eingabe

A sequence of numbers. (1, 5, 6, 4, 20).
Nach dem Login kopieren

Ausgabe

Die Anzahl der Umkehrungen, die erforderlich sind, um die Zahlen in aufsteigender Reihenfolge zu sortieren.

Here the number of inversions are 2.
First inversion: (1, 5, 4, 6, 20)
Second inversion: (1, 4, 5, 6, 20)
Nach dem Login kopieren

Algorithmus

merge(array, tempArray, left, mid, right)

Input – zwei Arrays, die zusammengeführt wurden, linker, rechter und mittlerer Index.

Ausgabe – zusammengeführte Arrays in sortierter Reihenfolge.

Begin
   i := left, j := mid, k := right
   count := 0
   while i <= mid -1 and j <= right, do
      if array[i] <= array[j], then
         tempArray[k] := array[i]
         increase i and k by 1
      else
         tempArray[k] := array[j]
         increase j and k by 1
         count := count + (mid - i)
   done
   while left part of the array has some extra element, do
      tempArray[k] := array[i]
      increase i and k by 1
   done
   while right part of the array has some extra element, do
      tempArray[k] := array[j]
      increase j and k by 1
   done
   return count
End
Nach dem Login kopieren

mergeSort(array, tempArray, left, right)

Eingabe - Gegeben ein Array und ein temporäres Array, der linke und der rechte Index des Arrays.

Ausgabe – Die Anzahl der umgekehrt geordneten Paare nach dem Sortieren.

Begin
   count := 0
   if right > left, then
      mid := (right + left)/2
      count := mergeSort(array, tempArray, left, mid)
      count := count + mergeSort(array, tempArray, mid+1, right)
      count := count + merge(array, tempArray, left, mid+1, right)
   return count
End
Nach dem Login kopieren

Beispiel

Echtzeitdemonstration

#include <iostream>
using namespace std;
int merge(int arr[], int temp[], int left, int mid, int right) {
   int i, j, k;
   int count = 0;
   i = left; //i to locate first array location
   j = mid; //i to locate second array location
   k = left; //i to locate merged array location
   while ((i <= mid - 1) && (j <= right)) {
      if (arr[i] <= arr[j]){ //when left item is less than right item
      temp[k++] = arr[i++];
      } else {
         temp[k++] = arr[j++];
         count += (mid - i); //find how many convertion is performed
      }
   }
   while (i <= mid - 1) //if first list has remaining item, add them in the list
      temp[k++] = arr[i++];
   while (j <= right) //if second list has remaining item, add them in the list
      temp[k++] = arr[j++];
   for (i=left; i <= right; i++)
      arr[i] = temp[i]; //store temp Array to main array
   return count;
}
int mergeSort(int arr[], int temp[], int left, int right){
   int mid, count = 0;
   if (right > left) {
      mid = (right + left)/2; //find mid index of the array
      count = mergeSort(arr, temp, left, mid); //merge sort left sub array
      count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
      count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
   }
   return count;
}
int arrInversion(int arr[], int n) {
   int temp[n];
   return mergeSort(arr, temp, 0, n - 1);
}
int main() {
   int arr[] = {1, 5, 6, 4, 20};
   int n = 5;
   cout << "Number of inversions are "<< arrInversion(arr, n);
}
Nach dem Login kopieren

Ausgabe

Number of inversions are 2
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonC/C++-Programm, das mit dem Merge-Sort-Algorithmus geschrieben wurde, um umgekehrte Zahlen in einem Array zu berechnen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage