Почему мой алгоритм сортировки быстрее, чем в книге «Введение в алгоритмы» в книге Х. Кормена?

Question

Я изучаю эту книгу со вчерашнего дня, и после того, как я понял и применил первый алгоритм, я попытался пойти самостоятельно и посмотреть по-другому. Вот, в Java, показанный алгоритм:

public static int[] sort(int[] array) 
{ 
    for(int i = 1; i < array.length; i++){ 
     int value = array[i]; 
     int j = i - 1; 

     while(j >= 0 && array[j] > value){ 
      array[j + 1] = array[j]; 
      j--; 
     } 
     array[j+1] = value; 
    } 

    return array; 
} 

А вот мой:

public static int[] sortb(int[] array) 
{ 
    for(int i = 0; i < array.length; i++){ 
     int value = array[i]; 
     int j = i; 

     while(j < array.length && value > array[j]){ 
      array[j] = array[j + 1]; 
      j++; 
     } 

     array[j] = value; 
    } 

    return array; 
} 

1 млн вызова функции для каждого, я получил 32 мс для первого и 25 мс для второго , Я все еще начинаю с алгоритмов, поэтому я понятия не имею о значении.

Answer 1

Я нашел, почему ваш вид намного быстрее оригинального: потому что вы вообще не занимаетесь.

В коде

int value = array[i]; 
    int j = i; 

    while(j < array.length && value > array[j]) { ... } 

Поскольку j = i, так value == array[j], прежде чем попасть в петлю в то время, и, таким образом, ваше тело цикла в то время как никогда не выполняться. Результат сортировки будет неправильным. Это основная причина, по которой ваш код работает очень быстро.

Answer 2

В моем опыте (см. опыт ученика), этот вид разных значений имеет мало смысла.

Возможно, у вас был фоновый процесс, который взял/выпустил немного больше ресурсов из одного в другой.

Возможно, конкретный случай, который вы пытались организовать, был лучше для одного из алгоритмов, чем другой.

Может быть, если вы использовали различные случайные массивы, один из них был ближе к сортироваться, чем другие ..

Чтобы иметь хорошие меры, как правило, вы должны сделать много испытаний, а не только один. Так, например, генерирует 1k 10k массивы элементов, каждые и сортировка каждый из этого массива с обеими алгоритмами ..

В любом случае, иногда специфическими особенностями языка или компилятор может генерировать разные результаты для алгоритмов с теоретически точно такими же сложностями (один пример: как только я заметил в C++, если вы пересекаете двумерный массив сначала по столбцам, а затем по строкам, у вас будет совсем другая скорость, чем если бы вы сделали это наоборот, но я не помню, какой из них был быстрее tbh).