CoE KKU

quicksort เป็นอัลกอริทึมที่รับรู้กันว่าในทางปฏิบัติแล้วมันงานได้เร็วที่สุด มีค่า average running time เป็น $O(N\ log\ N)$ อย่างไรก็ตามกรณี worst-case ของมันยังคงใช้ $O(N^2)$ แต่ก็สามารถปรับปรุงให้ดีขึ้นได้อย่างมากเพื่อลดเวลาการทำงานในกรณีนี้ลงได้ quicksort ใช้อัลกอริทึมแบบ recursive ที่เรียกว่า divide-and-conquer เช่นเดียวกับ mergesort อัลกอริทึมพื้นฐานของ quicksortที่ใช้ในการจัดเรียงค่าในอะเรย์ S มี 4 ขั้นตอน ดังนี้:

1. ถ้าจำนวนสมาชิกของ S มี 0 หรือ 1 ตัว ก็จบการทำงาน (return) ทันที
2. เลือกสมาชิกตัวหนึ่ง (v) ใน S ใช้เป็นค่าที่เรียกว่า pivot
3. ให้ทำการแบ่งสมาชิกที่เหลือใน S - {v} ออกเป็นสองกลุ่มคือ S1 = {x ∈ S - {v} | x ≤ v}, และ S2 = {x ∈ S - {v}| x ≥ v}
4. ให้ค่ากลับเป็น { quicksort(S1) ตามด้วย v และตามด้วย quicksort(S2) }

ในขั้นตอนที่ 3 ซึ่งเป็นขั้นตอนการแบ่งสมาชิก (partition) นั้นไม่ได้กำหนดว่าจะให้ทำอย่างไรกับสมาชิกที่มีค่าเท่ากับ pivot เนื่องจากว่ามันขึ้นอยู่กับการตัดสินใจในการออกแบบโดยหวังว่าจะทำให้การทำงานมีประสิทธิภาพมากที่สุด โดยเราหวังว่าการทำงานนี้จะสามารถจัดให้ค่าที่น้อยกว่าหรือเท่ากับค่า pivot มีจำนวนประมาณครึ่งหนึ่งจะถูกย้ายไปไว้ใน S1 และอีกครึ่งหนึ่งที่เหลือก็จะถูกย้ายไปไว้ใน S2 ลักษณะเดียวกับ balance binary search tree

รูปที่ 7.11 แสดง quicksort ของตัวเลขกลุ่มหนึ่ง เลือกค่า pivot (โดยบังเอิญ) เป็น 65 แบ่งสมาชิกที่เหลือออกเป็นสองกลุ่ม จากนั้นจัดเรียงกลุ่มข้อมูลย่อยทางด้านน้อยกว่าแบบ recursive จะได้ 0, 13, 26, 31, 43, 57 และจัดเรียงกลุ่มข้อมูลย่อยทางด้านมากกว่าในลักษณะเดียวกัน ก็จะได้ข้อมูลจัดเรียงทั้งหมด

ดังได้กล่าวมาแล้วว่าการทำงานของ quicksort มีลักษณะเดียวกับ mergesort คือการแก้ปัญหาแบบ recursive กระทำต่อปัญหาย่อย 2 ปัญหาและต้องใช้การทำงานอื่น ๆ ที่ใช้เวลาแบบ linear เพื่อทำงานอื่น ๆ เพิ่มเติม (คือขั้นตอนที่ 3 ของอัลกอริทึม) แต่จะแตกต่างจาก mergesort ที่ quicksort ไม่สามารถประกันได้ว่าขนาดของปัญหาย่อยที่แบ่งได้นั้นจะมีขนาดเท่ากันซึ่งเป็นไปได้ที่จะทำให้ได้ผลที่ไม่พึงประสงค์ในแง่ของ running time เหตุที่ quicksort ทำงานได้เร็วกว่า mergesort ก็คือในการทำงาน partition นั้นสามารถทำได้ในรูปแบบที่เรียกว่า in place partition และเป็นวิธีที่มีประสิทธิภาพมากซึ่งสามารถชดเชยความไม่เท่ากันของขนาดของปัญหาย่อยเมื่อทำ recursive call มีวิธีการทำงานหลายรูปแบบที่เป็นไปได้สำหรับการทำงานในขั้นตอนที่ 2 และขั้นตอนที่ 3 ของอัลกอริทึม วิธีการที่นำเสนอในที่นี้เป็นวิธีที่ได้รับการวิเคราะห์และทดสอบมาแล้วว่าเป็นวิธีที่มีประสิทธิภาพ

