การเขียนโปรแกรมภาษาซี/stdlib.h/qsort
qsort เป็น [[[function]]] ใน [[[stdlib|stdlib.h]]] ใช้ในการ [[[sort]]] ข้อมูลใน [[[array]]] ด้วย [[[algorithm]]] [[[Quicksort]]] โดยเฉลี่ยจะใช้เวลา [[[big oh|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 ([[[stl-sort|sort]]] ของ [[[STL]]] ไม่สามารถใช้ได้เพราะอาจารย์ไม่อนุญาต)
อย่างไรก็ตาม ควรเขียน sort ทั้งหลายให้เป็นด้วย เช่น Quicksort , [[[Merge sort]]] , [[[Bubble sort]]] ฯลฯ เนื่องจากแนวคิดของ sort เหล่านี้ อาจสามารถนำมาประยุกต์แก้ปัญหาต่างๆได้ เช่น ปัญหา [[[inversion|inversion]]] , [[[k-th-selection|k-th selection]]] เป็นต้น
+ วิธีใช้ qsort
ต้องเรียกใช้ header file "stdlib.h"
- include <stdlib.h>
qsort มี [[[parameter]]] ดังนี้
code type="Cpp" qsort(A, n, s, cmpfunc); /code
- **A คือ array ที่จะ sort**
- **n คือจำนวนข้อมูลที่จะเรียง**
- **s คือขนาดของข้อมูลหนึ่งช่อง**
- **cmpfunc คือ function ใช้เปรียบเทียบ**
โดยหลังเรียกใช้ qsort แล้ว สมาชิกของ array ในช่วง [0,n) จะถูกเรียง
+ ตัวอย่างการใช้ qsort
- include <stdlib.h>
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 => {3,3,17,18,19,20,1,6,5,2,4,3,7}
// A[0] .. A[5] is sorted
return 0;
} /code
+ parameter ตัวที่ 4 | function ใช้เปรียบเทียบ / cmpfunc คือ function ที่เราต้องเขียนขึ้นมาเพื่อบอกให้ qsort รู้ว่า เราจะเรียงข้อมูลอย่างไร (เช่นเรียงจากน้อยไปมาก มากไปน้อย ฯลฯ) สามารถเปลี่ยนเป็นชื่ออื่นได้ โดย function นี้จะต้องรับ Parameter เข้ามา 2 ตัว (ให้ชื่อว่า a และ b) และ [[[return]]] ออกไปเป็น int โดยมีกฎว่า
- **ถ้าอยากให้ a มาก่อน b ให้ return ค่าติดลบ (เช่น -1)**
- **ถ้าอยากให้ b มาก่อน a ให้ return ค่าเป็นบวก (เช่น 1)**
- **ถ้า a และ b มีความสำคัญพอๆกัน ให้ return ค่า 0**
แต่ตามความเป็นจริงแล้ว เรา return เพียงค่า 1 และ -1 ก็พอแล้ว เพราะถ้า a กับ b สำคัญพอๆกัน อะไรจะมาก่อนมันก็ไม่สำคัญ ! (ยังไง qsort ก็ไม่ได้เป็น [[[stablesort|stable sort]]] อยู่แล้ว)
อย่างไรก็ตาม a กับ b ที่ได้มานั้น ไม่สามารถนำไปใช้ได้ตรงๆ เพราะ qsort จะให้ a, b มาเป็น [[[address]]] ซึ่งเราก็ต้องใช้ [[[pointer]]] รับ address แต่ยังไม่จบเพียงเท่านั้น เพราะ qsort ยังให้ address นี้มาในรูปของ [[[pointer#void|void pointer]]] ซึ่งเป็นแบบ [[[constant]]] ด้วย ดังนั้น cmpfunc จึงมี [[[prototype]]] เป็น
- int cmpfunc(const void*,const void*);**
ตัวอย่าง cmpfunc
code type="Cpp" int cmpfunc(const void* a, const void* b){
return (*(int*)a < *(int*)b) ? -1 : 1;
} /code
a กับ b เป็น void pointer ไม่สามารถอ้างอิงข้อมูลโดยใช้ [[[pointer#dereference|*]]] ได้โดยตรง ดังนั้นเราจึงต้องแปลง 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 ข้อควรระวัง
- ค่าที่ return ออกมาจาก cmpfunc นี้จะต้องเป็น int เท่านั้น ดังนั้นควรหลีกเลี่ยงการ return จำนวนจริงออกมา
เนื่องจากมีโอกาสสูงที่หากจำนวนจริงถูกแปลงเป็น 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 ค่าอะไรลงไปก็จะเกิด [[[compile-error|compilation error]]]--
chalet16 บอกว่าเพราะสมัยนั้นไม่มี C++ จึงไม่สามารถทำ [[[overloading-function|overloading function]]] และ [[[pass by reference]]] ได้ เลยต้องส่งเป็น address มาแทน
++ ตัวอย่าง cmpfunc ที่ใช้ในการ sort struct ให้ 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 ข้อผิดพลาดจาก cmpfunc ส่วนมากมักเกิดจากการเขียน cmpfunc เช่นนี้
code type="Cpp" int cmpfunc(const void* a, const void* b){
return *(int*)a - *(int*)b;
} /code
สำหรับคนที่ไม่รู้ว่า cmpfunc นี้เอาไว้ทำอะไร นี่คือ cmpfunc ที่เอาไว้เรียงเลขจากน้อยไปมาก !
- *(int*)a ก็คือค่า a ที่เป็นเลข
- *(int*)b ก็คือค่า b ที่เป็นเลข
- ถ้า a < b จะได้ว่า a - b < 0 ซึ่งเป็นค่าลบ ดังนั้น a มาก่อน b
- ถ้า a = b จะได้ว่า a - b = 0 ซึ่งเป็นค่าลบ ดังนั้น a , b สำคัญพอกัน
- ถ้า a > b จะได้ว่า a - b > 0 ซึ่งเป็นค่าลบ ดังนั้น b มาก่อน a
จะเห็นได้ว่าโค้ดนี้สั้นมากและเป็นที่นิยมใช้ อย่างไรก็ตาม วิธีนี้อาจทำให้เกิดปัญหาตามหัวข้อ [#warning ข้อควรระวัง] เมื่อใช้ในการเรียง array ของ datatype จำนวนจริง เช่น float หรือ datatype ที่พิสัยเกิน int เช่น long long
- และถ้าจะให้พูดกันตามตรงแล้ว แม้แต่เรียง int ยังมีโอกาสผิดพลาดเลย !**
- include <stdio.h>
- include <stdlib.h>
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|implicit conversion]]] กลายเป็น 0 เลยโดนตีความว่า 12.2 = 12.1 ทำให้การ sort ผิดพลาด
- include <stdio.h>
- include <stdlib.h>
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 ตาม [[[twos-complement|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 ที่ไม่ระบุช่อง]]] มีความหมายคือ 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