3 Experimental setupIn the remainde

3 Experimental setup
In the remainder of this paper, we investigate whether
classic, theoretically non-adaptive sorting algorithms
can show adaptive behavior in practice. We nd that
this indeed is the case|the running times for Quick-
sort, Mergesort, and Heapsort are observed to improve
by factors between 1.5 and 3.5 when the Inv value of
the input goes from high to low. Furthermore, the im-
provements for Quicksort are in very good concordance
with Theorem 1.1, which shows this result to be a likely
explanation for the observed behavior.
In more detail, we study how the number of in-
versions in the input sequence aects the number of
comparisons, the number of element swaps, the num-
ber of branch mispredictions, the running time, and the
number of data cache misses of the version of Quicksort
shown in Figure 1. We also study the behavior of two
variants of Quicksort, namely the randomized version
that chooses the median of three random elements as
a pivot, and the deterministic version that chooses the
middle element as a pivot. Finally, we study the same
questions for the classic sorting algorithms Heapsort and
Mergesort.
The input elements are 4 byte integers. We generate
two types of input, having small di's and large di's,
respectively. We generate a sequence with small di's by
choosing each element xi randomly in [i

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

ตั้งค่าการทดลอง 3ในส่วนที่เหลือของเอกสารนี้ เราตรวจสอบว่าคลาสสิก ตามหลักวิชาไม่ใช่ปรับอัลกอริทึมการเรียงลำดับสามารถแสดงพฤติกรรมที่เหมาะสมในทางปฏิบัติ เรา nd ที่นี่คือ case|the ที่ทำงานเวลารวดเร็ว - แน่นอนเรียงลำดับ Mergesort และ Heapsort พบการปรับปรุงสาเหตุระหว่าง 1.5 และ 3.5 เมื่อค่า Invการป้อนข้อมูลไปจากสูงไปต่ำ นอกจากนี้ im -provements สำหรับ Quicksort อยู่ในสอดคล้องดีมากมีทฤษฎีบท 1.1 แสดงผลลัพธ์นี้จะ เป็นแนวโน้มอธิบายลักษณะการทำงานที่สังเกตรายละเอียดเพิ่มเติม เราศึกษาวิธีจำนวนในรุ่นในการป้อนข้อมูลหมายเลขของ ects เป็นลำดับเปรียบเทียบ หมายเลของค์ประกอบ swaps, num-เบอร์ของสาขา mispredictions เวลาทำงาน และจำนวนข้อมูลแคพุ่งรุ่น Quicksortแสดงในรูปที่ 1 นอกจากนี้เรายังศึกษาพฤติกรรมของสองย่อย Quicksort คือรุ่น randomizedที่เลือกมัธยฐานขององค์ประกอบเป็นแบบสุ่มมีสาระสำคัญ และรุ่น deterministic ที่เลือกองค์กลางเป็นสาระสำคัญ สุดท้าย เราเรียนเดียวกันคำถามสำหรับคลาสสิกเรียงอัลกอริทึม Heapsort และMergesortองค์ประกอบสำหรับการป้อนค่าเป็นจำนวนเต็ม 4 ไบต์ เราสร้างสองชนิดค่านำเข้า มีดีขนาดเล็กและขนาดใหญ่ไดตามลำดับ เราสร้างลำดับที่ มีขนาดเล็กไดโดยเลือกสิแต่ละองค์ประกอบในแบบสุ่ม [i