การเลือก pivot ที่มักใช้กันแต่เป็นการเลือกที่ผิด คือ การเลือกสมาชิกตัวแรกเป็น pivot การเลือกแบบนี้อาจจะยอมรับได้ถ้าข้อมูลเป็นแบบสุ่มจริง ๆ แต่ถ้าข้อมูลเริ่มต้นเป็นข้อมูลที่ได้รับการจัดเรียงหรือจัดเรียงย้อนกลับมาก่อนแล้ว การเลือกค่า pivot นี้ก็เป็นการเลือกที่แย่มาก เพราะในการแยกสมาชิกทั้งหมดจะถูกย้ายเข้าไปใน S1 หรือไม่ก็ถูกย้ายเข้าใน S2 ทั้งหมดและจะเกิดเหตุการณ์เช่นนี้ตลอดทุกครั้งของ recursive call ผลที่เกิดขึ้นก็คือ quicksort จะใช้เวลาเป็น quadratic โดยที่เนื้อแท้แล้วไม่ได้ทำงานใด ๆ เลยซึ่งเป็นสิ่งที่ไม่พึงปรารถนา การมีข้อมูลเริ่มต้นเป็น presort หรือข้อมูลเริ่มต้นที่มีส่วนที่เป็น presort ขนาดใหญ่ๆ เป็นสิ่งที่เกิดขึ้นได้เสมอในทางปฏิบัติ ดังนั้น การเลือกใช้สมาชิกตัวแรกเป็น pivot จึงเป็นสิ่งที่ไม่พึงกระทำอย่างยิ่ง อีกทางเลือกหนึ่งในการเลือกค่าที่จะใช้เป็น pivot คือเลือกค่าให้เป็นค่าเฉลี่ยของสมาชิกสองค่าแรกซึ่งก็จะให้ผลที่ไม่แตกต่างจากการใช้สมาชิกตัวแรกที่กล่าวมาแล้ว วิธีที่ดูเหมือนปลอดภัยในการเลือก pivot คือใช้การเลือกค่าแบบสุ่ม วิธีนี้เป็นวิธีที่ปลอดภัยที่สุดถ้าหากว่า random number generator ไม่มีข้อบกพร่องใด ๆ (ซึ่งความจริงมักจะเกิดขึ้นบ่อย ๆ) แต่เนื่องจากโดยทั่วไปแล้ว random number generation เป็นการทำงานที่ต้องเสียค่าใช้จ่าย (เวลา) มากและทำให้ไม่ช่วยในการลดเวลาการทำงานโดยเฉลี่ยของอัลกอริทึมโดยรวมลงได้

วิธีที่ดีที่สุดในการเลือก pivot น่าจะใช้ค่า median ของค่าข้อมูลทั้งหมด แต่โชคไม่ดีที่การคำนวณค่าดังกล่าวนั้นมีความยุ่งยากและจะทำให้การทำงานของ quicksort ช้าลงอย่างมาก วิธีการเลือกค่า pivot ที่ใช้กันทั่วไปคือใช้ค่า median ของสมาชิกตัวซ้ายสุด, ตัวขวาสุดและตัวที่อยู่ตำแหน่งตรงกลางของข้อมูล (Median-of-Three) เช่น อินพุต 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 มีสมาชิกตัวซ้ายสุดคือ 8 ตัวขวาสุด คือ 0 และตัวกลาง (ณ ตำแหน่ง ⌊(left + right)/2⌋) คือ ค่า 6 ดังนั้น pivot คือ v = 6

