[問題] gnome sort

[OPIV (稻草人)]

以下是我對 gnome sort 的實作
和網路上找得到的範例都幾乎相同

但是遇到某些輸入時，它就會變成一個無法結束的演算法
當傳入的 array length > 100的時候就很容易遇到，數字用亂數給 (rand() % 10000)
但是如果長度在60以下卻又從來沒發生過這問題

用 xcode 來 debug 會發現這些輸入都會讓 i 一直在一個區間裡來來回回，但是陣列內
容卻沒有改變

有試過直接複製別人的算法，一樣也都有這個問題
很好奇這麼久了都沒人發現嗎？

template <typename T>
void gnome_sort(T* array, size_t length)
{
        for(size_t i = 0; i < length; )
        {
                if((i == 0) || (array[i] > array[i - 1]))
                        i++;
                else
                {
                        T tmp = array[i - 1];
                        array[i - 1] = array[i];
                        array[i] = tmp;
                        i--;
                }
        }
}

主程式

int main(void)
{
        int* array = (int*)malloc(sizeof(int) * 100);

        srand(time(NULL));

        for(size_t i = 0; i < 100; i++)
                array[i] = rand() % 10000;

        gnome_sort<int>(array, 100);

        for(size_t i = 0; i < 100; i++)
                std::cout << array[i] << " ";
        std::cout << std::endl;

        free(array);

        return 0;
}

感謝各位～

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.98.20
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1447218242.A.125.html
推 ZanFu5566: 應該要>= 就i++吧?
→ ZanFu5566: 這樣愈到兩個一樣的連續數值會無窮迴圈
真的是這個問題
真的太北七了抱歉XDD…
※ 編輯: OPIV (49.218.98.20), 11/11/2015 14:42:40