Quick Sort [การเรียงข้อมูลอย่างรวดเร็ว...]

ผมเชื่อว่าสำหรับคนที่เคยเข้าค่ายโอลิมปิกวิชาการ หรือที่ทุกคนเรียกกันอย่างติดปากว่าค่ายสอวน. โดยเฉพาะในสาขาคอมพิวเตอร์ คงต้องคุ้นเคยกับการจัดเรียงข้อมูลตามอย่างที่เราต้องการหรือว่า SORTING อย่างแน่นอน ไม่ว่าจะเป็นการเรียงลำดับข้อมูลจาก น้อย -> มาก หรือจาก มาก -> น้อย ซึ่งเราก็จะพบว่าอัลกอริทึม (Algorithm) สำหรับการ Sorting นั้นมีด้วยกันหลากหลายประเภท ซึ่งแน่นอนว่าแต่ละ Algorithm ก็จะมีทั้งข้อดีและข้อเสีย แต่สำหรับวันนี้ผมอยากจะมาพูดถึงเรื่อง Quick Sort ซึ่งผมเดาว่าทุกคนน่าจะเคยได้ยินกันมา แต่คงจะไม่เคยได้ implement กันสักครั้ง ซึ่งสำหรับตัวผมในตอนที่เข้าค่ายสอวน. ก็ไม่เคยที่จะมาสนใจกับ Quick Sort เลย เพราะว่าอะไรก็ไม่รู้เหมือนกัน แต่เมื่อไม่กี่วันที่ผ่านมา ผมก็ได้ลองทำสักหน่อย ซึ่งผมก็จะแชร์ประสบการณ์และความเข้าใจของผมให้กับเพื่อนๆ ได้อ่านกัน

แนวคิด : 

    สำหรับแนวคิดของ Quick Sort นั้นไม่ได้มีอะไรมากมาย สิ่งที่สำคัญมากที่สุดที่เราจะต้องรู้ก็คือ "จุดหมุน" หรือ Pivot ซึ่งมันจะเป็นตัวตัดสินชะตาชีวิตของ quick sort ของเราเลยก็ว่าได้ สมมติว่าเรามีข้อมูลในรูป array num[5] = {5, 2, 12, 4, 6} ในตอนแรกให้เราเลือกเลขอะไรก็มาเป็น Pivot ของเรา ขอสมมติว่า ให้ 5 เป็นจุดหมุน จากนั้นเราจะทำการสลับตำแหน่งของ Pivot กับสมาชิกตัวสุดท้ายเพื่อความง่ายต่อการ Implement 

num[5] = {6, 2, 12, 4, *5} ; * = Pivot ; ที่นี้เราก็จะใช้หลักการคล้ายๆ two-pointer ก็คือสร้างตัวแปรมา 2 ตัว คือ L [left] กับ R [right] ซึ่ง L = 0 [ตำแหน่งเริ่มต้น], R = 4-1 = 3 [ตำแหน่งสุดท้ายที่ไม่นับรวม Pivot] จากนั้นเราจะทำการเลื่อน pointer ทั้ง 2 ให้เข้าใกล้กันเรื่อยๆ ตามเงื่อนไขที่จะแสดงข้างล่าง

6, 2, 12, 4, *5

L            R

ตอนแรกให้เรา check ที่ตัวแปร L ว่าตัวเลขในปัจจุบันมากกว่า Pivot หรือไม่ถ้าไม่เราก็จะเพิ่มค่าให้ L ไป 1 จนกว่าจะได้ค่าที่มากกว่า Pivot ในทางกลับกันเราจะต้อง check ที่ตัวแปร R ว่าตัวเลขในปัจจุปันน้อยกว่าหรือเท่ากับ Pivot หรือไม่ถ้าไม่ก็ลดค่าให้ R ไป 1 จนกว่าจะได้ค่าที่น้อยกว่าหรือเท่ากับ Pivot

L = 0, R=  3

6, 2, 12, 4, *5

L            R

จะเห็นได้ว่าทั้ง L กับ R ตรงตามเงื่อนไขด้านบน จากนั้นเราจะทำการสลับตัวเลขในตำแหน่งที่ L และ R

4, 2, 12, 6, *5

L            R

พอสลับแล้วเราก็จะเพิ่มค่าให้ L และลดค่าให้ R ไป 1

4, 2, 12, 6, *5

    L   R

เนื่องจาก L ไม่ตรงตามเงื่อนไขก็จะเพิ่มค่าให้ L 

4, 2, 12, 6, *5

        L,R          

เนื่องจาก R ไม่ตรงตามเงื่อนไขก็จะลดค่าให้ R

4, 2, 12, 6, *5

    R   L

ทีนี้เมื่อไหร่ก็ตามที่ L > R ก็จะหยุดการทำงานทันที และเราก็จะสลับเลขที่เป็น Pivot กับเลขในตำแหน่งที่ L

4, 2, *5, 6, 12

 

ที่นี้เราก็จะสังเกตได้ว่าข้างซ้ายของ Pivot จะเป็นเลขที่น้อยกว่าหรือเท่ากับ Pivot และด้านขวาจะเป็นเลขที่มากกว่า Pivot เสมอ

จากนั้นเราก็จะทำการใช้หลักการเดิมแต่ทำกับข้อมูลที่เล็กลงที่อยู่ทั้ง 2 ข้างของ Pivot ได้แก่ในช่วง

{4, 2} และ {6, 12} โดยใช้หลักการ Recursion เข้ามาช่วย

และในท้ายที่สุด เราก็จะได้ array ที่เรียงข้อมูลจากน้อยไปมากเรียบร้อย

Example for Implementation : 

int num[n];

Void quick_sort(int left, int right){

    if(left >= right)

        return;

    // suppose we are going to choose the first element to be our pivot //

    // we are going to swap pivot and the last element for our ease // 

    num[0] ^= num[n-1] ^= num[0] ^= num[n-1]; // Note : "Exclusive Or" i.e. xor, can be used for                swapping two numbers //.

    int pivot = num[n-1];

    int L = left, R = right;

    while(L <= R){

        while(L <= R && num[L] <= pivot)

            ++L;

        while(L <= R && num[R] > pivot)

            --R;

        if(L > R)

            break;

        num[L] ^= num[R] ^= num[L] ^= num[R]; // or you can use swap(num[L], num[R]) //

        ++L, --R;

    }

    num[L] ^= num[right] ^= num[L] ^= num[right]; // swap Lth element and pivot //

    quick_sort(left, L-1);

    quick_sort(L+1, Right);

    return;

}