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

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

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





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



ค่าที่สามจะถูกเปรียบเทียบกับอีกสองค่าที่เหลือ จากนั้นจึงใส่ลงในดัชนีที่ถูกต้อง กระบวนการนี้จะดำเนินต่อไปจนกว่าจะจัดเรียงรายการทั้งหมด





ดูการเรียงลำดับการแทรกอย่างใกล้ชิด

คำอธิบายข้างต้นอาจไม่สมเหตุสมผลสำหรับคุณ ตัวอย่างควรช่วยให้คุณเข้าใจได้ดีขึ้นมาก

สมมติว่าคุณมีรายการ: [39, 6, 2, 51, 30, 42, 7].



อัลกอริทึมระบุ 39 เป็นค่าแรกของรายการย่อยที่เรียงลำดับ การประเมินจะไปยังตำแหน่งที่สอง

ที่เกี่ยวข้อง: การเขียนโปรแกรมแบบไดนามิก: ตัวอย่าง ปัญหาทั่วไป และวิธีแก้ไข



จากนั้นนำ 6 มาเปรียบเทียบกับ 39 เนื่องจาก 6 น้อยกว่า 39 จึงใส่ 6 ไว้ในตำแหน่งแรกและ 39 อยู่ในตำแหน่งที่สอง ลำดับรายการใหม่อยู่หลังรอบแรกตอนนี้:

[6, 39, 2, 51, 30, 42, 7]



การประเมินตอนนี้เลื่อนไปที่ตำแหน่งที่สาม 2 ถูกเปรียบเทียบกับตัวเลขสองตัวสุดท้ายแล้วแทรกในตำแหน่งที่ถูกต้อง ลำดับรายการใหม่อยู่หลังรอบที่สองตอนนี้:

[2, 6, 39, 51, 30, 42, 7]

สำหรับรอบที่สาม ลำดับรายการคือ:

[2, 6, 39, 51, 30, 42, 7]

กระบวนการจะทำซ้ำจนกว่าจะจัดเรียงรายการทั้งหมด

ดูแผนภาพด้านล่างที่สรุปการดำเนินการเหล่านี้:

การวิเคราะห์อัลกอริทึม

ความซับซ้อนของเวลาของการเรียงลำดับการแทรกคือ O(n2), เหมือนกับ การเรียงลำดับฟอง . จำนวนการเปรียบเทียบในสถานการณ์กรณีที่เลวร้ายที่สุดคือผลรวมของจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง (n-1) โดยให้ผลรวมกำลังสอง

การติดตั้งโค้ด

โค้ด Python และ Java ด้านล่างแสดงวิธีใช้งานวิธีการจัดเรียงการแทรก

หลาม:

def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_element

ชวา:

void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}

การเข้ารหัสที่ดีขึ้นด้วย Pseudocode

ตัวอย่างโค้ดข้างต้นมีให้โดยไม่มีรหัสเทียมใดๆ ที่คุณสามารถอ้างอิงเพื่อเขียนอัลกอริทึมนี้ในภาษาอื่นได้ โปรแกรมเมอร์ส่วนใหญ่ (รวมผู้เขียนด้วย) ชอบวิ่งไปที่คีย์บอร์ดหลังจากได้รับแจ้งว่า 'กระซิบ' เกี่ยวกับวิธีการทำงานของโปรแกรม

น่าเสียดายที่แนวทางนี้มีแนวโน้มที่จะเกิดข้อผิดพลาดเนื่องจากตรรกะของโปรแกรมมีความซับซ้อนมากขึ้น คุณต้องการยกระดับเกมการเขียนโปรแกรมของคุณด้วยการเรียนรู้วิธีการใช้ pseudocode อย่างไร?

แบ่งปัน แบ่งปัน ทวีต อีเมล Pseudocode คืออะไรและทำให้คุณเป็นนักพัฒนาที่ดีขึ้นได้อย่างไร

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

อ่านต่อไป หัวข้อที่เกี่ยวข้อง
  • การเขียนโปรแกรม
  • Java
  • Python
  • บทเรียนการเข้ารหัส
เกี่ยวกับผู้เขียน เจอโรม เดวิดสัน(ตีพิมพ์บทความ 22 บทความ)

เจอโรมเป็นพนักงานเขียนบทที่ MakeUseOf เขาครอบคลุมบทความเกี่ยวกับการเขียนโปรแกรมและลินุกซ์ เขายังเป็นคนที่กระตือรือร้นในการเข้ารหัสและคอยติดตามดูอุตสาหกรรม crypto อยู่เสมอ

mac desktop เปิดไม่ติด
เพิ่มเติมจาก Jerome Davidson

สมัครรับจดหมายข่าวของเรา

เข้าร่วมจดหมายข่าวของเราสำหรับเคล็ดลับทางเทคนิค บทวิจารณ์ eBook ฟรี และดีลพิเศษ!

คลิกที่นี่เพื่อสมัครสมาชิก