อัลกอริธึมสับเปลี่ยนฟิชเชอร์-เยทส์
อัลกอริทึมนี้คือการสับเปลี่ยนองค์ประกอบในอาร์เรย์ ในการสับเปลี่ยนองค์ประกอบในอาร์เรย์ เราสามารถเขียนตรรกะของเราเองได้ แต่นักพัฒนาหลายคนคิดว่า F อิชเชอร์-เยทส์ อัลกอริทึมการสับเปลี่ยนสมัยใหม่เป็นวิธีที่ดีที่สุดในการสับเปลี่ยนองค์ประกอบในอาร์เรย์ อัลกอริทึมนี้มีขั้นตอนดังต่อไปนี้
ขั้นตอนที่ต้องปฏิบัติตาม
- ตามอัลกอริธึมนี้ เราควรวนรอบอาร์เรย์จากหลังมาข้างหน้า ตัวอย่างเช่น ในตัวอย่างต่อไปนี้ เรามีอาร์เรย์ที่ประกอบด้วย 8 องค์ประกอบ (A,B,C,D,E,F,G,H) จากดัชนี 0 ถึงดัชนี 7 ดังนั้นการวนรอบแรกจะส่งผลต่อองค์ประกอบที่ ดัชนีสุดท้าย 7 นั่นคือ H.
- ขั้นตอนต่อไปคือการสร้างตัวเลขสุ่ม (ดัชนีสุ่ม) ระหว่างดัชนีที่เลือก 7 และดัชนี 0 สำหรับสมมติว่าดัชนีสุ่มเป็น 3
- หลังจากได้รับดัชนีสุ่มสลับองค์ประกอบที่อยู่ในดัชนีที่เลือกและที่ดัชนีสุ่ม องค์ประกอบที่ดัชนีสุ่มในอาร์เรย์ที่ระบุคือ D ดังนั้นหลังจากสลับอาร์เรย์แล้ว อาร์เรย์จะเปลี่ยนเป็น A,B,C ,H,E,G,F,D
- ในการวนรอบที่สองให้ละเว้นดัชนีสุดท้าย (เนื่องจากวนซ้ำแล้ว) และพยายามค้นหาดัชนีสุ่มระหว่างดัชนี 0 และดัชนี 6 ที่อยู่ระหว่างองค์ประกอบ A และ F ปล่อยให้ดัชนีสุ่มที่สร้างขึ้นเป็น 2
- หลังจากได้รับดัชนีสุ่มแล้ว ให้สลับองค์ประกอบที่ดัชนีที่ 6 และ 2 ตอนนี้อาร์เรย์จะมีลักษณะเป็น A,B,F,H,E,G,C,D
- อัลกอริธึมนี้ใช้รูปแบบเดียวกับที่ไม่สนใจดัชนี 6 และเริ่มค้นหาดัชนีสุ่มระหว่างดัชนี 5 และดัชนี 0 เป็นต้น จนกว่าจะถึงดัชนี 1 ไม่สามารถใช้ดัชนี 0 วนซ้ำได้เนื่องจากไม่มีดัชนี น้อยกว่า 0 เพื่อวัตถุประสงค์ในการแลกเปลี่ยน
- โปรดทราบว่ามีความเป็นไปได้ที่จะสร้างดัชนีสุ่มเลือกดัชนีวนรอบ ตัวอย่างเช่น ให้ลูปทำงานระหว่างดัชนี 4 และดัชนี 0 ที่เลือก ปล่อยให้ดัชนีสุ่มสร้างเป็น 4 จากนั้นค่าที่ดัชนี 4 จะยังคงอยู่ที่ตำแหน่งเดิม
ตัวอย่างต่อไปนี้แสดงให้เห็นถึง ฟิชเชอร์-เยทส์ อัลกอริธึมสับเปลี่ยนที่ทันสมัย
ตัวอย่าง
<html>
<body>
<script>
var arr = ['A','B','C','D','E','F','G','H']
var i = arr.length, k , temp; // k is to generate random index and temp is to swap the values
while(--i > 0){
k = Math.floor(Math.random() * (i+1));
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
document.write(arr);
</script>
</body>
</html> ผลลัพธ์
C,F,H,D,A,G,E,B // note that output will change for every iteration.
