การเรียงลำดับการแทรก
เป็นการจัดเรียงแบบเปรียบเทียบที่ง่ายมากในการจัดเรียงอาร์เรย์ ประเภทเปรียบเทียบ เปรียบเทียบค่าปัจจุบันที่เราพยายามจัดเรียงกับค่าอื่นๆ ในอาร์เรย์ โดยจะทำงานกับทีละรายการและวางแต่ละรายการในตำแหน่งที่ถูกต้องซ้ำๆ เพื่อให้ได้อาร์เรย์ที่จัดเรียงตามที่ต้องการ
อันที่จริง การแทรก sort ไม่ได้มีประสิทธิภาพเท่ากับอัลกอริธึมขั้นสูงบางอย่าง เช่น heap sort หรือ การเรียงลำดับการผสาน . ไม่ใช่ตัวเลือกที่ดีที่สุดในขณะที่ต้องรับมือกับโปรแกรมขนาดใหญ่ เนื่องจาก ค่าคงที่ที่ซ่อนอยู่ต่ำ การเรียงลำดับการแทรกมีประสิทธิภาพเหนือกว่าอัลกอริธึมขั้นสูงบางตัว เช่น การเรียงลำดับแบบฮีปหรือการเรียงลำดับอย่างรวดเร็ว ในขณะที่จัดการกับ อาร์เรย์ขนาดเล็ก .
การเรียงลำดับการแทรก ทำงานโดยเลื่อนจากซ้ายไปขวาบนอาร์เรย์ จะใช้ รายการปัจจุบัน เป็น 'กุญแจ' และค้นหาค่าทางด้านซ้ายของคีย์นั้นเพื่อค้นหาตำแหน่งที่คีย์ควรจะอยู่จริง
อัลกอริทึม
ในตัวอย่างต่อไปนี้ อาร์เรย์ที่ระบุคือ 0,-3,5,8,2,7,6
- การวนซ้ำ 0 - ในการวนซ้ำครั้งแรก เรามีเฉพาะอาร์เรย์ที่ไม่ได้เรียงลำดับจริงเท่านั้น นั่นคือ 0,-3,5,8,2,7,6
- วนซ้ำ 1 - ในการทำซ้ำนี้ คีย์คือค่าที่ดัชนี 1 นั่นคือ -3 การเรียงลำดับการแทรกจะเปรียบเทียบคีย์กับค่าทางด้านซ้ายของคีย์นั้นและดำเนินการตามขั้นตอน เนื่องจาก -3 น้อยกว่า 0 มันจะเลื่อนไปทางซ้ายของ 0 โดยกำหนดให้อาร์เรย์เป็น -3,0,5,8,2,7,6
- ซ้ำ 2 - กุญแจสำคัญคือ 5 (ค่าที่ดัชนี 2) โดยจะนำไปเปรียบเทียบกับค่าทางด้านซ้ายซึ่งก็คือ -3 และ 0 และนำไปใส่ไว้ในค่าที่จัดเรียงไว้ ดังนั้นอาร์เรย์หลังการวนซ้ำ 2 คือ -3,0,5,8,2,7,6
- ซ้ำ 3 - ในการวนซ้ำนี้ ค่าคีย์ 8 จะถูกเปรียบเทียบกับองค์ประกอบทางด้านซ้าย และอาร์เรย์สุดท้ายจะเป็น -3,0,5,8,2,7,6
- ซ้ำ 4 - ในการทำซ้ำนี้ ค่าคีย์ 2 จะถูกเปรียบเทียบกับค่าทางด้านซ้ายและวางในตำแหน่งที่จัดเรียง ดังนั้นอาร์เรย์สุดท้ายหลังจากการวนซ้ำ 4 คือ -3,0,2,5,8,7,6
ในทำนองเดียวกัน เมื่อสิ้นสุดการวนซ้ำครั้งสุดท้าย อาร์เรย์ที่เรียงลำดับจะเป็น -3,0,2,5,6,7,8
ตัวอย่าง
<html>
<head>
<script>
function iSort(array) {
for (var p = 1; p < array.length; p++) {
if (array[p] < array[0]){
array.unshift(array.splice(p,1)[0]);
}
else if (array[p] > array[p-1]){
continue;
}
else {
for (var q = 1; q < p; q++) {
if (array[p] > array[q-1] && array[p] < array[q]){
array.splice(q,0,array.splice(p,1)[0]);
}
}
}
}
return array;
}
document.write(iSort([0,-3,5,8,2,7,6]));
</script>
</body>
</html> ผลลัพธ์
-3,0,2,5,6,7,8
