Zeit Komplexität in Shell-Sortierung

Question

Warum Zeit Komplexität ist weniger in Shell-Sortierung im Vergleich zu Bubble-Sortierung und Insertion Sortierung? Wie können wir die Zeitkomplexität berechnen? Ich meine, auf welcher Basis betrachten wir unseren Code als hoch oder niedrig?

#include <stdio.h> 
void shellsort(int arr[], int num) 
{ 
    int i, j, k, tmp; 
    for (i = num/2; i > 0; i = i/2) 
    { 
     for (j = i; j < num; j++) 
     { 
      for (k = j - i; k >= 0; k = k - i) 
      { 
       if (arr[k + i] >= arr[k]) 
        break; 
       else 
       { 
        tmp = arr[k]; 
        arr[k] = arr[k + i]; 
        arr[k + i] = tmp; 
       } 
      } 
     } 
    } 
} 
int main() 
{ 
    int arr[30]; 
    int k, num; 
    printf("Enter total no. of elements : "); 
    scanf("%d", &num); 
    printf("\nEnter %d numbers: ", num); 
    for (k = 0; k < num; k++) 
    { 
     scanf("%d", &arr[k]); 
    } 
    shellsort(arr, num); 
    printf("\n Sorted array is: "); 
    for (k = 0; k < num; k++) 
     printf("%d ", arr[k]); 
    return 0; 
} 

Answer 1

In Bezug auf Ihre Frage , auf welcher Grundlage betrachten wir unseren Code hohe oder niedrige Zeitkomplexität für Sortieralgorithmus mit N Elementen eine einfache Sache zu prüfen ist, wie viele Vergleiche die Anordnung von Elementen sortierten machen gemacht werden. Die Vergleiche führen weiterhin zum Austausch von Elementen, was zu mehr Ressourcen auf dem System (CPU) führt.

Bubble/Insertion sort kann mit n^2 Vergleichen enden (kann optimiert werden, wenn keine Swaps gemacht werden, dann nicht erneut nach bereits sortierten Arrays scannen). Shell-Sortierung wurde verfeinert, um in bestimmten Szenarien besser als n^2 zu sein. Die Wikipedia-Zeiger sind eine gute Referenz, würden aber vorschlagen, ein Buch über Algorithmen zu lesen, die sich speziell mit dem Sortieren befassen, um mehr Klarheit zu erhalten (Datenstrukturen und Algorithmusanalyse - Mark Allen Weiss oder andere)