Proof. In discussed version, algori

Proof. In discussed version, algorithm to re-arranging elements in a triple heap
is performed in a loop from i = 0 to i = n − 2. Algorithm to create triple
heap is proceeded n − 1 times. Theorem 1 indicates that height of triple heap
is ⌊log3 n⌋ + 1 and Theorem 2 indicates that time to re-arrange triple heap is
C · n. Algorithm proceeds sorting n−1 times, therefore time complexity can be
estimated as
# (n) = C · (n − 1) · (⌊log3 n⌋ + 1) . (23)
Considering large scale data sets of n elements we can estimate (23) as
# (n) ∼=
C · n · log3 n. (24)
⊓⊔
2.3 Results of examinations
Theoretical analysis of examined versions shows that to find the maximum between
3 elements we compare elements 2 times. Similarly, to find maximum
between 4 elements we compare elements 3 times. Thus, comparing sort times
using double heap sorting to triple heap sorting we estimate potential difference
between those two methods, which is 2·n log2 n
3·n log3 n = 2 log 3
3 log 2 ≈ 1.0566. Therefore proposed
in Section 2 triple heap sort algorithm should be theoretically 5% more
effective. To verify this conclusion we have compared results of numerical experiments.
Described algorithm was examined for large scale data sets. Algorithm
was implemented using CLR C++ in MS Visual Studio 2010 Ultimate. To test
were taken random samples of 100 series in each class of frequencies, including
unfavorable positioning. Tests were carried out on quad core amd opteron processor
8356 8p. Research results were plotted in Fig.2 and Fig.3. The speed of
performed operations depends on the initial arrangement of the input data. It
is also affected by the number of changes made at a constant number of comparisons.
The aim of the analysis and comparison is to verify if the extended
triple heap is really better to sort large data sets than the classic version. In the
examinations and tests were compared the characteristics of the proposed algorithm
with the classic version. The analysis of Fig.2 shows that the proposed
algorithm behaves similarly to the classic version. In the interval to 1000000
elements, proposed in Section 2 algorithm can increase the stability of sorting
procedure. The values of the coefficients of variation are presented in Table 1.
Coefficients of variation were plotted with polynomial approximation, which is
shown in Fig.3. The resulting curves characterize potential variability of the examined
versions. Analysis of Fig.3 shows that the greatest variation of stability
of the classic version occurs in the area of 1000000 elements. The version that
uses triple heap has a better stability, understood as the repeatability of the
achieved results. Therefore, the application of the heap with extended structure
has a positive effect on sorting. Illustration of the difference between the two examined
versions of the algorithm is shown in Fig.3. As the reference method was
taken classic algorithm. The analysis and comparison of charts in Fig.3 shows

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

