การเขียนโปรแกรมภาษาซี/stdlib.h/qsort

qsort เป็น [function] ใน stdlib.h] ใช้ในการ [sort] ข้อมูลใน [array] ด้วย [algorithm] [Quicksort]
โดยเฉลี่ยจะใช้เวลา O]$(n \log n)$ และในกรณีเลวร้ายสุดจะใช้เวลา $ O(n^2) $ ด้วยโอกาสที่ต่ำมาก
footnoteqsort ของ compiler แต่ละตัวต่างกันออกไป อาจมีการใช้ขั้นตอนพิเศษทำให้ algorithm นี้ใช้เวลา $O(n \log n)$ เสมอ/footnote
สอวน. ค่าย 2 มีข้อสอบที่ต้อง sort ดังนั้น ควรฝึกใช้ qsort ให้เป็นเพื่อความรวดเร็วในการทำข้อสอบ
footnoteบางปีมีโจทย์ประมาณว่า จงเขียน bubble sort ซึ่งอาจารย์จะตรวจ source code ดังนั้นจึงไม่สามารถใช้ qsort ได้/footnote
อย่างไรก็ตาม ควรเขียน sort ทั้งหลายให้เป็นด้วย เช่น Quicksort , [Merge sort] , [Bubble sort] ฯลฯ
เนื่องจากแนวคิดของ sort เหล่านี้ อาจสามารถนำมาประยุกต์แก้ปัญหาต่างๆได้ เช่น ปัญหา inversion] , k-th selection] เป็นต้น
+ วิธีใช้ qsort
ต้องเรียกใช้ header file "stdlib.h"
code type="Cpp"
/code
qsort มี [parameter] ดังนี้
code type="Cpp"
qsort(A, n, s, cmpfunc);
/code
โดยหลังเรียกใช้ qsort แล้ว สมาชิกของ array ในช่วง [0,n) จะถูกเรียง
+ ตัวอย่างการใช้ qsort
code type="Cpp"
int cmpfunc(const void* a, const void* b){
 return (*(int*)a < *(int*)b) ? -1 : 1;
int A[] = {20,19,17,3,3,18,1,6,5,2,4,3,7};
int main{
 qsort(A, 6, sizeof(A[0]), cmpfunc);
 // A[0] .. A[5] is sorted
 return 0;
/code
+ parameter ตัวที่ 4 | function ใช้เปรียบเทียบ / cmpfunc
คือ function ที่เราต้องเขียนขึ้นมาเพื่อบอกให้ qsort รู้ว่า เราจะเรียงข้อมูลอย่างไร (เช่นเรียงจากน้อยไปมาก มากไปน้อย ฯลฯ)
สามารถเปลี่ยนเป็นชื่ออื่นได้ โดย function นี้จะต้องรับ Parameter เข้ามา 2 ตัว (ให้ชื่อว่า a และ b) และ [return] ออกไปเป็น int โดยมีกฎว่า
แต่ตามความเป็นจริงแล้ว เรา return เพียงค่า 1 และ -1 ก็พอแล้ว เพราะถ้า a กับ b สำคัญพอๆกัน อะไรจะมาก่อนมันก็ไม่สำคัญ !
อย่างไรก็ตาม a กับ b ที่ได้มานั้น ไม่สามารถนำไปใช้ได้ตรงๆ เพราะ qsort จะให้ a, b มาเป็น [address] ซึ่งเราก็ต้องใช้ [pointer] รับ address
แต่ยังไม่จบเพียงเท่านั้น เพราะ qsort ยังให้ address นี้มาในรูปของ void pointer] ซึ่งเป็นแบบ [constant] ด้วย ดังนั้น cmpfunc จึงมี [prototype] เป็น
ตัวอย่าง cmpfunc
code type="Cpp"
int cmpfunc(const void* a, const void* b){
 return (*(int*)a < *(int*)b) ? -1 : 1;
/code
a กับ b เป็น void pointer ไม่สามารถอ้างอิงข้อมูลโดยใช้ *] ได้โดยตรง ดังนั้นเราจึงต้องแปลง a, b เป็น pointer ชนิดอื่น เช่น
int pointer , double pointer , [struct] pointer (แล้วแต่ว่าเราประกาศ [datatype] ของ array เป็นอะไร)
แล้วค่อยใช้ * เพื่ออ้างอิงถึงข้อมูลข้างใน address ตามโค้ดข้างต้น ซึ่ง cmpfunc ดังกล่าวก็จะทำให้ qsort เรียงเลขจากน้อยไปมาก
หากต้องการเปลี่ยนเป็นเรียงจากมากไปน้อยก็อาจเปลี่ยนเป็น
code type="Cpp"
int cmpfunc(const void* a, const void* b){
 return (*(int*)a > *(int*)b) ? -1 : 1;
/code
 # warning ข้อควรระว.
เนื่องจากมีโอกาสสูงที่หากจำนวนจริงถูกแปลงเป็น int แล้วจะถูกปัดจนค่าผิดพลาด (เช่นจากติดลบเป็น 0)
(ดูหัวข้อ [#sample-error ข้อผิดพลาดจาก cmpfunc] สำหรับตัวอย่างที่ทำให้เกิดความผิดพลาด)**
 ทำไมต้องทำให้ยุ่งยากขนาดน.
--หัวข้อนี้ผมเขียนเอาตามความเข้าใจผมนะ (เดาใจคนออกแบบ qsort) เพราะฉะนั้นไม่รับประกันว่ามันจะเป็นแบบนี้จริงหรือเปล่า
หากเรารับข้อมูลเข้ามาเป็นข้อมูลตรงๆเลย จะเสียเวลาในการ [pass by value] โดยเฉพาะการเรียง struct ซึ่งใน struct มีสมาชิกมากๆ
ดังนั้น คนออกแบบจึงออกแบบให้ส่ง address มาแทน แต่ทีนี้ก็เกิดปัญหาขึ้นอีก ถ้าจะส่งมาเป็น address
จะส่งมาในรูปของ pointer ของอะไร เพราะอย่าลืมว่า qsort ต้องรองรับการ sort array ทุกๆ datatype
ไม่ใช่เฉพาะ int อย่างเดียว ดังนั้นเขาจึงออกแบบให้ส่งมาเป็น void pointer แล้วพอจะใช้งานจริงค่อยเอาไปแปลงกันเอาเอง
ปัญหาสุดท้ายคือเมื่อส่งมาเป็น address ก็อาจจะทำให้เราเข้าไปแก้ข้อมูลได้ ซึ่งตามความจริงแล้ว cmpfunc ไม่ควรทำได้
เขาเลยป้องกันโดยบังคับให้เป็น constant ซึ่งถ้าเราไป assign ค่าอะไรลงไปก็จะเกิด compilation error]--
chalet16 บอกว่าเพราะสมัยนั้นไม่มี C++ จึงไม่สามารถทำ overloading function] และ [pass by reference] ได้ เลยต้องส่งเป็น address มาแทน
 ตัวอย่าง cmpfunc ที่ใช้ในการ sort stru.
ให้ struct ST มี สมาชิก p และ q โดยเราจะทำการเรียงตาม p ก่อน และถ้า p เท่ากันค่อยเรียงตาม q
code type="Cpp"
int cmpfunc(const void* a, const void* b){
 ST *aa,*bb;
 aa = (ST*)a;
 bb = (ST*)b;
 if(aa->p == bb->p)
 return (aa->q < bb->q) ? -1 : 1;
 return (aa->p < bb->p) ? -1 : 1;
/code
 # sample-error ข้อผิดพลาดจาก cmpfu.
ส่วนมากมักเกิดจากการเขียน cmpfunc เช่นนี้
code type="Cpp"
int cmpfunc(const void* a, const void* b){
 return *(int*)a - *(int*)b;
/code
สำหรับคนที่ไม่รู้ว่า cmpfunc นี้เอาไว้ทำอะไร นี่คือ cmpfunc ที่เอาไว้เรียงเลขจากน้อยไปมาก !
จะเห็นได้ว่าโค้ดนี้สั้นมากและเป็นที่นิยมใช้ อย่างไรก็ตาม วิธีนี้อาจทำให้เกิดปัญหาตามหัวข้อ [#warning ข้อควรระวัง]
เมื่อใช้ในการเรียง array ของ datatype จำนวนจริง เช่น float หรือ datatype ที่พิสัยเกิน int เช่น long long
code type="Cpp"
int cmpfunc(const void *a , const void *b){
 return *(double*)a - *(double*)b;
double arr[] = {12.2,12.1};
int main{
 printf("before sort\n");
 printf("%lf %lf\n", arr[0], arr[1]); // 12.2 12.1
 qsort(arr, 2, sizeof(arr[0]), cmpfunc);
 printf("after sort\n");
 printf("%lf %lf\n", arr[0], arr[1]); // 12.2 12.1
 return 0;
/code
ปัญหาเกิดจากเมื่อนำ 12.2 - 12.1 = 0.1 แต่เมื่อโดนบังคับให้ return เป็น int จึงทำให้จาก 0.1 โดน implicit conversion] กลายเป็น 0
เลยโดนตีความว่า 12.2 = 12.1 ทำให้การ sort ผิดพลาด
code type="Cpp"
int cmpfunc(const void *a , const void *b){
 return *(int*)a - *(int*)b;
int arr[] = {2147483647,-1};
int main{
 printf("before sort\n");
 printf("%d %d\n", arr[0], arr[1]); // 2147483647 -1
 qsort(arr, 2, sizeof(arr[0]), cmpfunc);
 printf("after sort\n");
 printf("%d %d\n", arr[0], arr[1]); // 2147483647 -1
 return 0;
/code
ปัญหาเกิดจากเมื่อนำ 2147483647 - (-1) = 2147483648 แต่ 2147483648 เกินพิสัยของ int
จึงกลายเป็นค่าติดลบ (-2147483648 ตาม 2's Complement]) เลยโดนตีความว่า 2147483647 มาก่อน -1 ทำให้การ sort ผิดพลาด
ปัญหาที่เกิดจาก long long ก็จะคล้ายๆกับตัวอย่างนี้ คือพิสัยเกิน int เพราะฉะนั้นขอไม่กล่าวถึง
วิธีแก้ปัญหานี้ก็ง่ายๆ คือ หาวิธีอื่นมาใช้แทน เช่นตัวอย่างทั้งหลายที่เขียนไว้ในหัวข้อต่างๆ (ยกเว้นหัวข้อนี้ เพราะหัวข้อนี้มีแต่ตัวอย่างที่มีปัญหา)
+ parameter ตัวที่ 3 | ขนาดสมาชิกหนึ่งช่อง
ขนาดสมาชิกหนึ่งช่องของ array นั้น (หน่วย byte) อาจระบุเป็นตัวเลขเช่น 4 (ใช้กับ array ของ int , float , ฯลฯ)
หรืออาจใช้ [sizeof] มาเป็นตัวหาขนาดให้ เช่น sizeof(int) หรือ sizeof(A[0])
แต่แนะนำให้ใช้ sizeof(A[0]) เพราะมันแน่นอนอยู่แล้วว่า array A จะมีขนาดของช่องเป็น sizeof(A[0])
+ parameter ตัวที่ 1 และ 2 | array ที่จะ sort และ จำนวนข้อมูลที่จะเรียง
ตามความจริงแล้ว parameter ตัวแรกคือ address ของ array ช่องแรกที่จะทำการเรียง
อย่าลืมว่า ชื่อ array ที่ไม่ระบุช่อง] มีความหมายคือ address ของ array ช่องแรก => เรียงตั้งแต่ A[0]
ดังนั้นถ้าเราต้องการเรียงจาก array ในช่วง [1,n] ก็อาจเขียนโค้ดดังนี้
code type="Cpp"
qsort(A + 1, n, sizeof(A[0]), cmpfunc);
/code
หรือ
code type="Cpp"
qsort(&A[1], n, sizeof(A[0]), cmpfunc);
/code
ถ้าต้องการเรียงจาก array ในช่วง [a,b] ก็อาจเขียนโค้ดดังนี้
code type="Cpp"
qsort(A + a, b - a + 1, sizeof(A[0]), cmpfunc);
/code
หรือ
code type="Cpp"
qsort(&A[a], b - a + 1, sizeof(A[0]), cmpfunc);
/code