การแบ่งอะเรย์ที่เป็นอินพุตมีวิธีการทำอยู่หลายวิธี วิธีที่เสนอนี้เป็นเพียงวิธีการหนึ่งเท่านั้นที่ให้ผลค่อนข้างดีและเป็นวิธีการที่ค่อนข้างจะง่าย ขั้นตอนแรกเป็นการย้ายค่า pivot ออกจากอะเรย์โดยการสลับค่ามันกับสมาชิกตัวสุดท้าย ให้ i เริ่มต้นที่สมาชิกตัวแรกและ j เริ่มต้นที่สมาชิกรองจากตัวสุดท้าย รูปข้างล่างนี้แสดงสถานะเริ่มต้นของอะเรย์ตัวอย่างที่ได้กล่าวมาข้างบน

สำหรับขณะนี้สมมติให้สมาชิกมีค่าไม่ซ้ำกัน และจะกล่าวถึงกรณีที่มีค่าซ้ำในภายหลัง อัลกอริทึมที่จะนำเสนอนี้จะสามารถจัดการกับกรณีที่สมาชิกทุกตัวมีค่าเท่ากันได้ สิ่งที่ต้องการได้รับจากการทำ partition คือ ต้องการย้ายสมาชิกที่มีค่าน้อยกว่า pivot ทั้งหมดไปอยู่ทางด้านซ้ายของอะเรย์ และสมาชิกทุกตัวที่มีค่ามากกว่าค่า pivot ไปอยู่ทางด้านขวาของอะเรย์ ในขณะที่ i อยู่ด้ายซ้ายของ j เราจะเคลื่อน i ไปทางขวาโดยจะเคลื่อนผ่านค่าที่น้อยกว่าค่า pivot ไป และจะเลื่อน j ไปทางด้านซ้ายโดยจะเคลื่อนผ่านค่าที่มากกว่าค่า pivot ไป เมื่อ i และ j หยุดเลื่อนหมายความว่าเวลานั้น i อยู่ที่ตัวที่มีค่ามากกว่าค่า pivot และ j อยู่ที่ตัวที่มีค่าที่น้อยกว่าค่า pivot และถ้า i ยังคงอยู่ทางซ้ายของ j ก็ให้สลับค่าระหว่างค่าที่ตำแหน่ง i และ j จากรูปตัวอย่างข้างบนจะเห็นว่า i จะไม่เลื่อนแต่ j จะเลื่อนไปหนึ่งตำแหน่ง ดังนี้

จากนี้จะทำการสลับค่าระหว่างค่าที่ตำแหน่ง i และ j และเริ่มทำงานกระบวนการแบบเดิมไปเรื่อย ๆ จนกว่าตำแหน่ง i และ j มาอยู่ในตำแหน่งที่ข้ามกัน ดังรูปต่อไปนี้

สถานะก่อนการสลับค่าครั้งที่ 2

สถานะหลังการสลับค่าครั้งที่ 2

สถานะก่อนการสลับค่าครั้งที่ 3

สถานะในขณะนี้ตำแหน่งของ i และ j ถูกเลื่อนมาอยู่ในตำแหน่งที่ข้ามกันแล้วจึงไม่ต้องทำการสลับค่าอีก สุดท้ายให้ทำการสลับค่าระหว่างค่าที่อยู่ที่ตำแหน่งของ i และค่า pivot ซึ่งจะได้อะเรย์ดังรูปข้างล่างนี้