หลักฐานการ ในการกล่าวถึงรุ่น อัลกอริทึมการจัดเรียงองค์ประกอบในกองที่สามอีกครั้งในวนจากฉัน = 0 เพื่อฉัน = n − 2 อัลกอริทึมการสร้างทริปเปิ้ลกองเป็นครอบครัว n − 1 ครั้ง ทฤษฎีบท 1 บ่งชี้ว่า ความสูงของสามกองเป็น ⌊log3 n⌋ + 1 และ 2 ทฤษฎีบทระบุเวลาที่การจัดเรียงใหม่เป็นสามกองC · n. ดำเนินอัลกอริทึมการเรียงลำดับเวลา n−1 ดังนั้นความซับซ้อนของเวลาได้ประเมินเป็น# (n) = C · (n − 1) · (⌊log3 n⌋ + 1) (23)พิจารณาชุดข้อมูลขนาดใหญ่ขององค์ประกอบ n เราสามารถประเมินเป็น (23)# (n) ∼=C · n · n. log3 (24)⊓⊔2.3 ผลการตรวจสอบวิเคราะห์ทฤษฎีกล่าวถึงรุ่นแสดงที่พบสูงสุดระหว่างองค์ประกอบ 3 ที่เราเปรียบเทียบองค์ประกอบ 2 ครั้ง ในทำนองเดียวกัน การค้นหาสูงสุดระหว่างองค์ประกอบที่ 4 เราเปรียบเทียบองค์ประกอบครั้งที่ 3 ดังนั้น เปรียบเทียบเรียงลำดับเวลาใช้กองคู่เรียงสามกองเรียงลำดับเราประเมินความต่างศักย์ระหว่างวิธีทั้งสองเหล่านั้น ซึ่งเป็น 2·n log2 n3·n log3 n = 2 ล็อก 3ล็อก 3 2 ≈ 1.0566 ดังนั้น การนำเสนอส่วน 2 อัลกอริทึมการเรียงลำดับสามกองควรครั้งแรกราคา 5% เพิ่มเติมมีผลบังคับใช้ การตรวจสอบบทสรุปนี้เราได้เปรียบเทียบผลการทดลองเป็นตัวเลขอธิบายขั้นตอนวิธีการตรวจสอบสำหรับชุดข้อมูลขนาดใหญ่ อัลกอริทึมได้ดำเนินการโดยใช้ c ++ CLR ใน MS Visual Studio 2010 สุดยอด ในการทดสอบได้รับตัวอย่างที่สุ่มของ 100 ชุดแต่ละชั้นความถี่ รวมทั้งตำแหน่งร้าย ทดสอบได้ดำเนินการบนมีแกน amd opteron โปรเซสเซอร์8356 8p ผลการวิจัยถูกพล็อตใน Fig.2 Fig.3 ความเร็วของการดำเนินการดำเนินการขึ้นอยู่กับการจัดเรียงเริ่มต้นของข้อมูลที่ป้อนเข้า มันนอกจากนี้ยังเป็นผลกระทบตามจำนวนแปลงที่คงเปรียบเทียบจุดมุ่งหมายของการวิเคราะห์และเปรียบเทียบคือการ ตรวจสอบถ้าที่ขยายสามกองอยู่จริง ๆ ให้เรียงลำดับชุดข้อมูลขนาดใหญ่กว่ารุ่นคลาสสิก ในตรวจสอบและทดสอบได้เปรียบเทียบลักษณะของขั้นตอนวิธีนำเสนอรุ่นคลาสสิค การวิเคราะห์ของ Fig.2 แสดงให้เห็นว่าการนำเสนออัลกอริทึมทำงานเหมือนกับรุ่นคลาสสิก ในช่วง 1000000องค์ประกอบ การนำเสนอใน 2 ส่วนอัลกอริทึมสามารถเพิ่มเสถียรภาพของการเรียงลำดับขั้นตอนการ ค่าของสัมประสิทธิ์ความผันแปรจะแสดงในตารางที่ 1สัมประสิทธิ์ความผันแปรถูกพล็อตกับประมาณพหุนาม ซึ่งเป็นแสดงใน Fig.3 ความแปรผันที่เป็นไปได้ของการกล่าวถึงลักษณะของเส้นโค้งได้รุ่น วิเคราะห์ Fig.3 แสดงให้เห็นว่าการเปลี่ยนแปลงที่ยิ่งใหญ่ที่สุดของความมั่นคงรุ่นคลาสสิคเกิดขึ้นในพื้นที่ขององค์ประกอบที่ 1000000 รุ่นที่ใช้สามกองมีเสถียรภาพดี เข้าใจว่าเป็นการทำซ้ำในของสำเร็จผล ดังนั้น ไม่ใช้กองมีโครงสร้างแบบขยายมีผลดีต่อการเรียงลำดับ ภาพแสดงความแตกต่างระหว่างสองที่ตรวจสอบรุ่นของอัลกอริทึมจะแสดงใน Fig.3 เป็นวิธีการอ้างอิงนำอัลกอริทึมที่คลาสสิก การวิเคราะห์และเปรียบเทียบแผนภูมิใน Fig.3 แสดง

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

