Datenstrukturen - Sortieralgorithmus zusammenführen

Die Zusammenführungssortierung ist eine Sortiertechnik, die auf der Teilungs- und Eroberungstechnik basiert. Mit der Worst-Case-Zeitkomplexität von Ο (n log n) ist dies einer der am meisten respektierten Algorithmen.

Die Zusammenführungssortierung teilt das Array zunächst in gleiche Hälften und kombiniert sie dann sortiert.

Wie funktioniert die Sortierung zusammenführen?

Um die Zusammenführungssortierung zu verstehen, nehmen wir ein unsortiertes Array wie folgt:

Wir wissen, dass die Zusammenführungssortierung zuerst das gesamte Array iterativ in gleiche Hälften teilt, sofern die Atomwerte nicht erreicht werden. Wir sehen hier, dass ein Array von 8 Elementen in zwei Arrays der Größe 4 unterteilt ist.

Dies ändert nichts an der Reihenfolge des Erscheinungsbilds von Elementen im Original. Nun teilen wir diese beiden Arrays in zwei Hälften.

Wir teilen diese Arrays weiter und erreichen einen Atomwert, der nicht mehr geteilt werden kann.

Jetzt kombinieren wir sie genauso, wie sie zerlegt wurden. Bitte beachten Sie die Farbcodes in diesen Listen.

Wir vergleichen zuerst das Element für jede Liste und kombinieren sie dann sortiert zu einer anderen Liste. Wir sehen, dass 14 und 33 in sortierten Positionen sind. Wir vergleichen 27 und 10 und setzen in der Zielliste von 2 Werten zuerst 10, gefolgt von 27. Wir ändern die Reihenfolge von 19 und 35, während 42 und 44 nacheinander platziert werden.

In der nächsten Iteration der Kombinationsphase vergleichen wir Listen mit zwei Datenwerten und führen sie zu einer Liste gefundener Datenwerte zusammen, die alle in einer sortierten Reihenfolge angeordnet sind.

Nach dem endgültigen Zusammenführen sollte die Liste folgendermaßen aussehen:

Jetzt sollten wir einige Programmieraspekte der Zusammenführungssortierung lernen.

Algorithmus

Die Zusammenführungssortierung teilt die Liste so lange in gleiche Hälften, bis sie nicht mehr geteilt werden kann. Wenn es sich per Definition nur um ein Element in der Liste handelt, wird es sortiert. Beim Zusammenführen der Sortierung werden dann die kleineren sortierten Listen kombiniert, wobei auch die neue Liste sortiert bleibt.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocode

Wir werden nun die Pseudocodes für Sortierfunktionen zum Zusammenführen sehen. Wie unsere Algorithmen zeigen, sind zwei Hauptfunktionen - Teilen und Zusammenführen.

Die Zusammenführungssortierung funktioniert mit Rekursion, und wir werden unsere Implementierung auf die gleiche Weise sehen.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Klicken Sie hier , um Informationen zur Implementierung der Zusammenführungssortierung in der Programmiersprache C zu erhalten .