เมื่อมีการสลับค่าระหว่างค่า pivot ด้วยค่าที่ตำแหน่ง i ในขั้นตอนสุดท้ายก็หมายความว่าสมาชิกทุกตัวในตำแหน่งที่ p < i จะมีค่าน้อยกว่า เนื่องจากไม่ว่าตำแหน่ง p จะเป็นค่าที่น้อยกว่าหรือค่าที่มากกว่าในขณะเริ่มต้นนั้นมันก็จะถูกแทนที่จากการสลับ ซึ่งก็หมายความว่าสมาชิกในตำแหน่งที่ p > i เป็นค่าที่มากกว่า

มีรายละเอียดที่สำคัญที่ยังไม่ได้กล่าวถึงเลย คือ จะทำอย่างไรกับค่าที่เท่ากันกับค่า pivot ปัญหาที่ต้องการคำตอบก็คือ i และ j ควรจะหยุดหรือไม่เมื่อมันพบกับสมาชิกที่มีค่าเท่ากับ pivot ความจริงแล้วทั้ง i และ j ควรจะทำเหมือน ๆ กัน เพื่อไม่ให้เกิดการเอนเอียงในการทำ partition กล่าวคือ ถ้าให้ i หยุดแล้วไม่ให้ j หยุด ก็จะทำให้ค่าทั้งหมดที่เท่ากับ pivot ถูกย้ายไปใน S2

พิจารณาในกรณีที่ทุกค่าเท่ากันหมด ดังนี้ ถ้าทั้ง i และ j หยุดก็หมายความว่าจะมีการสลับค่าสมาชิกเกิดขึ้นมากครั้งถึงแม้ว่าดูจะไม่เกิดประโยชน์ใด ๆ แต่ก็เกิดผลด้านบวกคือ i และ j จะเลื่อนมาข้ามตำแหน่งกันที่ตรงกลางดังนั้นเมื่อมีการแทนที่ค่า pivot จะแบ่งส่วนอะเรย์ออกเป็น 2 ส่วนที่เกือบจะเท่า ๆ กัน และเช่นเดียวกับ mergesort วิเคราะห์ running time ได้ $O(N\ log\ N)$

ถ้าทั้ง i และ j ไม่หยุดก็จะไม่มีการสลับค่าใด ๆ เกิดขึ้น ดูเหมือนเป็นเรื่องที่ดีและจะทำการสลับค่า pivot กับค่าตำแหน่งสุดท้ายของค่าตำแหน่ง i ซึ่งเป็นค่าตำแหน่งรองสุดท้าย การทำเช่นที่กล่าวมานี้จะทำให้การแบ่งส่วนข้อมูลออกเป็นสองส่วนที่มีขนาดแตกต่างกันมากและจะทำให้มี running time เป็น $O(N^2)$ เช่นเดียวกับการเลือกใช้ pivot เป็นค่าของข้อมูลตัวแรกในอะเรย์ที่เป็น presort

ดังนั้น ทางที่ดีจึงควรต้องหยุดและทำการสลับค่า (ถึงแม้ค่าจะเท่ากันก็ตาม) เพื่อจะได้แบ่งข้อมูลออกเป็นสองส่วนเท่า ๆ กัน และ running time ไม่เป็น quadratic

สำหรับข้อมูลขนาดเล็ก (N < 20) quicksort ทำงานได้ไม่ดีเท่า insertion sort ดังนั้น จึงไม่ควรใช้ quicksort ในแบบ recursiveสำ หรับข้อมูลขนาดเล็ก แต่ควรใช้อัลกอริทึมที่เหมาะกับข้อมูลขนาดเล็กเช่น insertion sort ดังนั้นควรใช้ quicksort จนกระทั่งเหลือข้อมูลจำนวนน้อย ๆ จำนวนหนึ่งที่ไม่ถูกจัดเรียงแล้วใช้ insertion sort ทำงานต่อ เนื่องจาก insertion sort ทำงานได้ดีกับข้อมูลที่มีการจัดเรียงเกือบจะทั้งหมดแล้ว และการทำแบบนี้ทำให้ทำงานเร็วขึ้นประมาณ 15% จำนวนที่เหมาะสมที่เหลือ คือเมื่อ N อยู่ระหว่าง 5 ถึง 20