หลักฐาน ในรุ่นที่กล่าวถึงอัลกอริทึมที่จะกลับมาจัดองค์ประกอบในกองสาม
จะดำเนินการในวงจาก i = 0 ถึง i = n - 2 อัลกอริทึมในการสร้างสาม
กองจะดำเนินการ n - 1 ครั้ง ทฤษฎีบท 1 แสดงให้เห็นความสูงของกองสามที่
เป็น⌊log3n⌋ + 1 และทฤษฏี 2 แสดงให้เห็นว่าเวลาที่จะกลับมาจัดกองสามเป็น
c · n อัลกอริทึมการเรียงลำดับรายได้ n-1 ครั้งจึงซับซ้อนเวลาสามารถ
ประมาณเป็น
# (n) = C · (n - 1) · (⌊log3n⌋ + 1) (23)
เมื่อพิจารณาขนาดใหญ่ชุดข้อมูลขององค์ประกอบ n เราสามารถประมาณ (23) เป็น
# (n) ~ =
c ·· log3 n n (24)
⊓⊔
2.3 ผลการตรวจ
วิเคราะห์ตามทฤษฎีของรุ่นการตรวจสอบแสดงให้เห็นว่าในการค้นหาสูงสุดระหว่าง
3 องค์ประกอบเราเปรียบเทียบองค์ประกอบ 2 ครั้ง ในทำนองเดียวกันในการค้นหาสูงสุด
ระหว่างวันที่ 4 องค์ประกอบเราเปรียบเทียบองค์ประกอบ 3 ครั้ง ดังนั้นการเปรียบเทียบครั้งการเรียงลำดับ
โดยใช้กองสองกองเรียงลำดับการเรียงลำดับสามที่เราได้ประมาณการความแตกต่างที่อาจเกิดขึ้น
ระหว่างทั้งสองวิธีการซึ่งเป็น 2 · n log2 n
3 · n log3 n = 2 บันทึก 3
ล็อก 3 2 ≈ 1.0566 จึงเสนอ
ในส่วนขั้นตอนวิธีการจัดเรียง 2 กองสามควรจะเป็นทฤษฎี 5%
ที่มีประสิทธิภาพ เพื่อตรวจสอบข้อสรุปนี้เราได้เปรียบเทียบผลของการทดลองที่เป็นตัวเลข
ขั้นตอนวิธีอธิบายถูกตรวจสอบสำหรับขนาดใหญ่ชุดข้อมูล อัลกอริทึม
ถูกนำมาใช้โดยใช้ CLR C ++ ใน MS Visual Studio 2010 สุดยอด ในการทดสอบ
ถูกนำตัวอย่างแบบสุ่มของ 100 ชุดในชั้นเรียนของความถี่แต่ละครั้งรวมถึง
การวางตำแหน่งที่ไม่เอื้ออำนวย การทดสอบได้ดำเนินการเกี่ยวกับการประมวลผลแกนรูปสี่เหลี่ยม AMD Opteron
8356 8p ผลการวิจัยลงจุดในรูปที่ 2 และรูปที่ 3 ความเร็วของ
การดำเนินการดำเนินการขึ้นอยู่กับการจัดเริ่มต้นของการป้อนข้อมูล มัน
เป็นผลกระทบจากจำนวนของการเปลี่ยนแปลงที่ทำในจำนวนคงที่ของการเปรียบเทียบ
จุดมุ่งหมายของการวิเคราะห์และการเปรียบเทียบคือการตรวจสอบว่าการขยาย
กองสามเป็นจริงดีกว่าที่จะค้นหาชุดข้อมูลขนาดใหญ่กว่ารุ่นคลาสสิก ใน
การตรวจสอบและการทดสอบเปรียบเทียบลักษณะของอัลกอริทึมที่นำเสนอ
ด้วยรุ่นคลาสสิก การวิเคราะห์รูปที่ 2 แสดงให้เห็นว่าการเสนอ
ขั้นตอนวิธีการทำงานคล้าย ๆ กับรุ่นคลาสสิก ในช่วงเวลาที่ 1000000
องค์ประกอบที่นำเสนอในส่วนที่ 2 อัลกอริทึมสามารถเพิ่มเสถียรภาพของการเรียงลำดับ
ขั้นตอน ค่าสัมประสิทธิ์ของการเปลี่ยนแปลงดังกล่าวได้แสดงในตารางที่ 1
ค่าสัมประสิทธิ์ของการเปลี่ยนแปลงที่ถูกพล็อตที่มีการประมาณพหุนามซึ่งเป็น
ที่แสดงในรูปที่ 3 เส้นโค้งที่เกิดลักษณะความแปรปรวนที่อาจเกิดขึ้นจากการตรวจสอบ
รุ่น การวิเคราะห์รูปที่ 3 แสดงให้เห็นว่าการเปลี่ยนแปลงที่ยิ่งใหญ่ที่สุดของความมีเสถียรภาพ
ของรุ่นคลาสสิกเกิดขึ้นในพื้นที่ของ 1000000 องค์ประกอบ รุ่นที่
ใช้กองสามมีเสถียรภาพที่ดีขึ้นเข้าใจว่าการทำซ้ำของ
ผลการประสบความสำเร็จ ดังนั้นการใช้งานของกองที่มีโครงสร้างขยาย
มีผลกระทบเชิงบวกต่อการเรียงลำดับ ภาพของความแตกต่างระหว่างทั้งสองการตรวจสอบ
รุ่นของอัลกอริทึมที่มีการแสดงในรูปที่ 3 เป็นวิธีการอ้างอิงได้รับการ
ดำเนินการขั้นตอนวิธีคลาสสิก การวิเคราะห์และการเปรียบเทียบของแผนภูมิในรูปที่ 3 แสดงให้เห็นว่า

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

