DAA - เรียงลำดับการแทรก

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

ตัวเลขที่จำเป็นในการจัดเรียงเรียกว่า keys. นี่คืออัลกอริทึมของวิธีการเรียงลำดับการแทรก

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

การวิเคราะห์

เวลาทำงานของอัลกอริทึมนี้ขึ้นอยู่กับอินพุตที่กำหนดเป็นอย่างมาก

หากเรียงลำดับตัวเลขที่ระบุอัลกอริทึมนี้จะทำงานใน O(n)เวลา. หากตัวเลขที่ระบุอยู่ในลำดับย้อนกลับอัลกอริทึมจะทำงานO(n²) เวลา.

ตัวอย่าง

Unsorted list:

2 13 5 18 14

1^st iteration:

คีย์ = a [2] = 13

ก [1] = 2 <13

Swap ไม่มีการแลกเปลี่ยน

2 13 5 18 14

2^nd iteration:

คีย์ = a [3] = 5

ก [2] = 13> 5

สลับ 5 และ 13

2 5 13 18 14

ถัดไป a [1] = 2 <13

Swap ไม่มีการแลกเปลี่ยน

2 5 13 18 14

3^rd iteration:

คีย์ = a [4] = 18

ก [3] = 13 <18,

ก [2] = 5 <18,

ก [1] = 2 <18

Swap ไม่มีการแลกเปลี่ยน

2 5 13 18 14

4^th iteration:

คีย์ = a [5] = 14

ก [4] = 18> 14

สลับ 18 และ 14

2 5 13 14 18

ถัดไป a [3] = 13 <14,

ก [2] = 5 <14,

ก [1] = 2 <14

ดังนั้นไม่มีการแลกเปลี่ยน

2 5 13 14 18

สุดท้าย

the sorted list is

2 5 13 14 18