Shell Sort

In diesem Tutorial erfahren Sie, wie die Shell-Sortierung funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Shell-Sortierung in C, C ++, Java und Python.

Die Shell-Sortierung ist ein Algorithmus, der zuerst die Elemente weit voneinander entfernt sortiert und nacheinander das Intervall zwischen den zu sortierenden Elementen verringert. Es ist eine verallgemeinerte Version der Einfügesortierung.

Bei der Shell-Sortierung werden Elemente in einem bestimmten Intervall sortiert. Das Intervall zwischen den Elementen wird basierend auf der verwendeten Reihenfolge allmählich verringert. Die Leistung der Shell-Sortierung hängt von der Art der Sequenz ab, die für ein bestimmtes Eingabearray verwendet wird.

Einige der optimalen Sequenzen sind:

  • Shells ursprüngliche Sequenz: N/2 , N/4 ,… , 1
  • Knuths Inkremente: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewicks Inkremente: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbards Inkremente: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov & Stasevich Inkrement: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Wie funktioniert Shell Sort?

  1. Angenommen, wir müssen das folgende Array sortieren. Anfängliches Array
  2. Wir verwenden die ursprüngliche Sequenz der Shell (N/2, N/4,… 1als Intervalle in unserem Algorithmus.
    Wenn in der ersten Schleife die Arraygröße N = 8dann ist, werden die im Intervall von liegenden Elemente N/2 = 4verglichen und ausgetauscht, wenn sie nicht in Ordnung sind.
    1. Das 0. Element wird mit dem 4. Element verglichen.
    2. Wenn das 0. Element größer als das 4. ist, wird das 4. Element zuerst in einer tempVariablen gespeichert und das 0thElement (dh ein größeres Element) wird an der 4thPosition gespeichert und das Element, das in tempgespeichert ist, wird an der 0thPosition gespeichert . Ordnen Sie die Elemente im Intervall von n / 2 neu an.
      Dieser Vorgang wird für alle verbleibenden Elemente fortgesetzt. Ordnen Sie alle Elemente im Abstand von n / 2 neu an
  3. In der zweiten Schleife wird ein Intervall von N/4 = 8/4 = 2genommen und wieder werden die in diesen Intervallen liegenden Elemente sortiert. Ordnen Sie die Elemente im Abstand von n / 4 neu
    an. An dieser Stelle können Sie verwirrt sein. Alle Elemente im Array, die im aktuellen Intervall liegen, werden verglichen.
    Die Elemente an 4. und 2ndPosition werden verglichen. Die Elemente an 2. und 0thPosition werden ebenfalls verglichen. Alle Elemente im Array, die im aktuellen Intervall liegen, werden verglichen.
  4. Der gleiche Vorgang wird für die verbleibenden Elemente fortgesetzt. Ordnen Sie alle Elemente im Abstand von n / 4 neu an
  5. Wenn schließlich das Intervall ist, werden N/8 = 8/8 =1die Array-Elemente, die im Intervall von 1 liegen, sortiert. Das Array ist jetzt vollständig sortiert. Ordnen Sie die Elemente im Abstand von n / 8 neu an

Shell-Sortieralgorithmus

 shellSort (Array, Größe) für Intervall i <- Größe / 2n bis 1 für jedes Intervall "i" im Array sortieren alle Elemente im Intervall "i" und ShellSort

Beispiele für Python, Java und C / C ++

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Komplexität

Die Shell-Sortierung ist ein instabiler Sortieralgorithmus, da dieser Algorithmus die zwischen den Intervallen liegenden Elemente nicht untersucht.

Zeitliche Komplexität

  • Worst-Case-Komplexität : kleiner oder gleich Worst-Case-Komplexität für die Shell-Sortierung ist immer kleiner oder gleich . Nach dem Poonen-Theorem ist die Komplexität im schlimmsten Fall für die Shell-Sortierung oder oder oder etwas dazwischen.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Best-Case-Komplexität : O(n*log n)
    Wenn das Array bereits sortiert ist, entspricht die Gesamtzahl der Vergleiche für jedes Intervall (oder Inkrement) der Größe des Arrays.
  • Durchschnittliche Komplexität der Fälle : O(n*log n)
    Es gibt sie .O(n1.25)

Die Komplexität hängt vom gewählten Intervall ab. Die obigen Komplexitäten unterscheiden sich für verschiedene ausgewählte Inkrementsequenzen. Die beste Inkrementsequenz ist unbekannt.

Raumkomplexität:

Die Raumkomplexität für die Shell-Sortierung ist O(1).

Shell-Sortieranwendungen

Die Shell-Sortierung wird verwendet, wenn:

  • Das Aufrufen eines Stapels ist Overhead. Die uClibc-Bibliothek verwendet diese Sortierung.
  • Rekursion überschreitet eine Grenze. Der bzip2-Kompressor verwendet es.
  • Die Einfügesortierung funktioniert nicht gut, wenn die nahen Elemente weit voneinander entfernt sind. Die Shell-Sortierung hilft dabei, den Abstand zwischen den geschlossenen Elementen zu verringern. Somit müssen weniger Swaps durchgeführt werden.

Interessante Beiträge...