ความซับซ้อนของเวลาของการเรียงลำดับการแทรกคืออะไร
ความซับซ้อนของเวลา คือระยะเวลาที่ชุดโค้ดหรืออัลกอริทึมใช้ในการประมวลผลหรือเรียกใช้เป็นฟังก์ชันของจำนวนอินพุต
สำหรับการเรียงลำดับการแทรก ความซับซ้อนของเวลาจะอยู่ในลำดับ O(n) เช่น O ใหญ่ของ n ในสถานการณ์ที่ดีที่สุด และในกรณีเฉลี่ยหรือกรณีที่เลวร้ายที่สุด ความซับซ้อนอยู่ในลำดับ O(n 2 )
เวลาของการเรียงลำดับจะเป็นอย่างไรเมื่ออัลกอริทึมการเรียงลำดับการแทรกถูกนำไปใช้กับอาร์เรย์ขนาด n ของรูปแบบต่อไปนี้:6, 5, 8, 7, 10, 9 …… I, i-1
ความซับซ้อนของเวลาของการจัดเรียงรูปแบบอาร์เรย์ด้านบนคือ O(n) มาดูอัลกอริธึมนี้กันอย่างระมัดระวัง โดยที่คู่ทั้งหมดจะถูกสลับจากตำแหน่งเดิม กล่าวคือ ตำแหน่งขององค์ประกอบ 1 และองค์ประกอบ 2 มีการแลกเปลี่ยนกัน 3 และ 4 มีการแลกเปลี่ยนกัน เป็นต้น ดังนั้น ในขณะที่การเรียงลำดับอัลกอริธึมจะใช้เวลาดำเนินการเพียงครั้งเดียว n ครั้งเพื่อจัดเรียงอัลกอริธึมนี้
กำหนดประเภทการแทรกและเขียนโค้ดสำหรับการจัดเรียงการแทรกหรือไม่
การเรียงลำดับการแทรกคืออัลกอริธึมการเรียงลำดับที่จัดเรียงโครงสร้างข้อมูลโดยการวางองค์ประกอบที่ตำแหน่งในอาร์เรย์ที่จัดเรียง
รหัสด้านล่างแสดงฟังก์ชันสำหรับการเรียงลำดับการแทรก -
ตัวอย่าง
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++){
int element = arr[i];
int j = i-1;
while (j >= 0 && arr[j] > element){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = element;
}
} 