временная сложность в сортировке оболочки

Question

Почему временная сложность меньше при сортировке оболочки по сравнению с сортировкой и сортировкой пузырьков? Как мы можем рассчитать сложность времени, я имею в виду, на каком основании мы считаем, что наш код отличается высокой или низкой степенью сложности?

#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

Что касается вашего вопроса на каком основании мы считаем, что наш код высокий или низкий временная сложность простая вещь, чтобы рассмотреть для сортировки алгоритм с N элементами, как много сравнений сделаны, чтобы сделать массив элементов, отсортированных. Сравнение также приводит к замене элементов, что приводит к большему количеству ресурсов, используемых в системе (ЦП).

Bubble/insertion sort может завершиться с помощью сравнений n^2 (можно оптимизировать, если никаких свопов не производится, а затем не сканировать снова для уже отсортированных массивов). Сорт Shell был усовершенствован, чтобы в некоторых сценариях лучше, чем n^2. Указатели по википедии являются хорошей ссылкой, но предложили бы прочитать книгу об алгоритмах, специально занимающихся сортировкой, чтобы получить большую ясность (Структуры данных и анализ алгоритмов - Марк Аллен Вайс или некоторые другие)