Исправление alysnix, (текущая версия) :
берутся два индекса.
h0(индекс первой дырки) = 0, h1(индекс последней)=длина массива дырок-1; и индекс последнего элемента массива данных = i.
проверяется валидность i. i валиден если он указывает не на последнюю дырку(она с индексом h1). если указывает на последнюю - делаем –h1; –i. то есть данная дырка не может быть ничем заполнена(поскольку дырку можно заполнить только справа, а справа элементов нет), делаем это в цикле, пока последняя дырка не окажется слева от текущего i. тут мы нашли самый правый непустой элемент переставляемго массива. если h0 <= h1, то есть массив дырок не сошелся в ноль, мы переставляем этот элемент данных с индексом i на позицию holes[h0] и инкрементруем h0.
то есть data[holes[h0++]]=data[i–];
поскольку тут декрементировали i, проверяем holes[h1]<i. если тру - элемент можно переставить и он не дырка. если дырка - смотрите алгоритм выше. как только h0>h1 - дырки кончились, выходим.
то есть принцип простой. любой самый правый элемент данных индекс которого больше индекса самой последней дырки - не на своем месте и должен быть переставлен. если у дырки нет элементов справа - ее заполнить нечем, она отбрасывается. и последней дыркой считается предыдущая.
разумеется дырки изначально отсортированы массиве дырок
Исправление alysnix, :
берутся два индекса.
h0(индекс первой дырки) = 0, h1(индекс последней)=длина массива дырок-1; и индекс последнего элемента массива данных = i.
проверяется валидность i. i валиден если он указывает не на последнюю дырку(она с индексом h1). если указывает на последнюю - делаем –h1; –i. то есть данная дырка не может быть ничем заполнена(поскольку дырку можно заполнить только справа, а справа элементов нет), делаем это в цикле, пока последняя дырка не окажется слева от текущего i. тут мы нашли самый правый непустой элемент переставляемго массива. если h0 <= h1, то есть массив дырок не сошелся в ноль, мы переставляем этот элемент данных с индексом i на позицию holes[h0] и инкрементруем h0.
то есть data[holes[h0++]]=data[i–];
поскольку тут декрементировали i, проверяем holes[h1]<i. если тру - элемент можно переставить и он не дырка. если дырка - смотрите алгоритм выше. как только h0>h1 - дырки кончились, выходим.
то есть принцип простой. любой самый правый элемент данных индекс которого больше индекса самой последней дырки - не на своем месте и должен быть переставлен. если у дырки нет элементов справа - ее заполнить нечем, она отбрасывается. и последней дыркой считается предыдущая.
Исходная версия alysnix, :
берутся два индекса.
h0(индекс первой дырки) = 0, h1(индекс последней)=длина массива дырок-1; и индекс последнего элемента = i.
проверяется валидность i. i валиден если он указывает не на последнюю дырку(она с индексом h1). если указывает на последнюю - делаем –h1; –i. то есть данная дырка не может быть ничем заполнена(поскольку дырку можно заполнить только справа, а справа элементов нет), делаем это в цикле, пока последняя дырка не окажется слева от текущего i. тут мы нашли самый правый непустой элемент переставляемго массива. если h0 <= h1, то есть массив дырок не сошелся в ноль, мы переставляем этот элемент данных с индексом i на позицию holes[h0] и инкрементруем h0.
то есть data[holes[h0++]]=data[i–];
поскольку тут декрементировали i, проверяем holes[h1]<i. если тру - элемент можно переставить и он не дырка. если дырка - смотрите алгоритм выше. как только h0>h1 - дырки кончились, выходим.
то есть принцип простой. любой самый правый элемент данных индекс которого больше индекса самой последней дырки - не на своем месте и должен быть переставлен. если у дырки нет элементов справа - ее заполнить нечем, она отбрасывается. и последней дыркой считается предыдущая.