รูปที่ 7.12 เป็น driver สำหรับ quicksort รูปแบบทั่วไปของรูทีนการจัดเรียงค่าคือ จะเป็นการส่งผ่านอะเรย์และขนาดของอะเรย์ (left และ right) ที่จะทำการจัดเรียงค่า รูทีนแรกที่จะกล่าวถึงคือรูทีนสำหรับการเลือกค่า pivot วิธีที่ง่ายที่สุดคือใช้การจัดเรียงค่า a[left], a[right] และ a[center] ในแบบ in place ซึ่งมีผลทำให้ตัวที่มีค่าน้อยที่สุดถูกย้ายไปอยู่ในตำแหน่ง a[left] ซึ่งจะเป็นตำแหน่งที่อยู่ที่ต้องการหลังทำ partition นั่นเอง ส่วนค่าที่มากที่สุดจะถูกย้ายไปยังตำแหน่งที่ควรจะอยู่ได้อย่างถูกต้องคือตำแหน่งที่ a[right] เนื่องจากมันมีค่ามากกว่าค่า pivot ดังนั้นเราก็จะสามารถบรรจุค่า pivot ลงในตำแหน่งของ a[right – 1] และกำหนดค่าเริ่มต้นให้ i และ j ด้วยค่า left – 1 และ right – 2 ตามลำดับเพื่อใช้ในขั้นตอนการทำ partition ประโยชน์ที่ได้รับอีกประการคือ เนื่องจาก a[left] มีค่าน้อยกว่าค่า pivot ดังนั้นเราจึงสามารถใช้มันเป็นค่า sentinel สำหรับ j ได้ทำให้ไม่ต้องกังวนกับการที่ค่า j จะวิ่งผ่านค่าสุดท้ายไปได้ รูปที่ 7.13 เป็นโปรแกรมเพื่อทำ median-of-three ที่ได้ผลตามที่ได้กล่าวมาแล้วนี้

โปรแกรมรูปที่ 7.14 เป็นส่วนที่ทำ quicksort ซึ่งประกอบด้วยส่วนที่ทำ partition และการเรียกใช้แบบ recursive สังเกตด้วยว่าในบรรทัดที่ 3 เป็นการกำหนดค่าเริ่มต้นให้ i และ j มีค่าเกินค่าที่ถูกต้องของมันอยู่ 1 จะต้องเขียนโปรแกรมสำหรับการสลับค่าที่ใช้ในบรรทัดที่ 8 คำสั่งในบรรทัดที่ 5 และ 6 แสดงให้เห็นสาเหตุที่ทำให้ quicksort ทำงานได้อย่างรวดเร็วอย่างไร inner loop ของอัลกอริทึมประกอบด้วยการเพิ่มค่าและลดค่า (เพิ่มหรือลดลง 1 เท่านั้น) ตรวจสอบค่าและกระโดดข้ามข้ามการทำงาน ข้อที่ต้องระมัดระวังการเขียนโปรแกรมนี้ คือถ้าใช้คำสั่งบรรทัดที่ 3 ถึง 9 ด้วยคำสั่งรูปที่ 7.15 และถ้าค่า a[i] = a[j] = pivot ก็จะทำให้ลูปของ for ทำงานเป็น infinite loop เนื่องจากมันจะไม่เข้าทำงานใน while-loop เลย

public static void quicksort( Comparable [ ] a )
{  
	quicksort( a, 0, a.length - 1 );
}

รูปที่ 7.12 driver สำหรับ quicksort

private static Comparable median3( Comparable [ ] a, int left, int right )
{       
    int center = ( left + right ) / 2;
    if( a[ center ].compareTo( a[ left ] ) < 0 )
        swapReferences( a, left, center );
    if( a[ right ].compareTo( a[ left ] ) < 0 )
        swapReferences( a, left, right );
    if( a[ right ].compareTo( a[ center ] ) < 0 )
        swapReferences( a, center, right );
    swapReferences( a, center, right - 1 ); // Place pivot at right - 1
    return a[ right - 1 ];
}

