qsort

บทความนี้แก้เพิ่มจาก wiki ของ chalet16 ขอขอบคุณมา ณ ที่นี้ด้วย [1]

qsort เป็น function ใน stdlib.h ใช้ในการ sort ข้อมูลใน array ด้วย algorithm Quicksort
โดยเฉลี่ยจะใช้เวลา O$(n \log n)$ และในกรณีเลวร้ายสุดจะใช้เวลา $O(n^2)$ ด้วยโอกาสที่ต่ำมาก1

สอวน. ค่าย 2 มีข้อสอบที่ต้อง sort ดังนั้น ควรฝึกใช้ qsort ให้เป็นเพื่อความรวดเร็วในการทำข้อสอบ2
(sort ของ STL ไม่สามารถใช้ได้เพราะอาจารย์ไม่อนุญาต)

อย่างไรก็ตาม ควรเขียน sort ทั้งหลายให้เป็นด้วย เช่น Quicksort , Merge sort , Bubble sort ฯลฯ
เนื่องจากแนวคิดของ sort เหล่านี้ อาจสามารถนำมาประยุกต์แก้ปัญหาต่างๆได้ เช่น ปัญหา inversion , k-th selection เป็นต้น

วิธีใช้ qsort

ต้องเรียกใช้ header file "stdlib.h"

#include <stdlib.h>

qsort มี parameter ดังนี้

qsort(A, n, s, cmpfunc);
  • 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;
}

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 ก็ไม่ได้เป็น stable sort อยู่แล้ว)

อย่างไรก็ตาม a กับ b ที่ได้มานั้น ไม่สามารถนำไปใช้ได้ตรงๆ เพราะ qsort จะให้ a, b มาเป็น address ซึ่งเราก็ต้องใช้ pointer รับ address
แต่ยังไม่จบเพียงเท่านั้น เพราะ qsort ยังให้ address นี้มาในรูปของ void pointer ซึ่งเป็นแบบ constant ด้วย ดังนั้น cmpfunc จึงมี prototype เป็น

int cmpfunc(const void*,const void*);

ตัวอย่าง cmpfunc

int cmpfunc(const void* a, const void* b){
    return (*(int*)a < *(int*)b) ? -1 : 1;
}

a กับ b เป็น void pointer ไม่สามารถอ้างอิงข้อมูลโดยใช้ * ได้โดยตรง ดังนั้นเราจึงต้องแปลง a, b เป็น pointer ชนิดอื่น เช่น
int pointer , double pointer , struct pointer (แล้วแต่ว่าเราประกาศ datatype ของ array เป็นอะไร)
แล้วค่อยใช้ * เพื่ออ้างอิงถึงข้อมูลข้างใน address ตามโค้ดข้างต้น ซึ่ง cmpfunc ดังกล่าวก็จะทำให้ qsort เรียงเลขจากน้อยไปมาก

หากต้องการเปลี่ยนเป็นเรียงจากมากไปน้อยก็อาจเปลี่ยนเป็น

int cmpfunc(const void* a, const void* b){
    return (*(int*)a > *(int*)b) ? -1 : 1;
}

ข้อควรระวัง

ค่าที่ return ออกมาจาก cmpfunc นี้จะต้องเป็น int เท่านั้น ดังนั้นควรหลีกเลี่ยงการ return จำนวนจริงออกมา
เนื่องจากมีโอกาสสูงที่หากจำนวนจริงถูกแปลงเป็น int แล้วจะถูกปัดจนค่าผิดพลาด (เช่นจากติดลบเป็น 0)
(ดูหัวข้อ ข้อผิดพลาดจาก 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 struct

ให้ struct ST มี สมาชิก p และ q โดยเราจะทำการเรียงตาม p ก่อน และถ้า p เท่ากันค่อยเรียงตาม q

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;
}

ข้อผิดพลาดจาก cmpfunc

ส่วนมากมักเกิดจากการเขียน cmpfunc เช่นนี้

int cmpfunc(const void* a, const void* b){
    return *(int*)a - *(int*)b;
}

สำหรับคนที่ไม่รู้ว่า 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

จะเห็นได้ว่าโค้ดนี้สั้นมากและเป็นที่นิยมใช้ อย่างไรก็ตาม วิธีนี้อาจทำให้เกิดปัญหาตามหัวข้อ ข้อควรระวัง
เมื่อใช้ในการเรียง 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;
}

ปัญหาเกิดจากเมื่อนำ 12.2 - 12.1 = 0.1 แต่เมื่อโดนบังคับให้ return เป็น int จึงทำให้จาก 0.1 โดน 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;
}

ปัญหาเกิดจากเมื่อนำ 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] ก็อาจเขียนโค้ดดังนี้

qsort(A + 1, n, sizeof(A[0]), cmpfunc);

หรือ

qsort(&A[1], n, sizeof(A[0]), cmpfunc);

ถ้าต้องการเรียงจาก array ในช่วง [a,b] ก็อาจเขียนโค้ดดังนี้

qsort(A + a, b - a + 1, sizeof(A[0]), cmpfunc);

หรือ

qsort(&A[a], b - a + 1, sizeof(A[0]), cmpfunc);
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License