ความซับซ้อนของเวลาในการเรียงลำดับการแทรก

พิจารณาตัวเลขต่อไปนี้:

50 60 30 10 80 70 20 40

หากเรียงตามลำดับจากน้อยไปมาก จะเป็นดังนี้

10 20 30 40 50 60 70 80

ถ้าเรียงจากมากไปน้อยจะเป็นดังนี้

80 70 60 50 40 30 20 10

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

อัลกอริทึมสำหรับการเรียงลำดับการแทรก

รายการที่ไม่ได้เรียงลำดับจะได้รับ จุดมุ่งหมายคือการเรียงลำดับรายการจากน้อยไปมากโดยใช้รายการเดียวกัน การเรียงลำดับอาร์เรย์ที่ไม่เรียงลำดับโดยใช้อาร์เรย์เดียวกันเรียกว่าการเรียงลำดับแบบแทนที่ ที่นี่ใช้การจัดทำดัชนีแบบอิงศูนย์ ขั้นตอนมีดังนี้:

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

ภาพประกอบการจัดเรียงการแทรก

เมื่อต้องรับมือกับความซับซ้อนของเวลา เป็นกรณีที่เลวร้ายที่สุดที่ปกติจะนำมาพิจารณา การจัดเรียงที่แย่ที่สุดสำหรับรายการก่อนหน้าคือ:

80 70 60 50 40 30 20 10

มีแปดองค์ประกอบที่มีดัชนีตั้งแต่ศูนย์ถึง 7

ที่ดัชนีศูนย์ การสแกนไปที่ 80 นี่เป็นการเคลื่อนไหวครั้งเดียว หนึ่งการเคลื่อนไหวนี้เป็นการดำเนินการ จนถึงปัจจุบันมีการดำเนินการทั้งหมด 1 ครั้ง (การเคลื่อนไหวหนึ่งครั้ง ไม่มีการเปรียบเทียบ และไม่มีการสลับ) ผลลัพธ์คือ:

| 80 70 60 50 40 30 20 10

ที่ดัชนี 1 มีการเคลื่อนไหวที่ 70 70 เปรียบเทียบกับ 80 70 และ 80 ถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบอย่างหนึ่งก็เป็นการดำเนินการอย่างหนึ่งเช่นกัน การสลับหนึ่งครั้งก็เป็นการดำเนินการเดียวเช่นกัน ส่วนนี้ประกอบด้วยการดำเนินการสามอย่าง มีการดำเนินการทั้งหมดสี่ครั้ง (1 + 3 = 4) ผลลัพธ์จะเป็นดังนี้:

70 | 80 60 50 40 30 20 10

ที่ดัชนีที่สอง มีการเคลื่อนไหวไปที่ 60 60 เปรียบเทียบกับ 80 จากนั้น 60 และ 80 จะถูกสลับ 60 เปรียบเทียบกับ 70 จากนั้น 60 และ 70 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบสองอย่างคือการดำเนินการสองอย่าง การแลกเปลี่ยนสองครั้งคือการดำเนินการสองครั้ง ส่วนนี้ประกอบด้วยการดำเนินการห้าประการ มีการดำเนินการทั้งหมดเก้าครั้ง (4 + 5 = 9) ผลลัพธ์จะเป็นดังนี้:

60 70 | 80 50 40 30 20 10

ที่ดัชนีสาม มีการเคลื่อนไหวที่ 50 50 เปรียบเทียบกับ 80 จากนั้น 50 และ 80 จะถูกสลับ 50 เปรียบเทียบกับ 70 จากนั้น 50 และ 70 จะถูกสลับ 50 ถูกเปรียบเทียบกับ 60 จากนั้น 50 และ 60 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบสามอย่างคือการดำเนินการสามอย่าง สามสวอปคือการดำเนินการสามอย่าง ส่วนนี้ประกอบด้วยการดำเนินการเจ็ดประการ มีการดำเนินการทั้งหมดสิบหกครั้ง (9 + 7 = 16) ผลลัพธ์จะเป็นดังนี้:

50 60 70 | 80 40 30 20 10

ที่ดัชนีสี่ มีการเคลื่อนไหวที่ 40 40 เปรียบเทียบกับ 80 จากนั้น 40 และ 80 จะถูกสลับ 40 ถูกเปรียบเทียบกับ 70 จากนั้น 40 และ 70 จะถูกสลับ 40 ถูกเปรียบเทียบกับ 60 จากนั้น 40 และ 60 จะถูกสลับ 40 ถูกเปรียบเทียบกับ 50 จากนั้น 40 และ 50 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบสี่ประการคือการดำเนินการสี่ประการ สี่สวอปคือการดำเนินการสี่อย่าง ส่วนนี้ประกอบด้วยการดำเนินการเก้ารายการ มีการดำเนินการทั้งหมด 25 รายการ (16 + 9 = 25) ผลลัพธ์จะเป็นดังนี้:

40 50 60 70 80 | 30 20 10