รูปที่ 7.13 โปรแกรมเพื่อทำ median-of-three

private static void quicksort( Comparable [ ] a, int left, int right )
        {
/* 1*/      if( left + CUTOFF <= right )
            {
/* 2*/          Comparable pivot = median3( a, left, right );
                    // Begin partitioning
/* 3*/          int i = left, j = right - 1;
/* 4*/          for( ; ; )
                {
/* 5*/              while( a[ ++i ].compareTo( pivot ) < 0 ) { }
/* 6*/              while( a[ --j ].compareTo( pivot ) > 0 ) { }
/* 7*/              if( i < j )
/* 8*/                  swapReferences( a, i, j );
                    else
/* 9*/                  break;
                }
/*10*/          swapReferences( a, i, right - 1 );   // Restore pivot
/*11*/          quicksort( a, left, i - 1 );    	    // Sort small elements
/*12*/          quicksort( a, i + 1, right );   	    // Sort large elements
            }
            else  		// Do an insertion sort on the subarray 
/*13*/          insertionSort( a, left, right );
        }

รูปที่ 7.14 ส่วนที่ทำ quicksort

/* 3*/          int i = left + 1, j = right - 2;
/* 4*/          for( ; ; )
                {
/* 5*/              while( a[ i ].compareTo( pivot ) < 0 ) i++;
/* 6*/              while( a[ j ].compareTo( pivot ) > 0 ) j--;
/* 7*/              if( i < j )
/* 8*/                  swapReferences( a, i, j );
                    else
/* 9*/                  break;
                }

รูปที่ 7.15

เนื่องจาก quicksort เป็น recursive ดังนั้นในการวิเคราะห์จึงต้องแก้สมการ recurrence สมมุติให้ใช้ pivot แบบสุ่ม (คือ ไม่ใช้ median-of-three partitioning) และไม่ใช้ cutoff สำหรับข้อมูลขนาดเล็ก ทำให้ได้ T(0) = T(1) = 1 เช่นเดียวกับ mergesort และจะเห็นว่า running time ของ quicksort เท่ากับ running time ของการเรียกใช้แบบ recursive สองครั้ง บวกกับ linear time ที่ใช้สำหรับการทำ partition (การเลือก pivot ใช้เวลาคงที่) ได้ relation สำหรับ quicksort พื้นฐาน ดังนี้ $$T(N)= T(i)+ T(N - i - 1)+ cN \tag{7.1}$$ เมื่อ i = |S1| คือจำนวนสมาชิกใน S1

Worst-Case Analysis
เกิดขึ้นได้เมื่อค่า pivot เป็นค่าที่น้อยที่สุดตลอดเวลา ซึ่งจะทำให้ i = 0 และถ้าเราไม่สนใจค่าที่ T(0) = 1 ซึ่งไม่มีความสำคัญก็จะได้สมการ recurrence ดังนี้ $$ T(N) = T(N - 1) + cN,\ \ N > 1 \tag{7.2}$$ และเมื่อแก้สมการ recurrence จะได้ $$ T(N) = O(N^2)$$

Best-Case Analysis
ในกรณี best case มีค่า pivot อยู่ตรงกลาง เพื่อให้ง่ายขึ้นเราจะให้อะเรย์ย่อยทั้งสองเท่ากับครึ่งหนึ่งของอะเรย์เดิม เนื่องจากเรากำลังให้ความสนใจกับค่า Big-O ดังนั้นการสมมติแบบนี้จึงไม่เป็นการเกินเลย ดังนั้น $$ T(N) = 2T(N/2) + cN \tag{7.3}$$ และเมื่อแก้สมการ recurrence จะได้ $$ T(N) = O(N lg N)$$

