Abstract-~ -This paper describes th

Abstract-~ -This paper describes the results of a large empirical study to measure the run-time behavior
of Quick sort by using various methods of computing the pivot element for medium to large sire randomly
generated integer data. The results of our study contradict the common notion that Quick sort gives best
performance if median of three scheme is used to compute the pivot element and array partitions having
< IO elements are sorted by using insertion sort. It was found that Quicksort performs best when median
of three scheme is used to decide the pivot element and arrays with 14 elements are hand sorted. Our
method gives an average speedup of >9% when compared to the method with a cutoff of IO and
sub-arrays with < IO elements insertion sorted for 1000 < N < 1.5 x IO”. Our study shows that advanced
hardware features allow for implementation of very fast codes for sorting small arrays. and usmg such
codes instead of insertion sort can lead to substantial improvements for Quicksort. as conjectured by
Sedgewick many years ago. Copyright Q 1996 Elsevier Science Ltd

ผลลัพธ์ (ไทย) 1:

บทคัดย่อ- ~ -เอกสารนี้อธิบายผลลัพธ์ของการศึกษารวมขนาดใหญ่เพื่อวัดพฤติกรรมขณะทำงานของการเรียงลำดับอย่างรวดเร็วโดยใช้วิธีการต่าง ๆ ของคอมพิวเตอร์องค์ประกอบสาระสำคัญขนาดกลางถึงขนาดใหญ่เดินแบบสุ่มสร้างข้อมูลจำนวนเต็ม ผลการศึกษาของเราขัดแย้งกับแนวคิดทั่วไปที่เรียงลำดับอย่างรวดเร็วให้ดีที่สุดใช้เพื่อคำนวณสาระสำคัญองค์ประกอบและเรย์พาร์ติชันมีประสิทธิภาพถ้ามัธยฐานของโครงร่างสาม< IO องค์ประกอบเรียงลำดับโดยเรียงลำดับแบบแทรก พบว่า Quicksort ทำส่วนเมื่อมัธยฐานโครงร่างที่สามจะใช้ตัดสินใจมือเรียงลำดับองค์ประกอบสาระสำคัญและอาร์เรย์ มี 14 องค์ประกอบ ของเราวิธีให้ speedup การเฉลี่ยของ > 9% เมื่อเทียบกับวิธีการ ด้วยการตัดของ IO และอาร์เรย์ย่อยชุดด้วย < IO แทรกองค์ประกอบที่เรียงลำดับสำหรับ 1000 < N < 1.5 x IO " การศึกษาของเราแสดงให้เห็นว่าขั้นสูงคุณลักษณะของฮาร์ดแวร์อนุญาตให้ใช้รหัสอย่างรวดเร็วสำหรับอาร์เรย์ขนาดเล็ก และ usmg ดังกล่าวรหัสแทนการเรียงลำดับแบบแทรกสามารถนำไปปรับปรุงที่พบสำหรับ Quicksort เป็น conjectured โดยSedgewick หลายปีที่ผ่านมา ลิขสิทธิ์ Q 1996 Elsevier วิทยาศาสตร์ จำกัด

ผลลัพธ์ (ไทย) 2:

Abstract- ~ กระดาษ -This
อธิบายถึงผลการศึกษาเชิงประจักษ์ที่มีขนาดใหญ่ในการวัดพฤติกรรมเวลาทำงานของการจัดเรียงอย่างรวดเร็วโดยใช้วิธีการต่างๆของคอมพิวเตอร์องค์ประกอบหมุนสำหรับสื่อเพื่อพ่อใหญ่สุ่มสร้างข้อมูลจำนวนเต็ม
ผลที่ได้จากการศึกษาของเราขัดแย้งกับความคิดร่วมกันว่าการจัดเรียงที่ดีที่สุดได้อย่างรวดเร็วจะช่วยให้ประสิทธิภาพการทำงานถ้าเฉลี่ยของสามโครงการที่จะใช้ในการคำนวณองค์ประกอบหมุนและพาร์ทิชันที่มีอาร์เรย์<องค์ประกอบ IO จะถูกจัดเรียงโดยใช้การจัดเรียงแทรก มันก็พบว่า Quicksort ดำเนินการที่ดีที่สุดเมื่อเฉลี่ยในสามของโครงการจะใช้ในการตัดสินใจองค์ประกอบหมุนอาร์เรย์และ14 องค์ประกอบเป็นมือเรียง ของเราวิธีการให้เพิ่มความเร็วเฉลี่ยของ> 9% เมื่อเทียบกับวิธีการที่มีการตัดของ IO และอาร์เรย์ย่อยด้วย<แทรกองค์ประกอบ IO เรียง 1000 <ไม่มี <1.5 x IO " การศึกษาของเราแสดงให้เห็นว่าขั้นสูงคุณสมบัติของฮาร์ดแวร์อนุญาตให้มีการดำเนินงานของรหัสอย่างรวดเร็วสำหรับการเรียงลำดับอาร์เรย์ขนาดเล็ก และ usmg เช่นรหัสแทนการจัดเรียงแทรกสามารถนำไปสู่การปรับปรุงที่สำคัญสำหรับQuicksort ขณะที่คาดคะเนโดยเซดจ์วิกหลายปีที่ผ่านมา ลิขสิทธิ์ Q 1996 เอลส์ จำกัด วิทยาศาสตร์

ผลลัพธ์ (ไทย) 3:

นามธรรม - ~ - บทความนี้อธิบายผลของการศึกษาเชิงประจักษ์เพื่อวัดความเร็วขนาดใหญ่พฤติกรรม
รวดเร็วเรียงโดยใช้วิธีการต่างๆของคอมพิวเตอร์หมุนองค์ประกอบสำหรับปานกลางถึงมากขอรับ
สร้างจำนวนเต็มแบบสุ่มข้อมูล ผลการศึกษาของเราขัดแย้งกับความคิดทั่วไปที่เรียงให้เร็วที่สุด
ประสิทธิภาพถ้า median สามโครงการถูกใช้เพื่อคำนวณหมุนองค์ประกอบและพาร์ทิชันที่เรย์มี
< IO องค์ประกอบเรียงโดยใช้การแทรกการจัดเรียง พบว่า มีประสิทธิภาพดีที่สุดเมื่อควิกซอร์ตมัธยฐาน
3 โครงการใช้ตัดสินใจหมุนองค์ประกอบและอาร์เรย์กับ 14 องค์ประกอบ มือเรียงลําดับ วิธีของเรา
ให้ SpeedUp เฉลี่ย > 9 % เมื่อเทียบกับวิธีการของ IO และ
ตัดยอดอาร์เรย์ย่อยด้วย < IO องค์ประกอบแทรกเรียง 1000 < N < 1.5 x IO " การศึกษาของเราแสดงให้เห็นว่าคุณสมบัติ
ฮาร์ดแวร์ขั้นสูงให้ใช้รหัสที่รวดเร็วมากสำหรับการเรียงลำดับอาเรย์ขนาดเล็ก และ usmg รหัสเช่น
แทนการเรียงลำดับแบบแทรกสามารถนำไปสู่การปรับปรุงอย่างมากสำหรับควิกซอร์ต . เป็น conjectured โดย
เซดจ์วิค เมื่อหลายปีก่อน ลิขสิทธิ์ Q 1996 Elsevier Science จำกัด