Попытка понять сортировку оболочки

Question

Я пытаюсь понять сортировку оболочки, которую я нашел в Интернете. Это код:

for(increment = size/2;increment > 0; increment /= 2) 
{ 
    for(i = increment; i<size; i++) 
    { 
     temp = array[i]; 
     for(j = i; j >= increment ;j-=increment) 
     { 
      //perform the insertion sort for this section 
      if(temp < array[j-increment]) 
      { 
       array[j] = array[j-increment]; 
      } 
      else 
      { 
       break; 
      } 
     } 
     array[j] = temp; 
    } 
} 

Я понимаю, что первый цикл держит деления количества элементов в массиве 2, пока не доберется до 1. Но я не очень понимаю, остальную часть кода.

Answer 1

Сначала прочитайте на insertion sort.

Самый внутренний цикл выполняет часть сортировки вставки, вставляя элемент в (предположительно) отсортированный подрамник «влево» исходной точки, но учитывая только элементы, кратные interval. Второй цикл (for(i=...) выполняет вторую половину сортировки вставки, продвигаясь по массиву; когда этот цикл закончен, весь массив сортируется, но только в том смысле, что нет элементов, находящихся вне порядка, разделенных кратным interval. То есть, нет i и k таких, что array [i]> array [i + k * interval].

Исключительная петля повторяется через меньшие и меньшие интервалы, пока не станет «полной» вставкой всего массива.

Я полагаю, что идея начать с больших интервалов - ускорить весь вид, позволяя элементам, которые являются очень большими или очень маленькими, чтобы «перескакивать» большие участки массива, а не ползать через каждую позицию; как хорошо это работает, не сразу становится очевидным ...