Re: [問題] 資結-bubble程式
※ 引述《icrts (居天下之廣居)》之銘言：
: ※ 引述《bernachom (Terry)》之銘言：
: : 我程式很差...想問一些東西
: 手癢還是回一篇好了.
: 這類的問題，建議你先了解這個演算法是在做些什麼
: 然後再去看code，把code對應到程式碼，會比較好懂
: : Void bubble_sort(int list[],int n) #這是在說list[]有n個格子嗎?
: 首先這邊的宣告讓我覺得有點詭異， int list[] 傳的是整數，
: 但是依據我對程式的了解，這邊應該是要傳array的位址，該改為
: int *list。(但不是很確定，有望##確認) //如果是pseudo code就別管它
int* a
在參數上可以等於int a[]
只有在二維才有一點點差別
: 再來，int n所表示的是每次call這個function同時會傳一個參數
: 給這個function。在這裡依照bubble sort演算法來說傳遞的是list的
: 格子數沒錯，但其實表示的應該是要sort的數為前面n個。
: : {
: : int tag,i,j;
: : for(i=1;i<n;i++)#i小於array格子就往右移?
: 這邊應該說的是，這個找最大值的行為總共做了幾次。
如果單單翻譯程式碼的話
for( i=1; i<n; i++)
i初始為1
在接下來的指令部分會在 i<n的條件下執行
i++是在下一倫才開始作。
: : {
: : tag=0;
: : for(j=1;j<n-i;j++)#這行不太清楚..j<剩下的格子數?
j初始為1
下面的程式碼在j< n-i 下完成
同上個人說法，最大值會跑到最後面，所以內層其實不需要繼續往先前已經排過的
數字找了，因為在序列中不可能找到比排過的最大值還大的數。
所以可以直接把排過的部分省略掉。
: 在bubble sort演算法中，上一個for迴圈表示的i是做了第幾次
: 而每做一次最大的那個值就會跑到最後面
: 所以要比較出最大的值，就從第一個開始往後找
: : {
: : if list[j]>list[j+1]#為什麼j會>j+1 ???
j > j+1 跟
list[ j ] > list[ j+1 ]不同
下面是取得list的第j個以及第j+1個
: 在此如果有找到前面的值比後面的大的話
: 就將兩數交換位置
: : {
: : swap(list[j],list[j+1]);
: : tag=1;
: : }
: : }
: 做完一次for(j=..)之迴圈一次可以確保最大值在最後方
: : if tag==0 break;
tag被設為1的情形只有在找到list[ j ] > list[ j+1 ]的狀態。
所以當tag保持0的時候，表示整個陣列都是遞增/遞減狀態。
void bubble_sort( int list[], int n ){
int findGreater, i, j;
for( i = 0; i < n; i++ ) { /* i為[0 ... n-1] */
findGreater = 0; /* 令findGreater為0 */
for( j = 0; j < n-i; j++ ) {
if( list[ j ] > list[ j+1 ] ) { /* 如果第j個 > j+1個 */
swap( list[ j ], list[ j+1 ] ); /* 交換 */
findGreater = 1; /* 標記有出現較大的部分 */
}
}
if( !findGreater ) { /* 如果整個陣列是遞增狀態則不需排序 */
break;
}
}
}
原po所打的算是pseudo code，因為c語言的陣列不是以1為底的，
但題目沒有說他是c語言，如果是一個simulation language如slx
或者matlab，陣列的確是以1為底。
另外假使是c語言 if 敘述後面要有括號的，所以他不是c語言。
且if tag=1，equal跟assign會混淆的，如果有個程式寫著
if( a = 0 ){
say("you approach Unreachable code ... wtf ?");
}
這如果在考試的時候，評分成了很大的問題吧。
說不定寫了兩種答案的人還會被改考卷的扣分。(今年我想要當作他是assign)
(明年我決定當他是equal)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.123.187
推
04/30 05:34, , 1F
04/30 05:34, 1F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：
問題
1
3