Average-Case Analysis\ กรณีเฉลี่ยเป็นกรณีที่ยุ่งยากมาก สมมุติให้ขนาดต่างๆ ที่จะเกิดขึ้นได้ของ S1 นั้นมีโอกาสเกิดขึ้นได้เท่า ๆ กันทุกขนาด และดังนั้นจึงมีความน่าจะเป็น (probability) ของแต่ละขนาดคือ 1/N การสมมุติเช่นนี้หมายความว่าการ partition และการเลือก pivot เป็นแบบสุ่ม จากข้อสมมุติเช่นนี้ ค่าเฉลี่ยของ T(i), และ (เช่นกัน) ของ T(N - i -1), คือ $(1/N) ∑_{j=0}^{N-1} T(j) $ หรือพิจารณาได้ดังนี้ ถ้า T(N) เป็นค่าเฉลี่ยของค่าใช้จ่าย quicksort จำนวนสมาชิก N ตัว ค่าเฉลี่ยของค่าใช้จ่ายในการเรียกใช้แบบ recursive แต่ละครั้งเท่ากับค่าเฉลี่ยของความเป็นไปได้ทั้งหมดของขนาดทุกขนาดของปัญหาย่อย ดังนั้น ค่าเฉลี่ยของการเรียกใช้แบบ recursive ของปัญหาย่อยทางซ้ายและขวาจึงเป็น:

ดังนั้น สมการ 7.1 จะเป็น $$T(N)=2/N [∑_{j=0}^{N-1}T(j)] + cN \tag{7.4}$$ คูณสมการ 7.4 ด้วย N จะได้ $$NT(N)=2[∑_{j=0}^{N-1}T(j)]+cN^2 \tag{7.5}$$ ทำการ iterate สมการ 7.5 จะได้ $$(N - 1)T(N-1)=2[∑_{j=0}^{N-2}T(j)]+c(N-1)^2 \tag{7.6}$$ ลบสมการ 7.5 ด้วยสมการ 7.6 $$NT(N) - (N - 1)T(N-1)=2T(N-1)+2cN-c \tag{7.7}$$ จัดรูปสมการ 7.7 และตัดเทอม –c ทิ้งจะได้ $$NT(N) = (N + 1)T(N-1)+2cN \tag{7.8}$$ หารสมการ 7.8 ด้วย N(N+1) จะได้ $$(T(N))/(N+1) = (T(N-1))/N+2c/(N+1) \tag{7.9}$$ แก้สมการ 7.9 ด้วยวิธี iteration จะได้ $$(T(N))/(N+1) = (T(1))/2+2c∑_{i=3}^{N+1} 1/i \tag{7.10}$$ เทอมท้ายของ 7.10 มีค่าประมาณ $loge(N+1) + \gamma - 3/2$ เมื่อ $\gamma = 0.577$ ซึ่งคือค่า Euler's constant ดังนั้น $$(T(N))/(N+1) = O(log\ N)$$ จะได้ $$ T(N)= O(N\ log\ N)$$

เราสามารถปรับปรุง quicksort เพื่อแก้ปัญหาการเลือก (selection problem) ที่กล่าวถึงมาแล้วก่อนหน้านี้ (บทที่ 1 และ 6) การใช้ priority queue สามารถค้นหาค่าที่มากที่สุดในอันดับที่ k ด้วยเวลา O(N + k log N) ซึ่งถ้าค่าที่ต้องการหานั้นเป็นค่า median อัลกอริทึมนี้ก็จะมี running time เป็น O(N log N)

ในที่นี้จะกล่าวถึงอัลกอริทึมที่เกือบจะเหมือนกับอัลกอริทึมของ quicksort เพื่อใช้ในการค้นหาค่าที่น้อยเป็นอันดับ k ในกลุ่มข้อมูล S โดยที่สามขั้นตอนแรกของอัลกอริทึมที่จะใช้นี้จะเหมือนกันกับของ quicksort และเรียกอัลกอริทึมนี้ว่า quickselect กำหนดให้ $|S_i|$ เป็นจำนวนสมาชิกในเซต $S_i$ อัลกอริทึมของ quickselect คือ

