[問題] gnome sort
以下是我對 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
推
11/11 13:23, , 1F
11/11 13:23, 1F
→
11/11 13:23, , 2F
11/11 13:23, 2F
真的是這個問題
真的太北七了抱歉XDD…
※ 編輯: OPIV (49.218.98.20), 11/11/2015 14:42:40
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
