Datenstruktur und Algorithmen - Shell-Sortierung

Die Shell-Sortierung ist ein hocheffizienter Sortieralgorithmus und basiert auf dem Einfügungssortieralgorithmus. Dieser Algorithmus vermeidet große Verschiebungen wie bei der Einfügesortierung, wenn der kleinere Wert ganz rechts liegt und ganz links verschoben werden muss.

Dieser Algorithmus verwendet die Einfügesortierung für weit verbreitete Elemente, um sie zuerst zu sortieren und dann die weniger weit auseinander liegenden Elemente zu sortieren. Dieser Abstand wird als bezeichnetinterval. Dieses Intervall wird basierend auf Knuths Formel als - berechnet

Knuths Formel

h = h * 3 + 1
where −
   h is interval with initial value 1

Dieser Algorithmus ist für mittelgroße Datensätze sehr effizient, da seine durchschnittliche und Worst-Case-Komplexität dieses Algorithmus von der Lückenfolge abhängt, von der die bekannteste Ο (n) ist, wobei n die Anzahl der Elemente ist. Und die Worst-Case-Raumkomplexität ist O (n).

Wie funktioniert Shell Sort?

Betrachten wir das folgende Beispiel, um eine Vorstellung davon zu bekommen, wie die Shell-Sortierung funktioniert. Wir verwenden dasselbe Array, das wir in unseren vorherigen Beispielen verwendet haben. Für unser Beispiel und zum besseren Verständnis nehmen wir das Intervall 4 an. Erstellen Sie eine virtuelle Unterliste aller Werte, die sich im Intervall von 4 Positionen befinden. Hier sind diese Werte {35, 14}, {33, 19}, {42, 27} und {10, 44}.

Wir vergleichen die Werte in jeder Unterliste und tauschen sie (falls erforderlich) im ursprünglichen Array aus. Nach diesem Schritt sollte das neue Array folgendermaßen aussehen:

Dann nehmen wir das Intervall 1 und diese Lücke erzeugt zwei Unterlisten - {14, 27, 35, 42}, {19, 10, 33, 44}

Wir vergleichen und tauschen die Werte bei Bedarf im ursprünglichen Array aus. Nach diesem Schritt sollte das Array folgendermaßen aussehen:

Schließlich sortieren wir den Rest des Arrays nach dem Intervall von Wert 1. Die Shell-Sortierung verwendet die Einfügesortierung, um das Array zu sortieren.

Es folgt die schrittweise Darstellung -

Wir sehen, dass nur vier Swaps erforderlich waren, um den Rest des Arrays zu sortieren.

Algorithmus

Es folgt der Algorithmus für die Shell-Sortierung.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocode

Es folgt der Pseudocode für die Shell-Sortierung.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Klicken Sie hier , um Informationen zur Implementierung der Shell-Sortierung in der Programmiersprache C zu erhalten .