1. ถ้า |S| = 1, นั่นคือ k = 1 และให้ค่ากลับเป็นสมาชิกใน S เป็นคำตอบ ถ้าใช้การ cutoff สำหรับข้อมูลขนาดเล็กและ |S| ≤ CUTOFF ก็ให้จัดเรียง S และให้ค่ากลับเป็นสมาชิกตัวที่น้อยเป็นอันดับ k
2. เลือกค่า pivot ซึ่ง v ∈ S.
3. ทำ Partition เซตของ S - {v} ให้เป็นเซต S1 และ S2, ดังที่ทำกับ quicksort
4. ถ้า k ≤ |S1| นั่นคือสมาชิกที่มีค่าน้อยอันดับ k ต้องอยู่ในเซต S1 กรณีนี้ให้ส่งค่ากลับเป็น quickselect (S1, k)
5. ถ้า k = 1 + |S1| นั่นคือ ค่า pivot เป็นค่าที่น้อยเป็นอันดับ k ก็ให้ค่ากลับเป็นค่า pivot เป็นคำตอบ
   • ถ้าไม่เป็นไปตามกรณีที่กล่าวมานี้ ก็หมายความว่า ค่าที่น้อยเป็นอันดับ k นั้นอยู่ใน S2 ซึ่งก็จะเป็นสมาชิกตัวที่มีค่าน้อยเป็นอันดับที่ (k - |S1| - 1) ที่อยู่ใน S2 ให้ทำการ recursive call และให้ค่ากลับเป็น quickselect (S2, k - |S1| - 1)

จะเห็นว่า quickselect ทำการเรียกใช้ฟังก์ชันแบบ recursive เพียงครั้งเดียวเท่านั้น (ในขณะที่ quicksort เรียก recursive 2 ครั้ง) สำหรับกรณี worst case ของ quickselect จะเท่ากันกับของ quicksort คือ O(N2) เนื่องจากกรณี worst case ของ quicksort นั้นเกิดขึ้นเมื่อ S1 หรือ S2 เป็นเซ็ตว่างนั่นเอง ส่วนกรณีเฉลี่ยของ quickselect เป็น O(N) และการวิเคราะห์หา running time ก็สามารถทำได้ด้วยการเรียนแบบกับที่ทำกับ quicksort

โปรแกรม quickselect แสดงในรูปที่ 7.16 เมื่อโปรแกรมทำงานเสร็จสิ้นข้อมูลที่มีค่าน้อยเป็นอันดับ k ที่ต้องการก็จะอยู่ที่ตำแหน่ง k – 1 (เนื่องจากดัชนีเริ่มที่ 0)

private static void quickSelect( Comparable [ ] a, int left, int right, int k )
        {
/* 1*/      if( left + CUTOFF <= right )
            {
/* 2*/          Comparable pivot = median3( a, left, right );
                    // Begin partitioning
/* 3*/          int i = left, j = right - 1;
/* 4*/          for( ; ; )
                {
/* 5*/              while( a[ ++i ].compareTo( pivot ) < 0 ) { }
/* 6*/              while( a[ --j ].compareTo( pivot ) > 0 ) { }
/* 7*/              if( i < j )
/* 8*/                  swapReferences( a, i, j );
                    else
/* 9*/                  break;
                }
/*10*/          swapReferences( a, i, right - 1 );   // Restore pivot
/*11*/          if( k <= i )
/*12*/              quickSelect( a, left, i - 1, k );
/*13*/          else if( k > i + 1 )
/*14*/              quickSelect( a, i + 1, right, k );
            }
            else  		// Do an insertion sort on the subarray 
/*15*/           insertionSort( a, left, right );
        } 

รูปที่ 7.16 โปรแกรม quickselect