ที่ดัชนีห้า มีการเคลื่อนไหวไปที่ 30 30 เปรียบเทียบกับ 80 จากนั้น 30 และ 80 จะถูกสลับ 30 เปรียบเทียบกับ 70 จากนั้น 30 และ 70 จะถูกสลับ 30 เปรียบเทียบกับ 60 จากนั้น 30 และ 60 จะถูกสลับ 30 เปรียบเทียบกับ 50 จากนั้น 30 และ 50 จะถูกสลับ 30 เปรียบเทียบกับ 40 จากนั้น 30 และ 40 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบห้ารายการคือการดำเนินการห้ารายการ การแลกเปลี่ยนห้าครั้งคือการดำเนินการห้าครั้ง ส่วนนี้ประกอบด้วยการดำเนินการสิบเอ็ดรายการ มีการดำเนินการทั้งหมด 36 รายการ (25 + 11 = 36) ผลลัพธ์จะเป็นดังนี้:

30 40 50 60 70 80 | 20 10

ที่ดัชนีหก มีการเคลื่อนไหวไปที่ 20 20 เปรียบเทียบกับ 80 จากนั้น 20 และ 80 จะถูกสลับ 20 ถูกเปรียบเทียบกับ 70 จากนั้น 20 และ 70 จะถูกสลับ 20 ถูกเปรียบเทียบกับ 60 จากนั้น 20 และ 60 จะถูกสลับ 20 ถูกเปรียบเทียบกับ 50 จากนั้น 20 และ 50 จะถูกสลับ 20 ถูกเปรียบเทียบกับ 40 จากนั้น 20 และ 40 จะถูกสลับ 20 ถูกเปรียบเทียบกับ 30 จากนั้น 20 และ 30 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบหกประการคือการดำเนินการหกครั้ง การแลกเปลี่ยนหกครั้งคือการดำเนินการหกครั้ง ส่วนนี้ประกอบด้วยการดำเนินการสิบสามรายการ มีการดำเนินการทั้งหมดสี่สิบเก้าครั้ง (36 + 13 = 49) ผลลัพธ์จะเป็นดังนี้:

20 30 40 50 60 70 80 | 10

ที่ดัชนีเจ็ด มีการเคลื่อนไหวที่ 10 10 เปรียบเทียบกับ 80 จากนั้น 10 และ 80 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 70 จากนั้น 10 และ 70 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 60 จากนั้น 10 และ 60 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 50 จากนั้น 10 และ 50 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 30 จากนั้น 10 และ 40 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 30 จากนั้น 10 และ 30 จะถูกสลับ 10 ถูกเปรียบเทียบกับ 20 จากนั้น 10 และ 20 จะถูกสลับ หนึ่งการเคลื่อนไหวคือหนึ่งการดำเนินการ การเปรียบเทียบเจ็ดรายการคือการดำเนินการเจ็ดรายการ การแลกเปลี่ยนเจ็ดครั้งคือการดำเนินการเจ็ดครั้ง ส่วนนี้ประกอบด้วยการดำเนินการสิบห้ารายการ มีการดำเนินการทั้งหมดหกสิบสี่ครั้ง (49 + 15 = 64) ผลลัพธ์จะเป็นดังนี้:

10 20 30 40 50 60 70 80 10 |

งานเสร็จแล้ว! มีการดำเนินการ 64 รายการที่เกี่ยวข้อง

64 = 8 x 8 = 8 ^สอง

ความซับซ้อนของเวลาสำหรับการเรียงลำดับการแทรก

หากมีองค์ประกอบ n รายการที่จะจัดเรียงด้วยการเรียงลำดับการแทรก จำนวนสูงสุดของการดำเนินการที่เป็นไปได้จะเป็น n2 ดังที่แสดงไว้ก่อนหน้านี้ ความซับซ้อนของเวลาในการจัดเรียงการแทรกคือ:

บน ^สอง )

สิ่งนี้ใช้สัญกรณ์ Big-O สัญกรณ์ Big-O เริ่มต้นด้วย O เป็นตัวพิมพ์ใหญ่ ตามด้วยวงเล็บ ภายในวงเล็บคือนิพจน์สำหรับจำนวนการดำเนินการสูงสุดที่เป็นไปได้

การเข้ารหัสในC

ในช่วงเริ่มต้นของการสแกน องค์ประกอบแรกไม่สามารถเปลี่ยนตำแหน่งได้ โปรแกรมเป็นหลักดังต่อไปนี้:

คำจำกัดความของฟังก์ชัน insertionSort() ใช้อัลกอริทึมตามที่อธิบายไว้ สังเกตเงื่อนไขสำหรับ while-loop ฟังก์ชันหลัก C ที่เหมาะสมสำหรับโปรแกรมนี้คือ:

บทสรุป

ความซับซ้อนของเวลาสำหรับการเรียงลำดับการแทรกถูกกำหนดเป็น:

บน ^สอง )

ผู้อ่านอาจเคยได้ยินเกี่ยวกับความซับซ้อนของเวลาที่แย่กว่านั้น ความซับซ้อนของเวลาโดยเฉลี่ยของเคส และความซับซ้อนของเวลาที่ดีที่สุด รูปแบบต่างๆ ของความซับซ้อนของเวลาในการจัดเรียงการแทรกเหล่านี้จะกล่าวถึงในบทความถัดไปในเว็บไซต์ของเรา