พิสูจน์ ในการกล่าวถึงรุ่น , ขั้นตอนวิธีการจัดองค์ประกอบใหม่ในสามกอง
จะดําเนินการในเป็นวงจากฉัน = 0 = n − 2 ขั้นตอนวิธีการสร้างสามกองคือการ− 1
n ครั้ง ทฤษฎีบทที่ 1 พบว่า ความสูงของสามกอง
เป็น⌊ log3 N ⌋ 1 และ 2 บ่งบอกเวลาว่าทฤษฎีบทอีกครั้ง จัดเป็นสามกองด้วยขั้นตอนวิธีการเรียงลำดับ ( C .
n − 1 ครั้ง ดังนั้นความซับซ้อนด้านเวลา สามารถ
ประเมินเป็น
# ( n ) = C ด้วย ( − 1 ) ด้วย ( ⌊ log3 N ⌋ 1 ) ( 23 )
พิจารณาชุดข้อมูลขนาดใหญ่ขององค์ประกอบเราสามารถประเมิน ( 23 )
# ( N ) ∼ =
C ด้วย N ด้วย log3 . ( 24 )


⊓⊔ 2.3 ผลสอบทฤษฎีการวิเคราะห์ตรวจสอบรุ่น แสดงให้เห็นว่าการค้นหาสูงสุดระหว่าง
3 องค์ประกอบเราเปรียบเทียบองค์ประกอบ 2 ครั้ง . ในทำนองเดียวกันพบสูงสุด
4 องค์ประกอบเราเปรียบเทียบองค์ประกอบ 3 ครั้ง ดังนั้นเปรียบเทียบการจัดเรียงครั้ง
ใช้คู่กองเรียงไปสามกองเรียงเราประเมินศักยภาพระหว่างสองวิธีการ
ความแตกต่าง ซึ่งเป็น 2 ด้วย N LN N
3 N log3 ด้วย n = 2
3 ล็อก 3 ล็อก 2 ≈ 1.0566 . จึงได้เสนอ
ในส่วน 2 สามกองเรียงขั้นตอนควรตามหลักวิชา 5 %
ที่มีประสิทธิภาพ เพื่อยืนยันข้อสรุปนี้เราได้เทียบผลของการทดลองเชิงตัวเลข .
อธิบายขั้นตอนวิธีการตรวจสอบสำหรับชุดข้อมูลที่มีขนาดใหญ่ขนาด ขั้นตอนวิธี
ใช้ใช้ CLR C ใน MS Visual Studio 2010 ultimate ทดสอบ
ถ่ายจำนวน 100 ชุดในแต่ละชั้นเรียนของความถี่ รวมทั้ง
ตำแหน่งร้าย ทดสอบจาก AMD Opteron โปรเซสเซอร์ quad core
8356 8p . การวิจัยและวางแผนใน fig.2 fig.3 . ความเร็วของ
ผ่าตัดขึ้นอยู่กับการเริ่มต้นของข้อมูลเริ่มต้น มัน
ยังได้รับผลกระทบจากจำนวนของการเปลี่ยนแปลงที่เป็นจำนวนคงที่ของการเปรียบเทียบ
จุดมุ่งหมายของการวิเคราะห์และการเปรียบเทียบการตรวจสอบหากขยาย
สามกองเป็นดีกว่าที่จะเรียงลำดับชุดข้อมูลขนาดใหญ่กว่ารุ่นคลาสสิก ในการสอบและการทดสอบ
เปรียบเทียบลักษณะของวิธีที่เสนอ
กับรุ่นคลาสสิก การวิเคราะห์ fig.2 แสดงขั้นตอนวิธีที่เสนอ
ประพฤติตัวคล้ายกับรุ่นคลาสสิก ในช่วงการ 1000000
องค์ประกอบการนำเสนอในส่วนที่ 2 นี้สามารถเพิ่มความมั่นคงของ
ขั้นตอนการเรียงลำดับ ค่าของสัมประสิทธิ์การแปรผันจะแสดงในตารางที่ 1 .
สัมประสิทธิ์การแปรผันกำลังวางแผนกับการประมาณพหุนามซึ่ง
แสดงใน fig.3 . ลักษณะของเส้นโค้งที่มีศักยภาพของการตรวจสอบ
รุ่น การวิเคราะห์ fig.3 แสดงให้เห็นว่ารูปแบบมากที่สุดของความมั่นคง
ของรุ่นคลาสสิกเกิดขึ้นในพื้นที่ของ 1000000 องค์ประกอบ รุ่นที่
ใช้สามกองมีความมั่นคงดี เข้าใจเป็นกาลของ
สําเร็จผล ดังนั้นการประยุกต์ใช้กองไว้
โครงสร้างขยายมีผลเป็นบวกในการเรียงลำดับ ภาพประกอบของความแตกต่างระหว่างสองตรวจสอบ
รุ่นของขั้นตอนวิธีจะแสดงใน fig.3 . เป็นวิธีมาตรฐานคือ
ถ่ายคลาสสิกอัลกอริทึม การวิเคราะห์และการเปรียบเทียบแผนภูมิใน fig.3 แสดง