作者TommyKSHS (湯米)
看板b98902HW
標題Re: [計程] qsort()
時間Wed Oct 28 14:28:21 2009
你這個有點 bug...
int cmp(const void* A,const void* B ){
int* A = (int*) a;//將原本為void*的a
轉型為int*並指定給A
int* B = (int*) b;
if( *A < *B ) return -1; //若*A比*B小，代表A的順位比較前面
else if( *A == *B ) return 0;
else return 1;
return 0;
}
我覺得應該是 int cmp(const void
*a,const void
*b)
補充一下， -1 0 1 代表的是 負 零 正
也就是說整個 cmp 可以寫成
int cmp(const void *a,const void *b)
{
return *(int*)b-*(int*)a;
}
不過，…這個寫法雖然比較簡捷，可是要小心可能某些 TA 會出陰險的 testdata
然後 *(int*)b-*(int*)a 就會 overflow... 到時候就 WA 到天荒地老了
--
╭═══╤═══╮ ╰═╮ ╭═╯
│ │ │╭═和平，土地，麵包═╮ │ │
│ ╭═╧╧╮╤═╤═╮═╤═╤╧╮ │ │
│ │ ││ │ │ │ │ │ ╰═╤═╯
│ │ ││ │ │ │ │ │ │
╰╧╯╰═══╯╰ ╰ ╰ ╰ ╰ ╰ ─╯
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.239.191
1F：→ silentvow:應該是 *(int*)b-*(int*)a 吧？ 10/28 14:35
2F：推 hallogameboy:噢對耶，感謝Tommy~ 10/28 14:41
3F：→ hallogameboy:恩因為怕overflow所以建議自己判斷之後再輸出~ 10/28 14:42
4F：→ mimi9126:其實在這堂課不太需要考慮這種oveflow的問題，因為那"還" 10/28 15:07
5F：→ mimi9126:不是這些題目的重點，相對的我反而希望你們能注意看每個 10/28 15:07
6F：→ mimi9126:題目給的範圍，很多時候從範圍就可以知道大概會有啥問題 10/28 15:08
7F：→ mimi9126:不過本篇這種寫法的確是比較好的 10/28 15:09
8F：推 YAOMMENT:為什麼不是*(int*)a-*(int*)b阿 10/28 15:13
9F：→ mimi9126:看要ascending還是decending 10/28 15:49
10F：→ TommyKSHS:阿 一樓說的對 10/28 16:10
11F：→ TommyKSHS:我改一下 10/28 16:10
※ 編輯: TommyKSHS 來自: 140.112.239.191 (10/28 16:11)
※ 編輯: TommyKSHS 來自: 140.112.239.191 (10/28 16:14)
12F：推 sa072686:這個很常見…所以講qsort()有必要提一下overflow 10/28 18:22
13F：→ sa072686:不然哪天被陰了可能都不知道XD 10/28 18:23
14F：推 anfranion:範圍很重要啊~ 也還是要考慮overflow的~ 10/28 20:53
15F：→ anfranion:不然就不會有何木木問題了~ 10/28 20:53
16F：→ zenixls2:我有個東西想問，好像只回傳0和1其實不影響正確性?! 10/28 23:47
17F：→ zenixls2:因為像sort的回傳也只是0和1...那個-1好像沒必要?? 10/28 23:47
18F：推 davll:對標準C函式庫而言,compare是代表差值的正負或零(ex:strcmp) 10/28 23:52
19F：→ zenixls2:不過我想應該是因為沒太大意義才會在C++改成二分 10/29 01:09
20F：推 davll:嗯，因為已經有分stable_sort與sort了，cmp就變成< or >了 10/29 19:07