# ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์
ขั้นตอนวิธีของชไตน์เฮาส์ จอห์นสันและทร็อทเทอร์  คือ ขั้นตอนวิธีสร้างวิธีการเรียงสับเปลี่ยนโดยอาศัยการสลับที่ของตัวเลข

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

 <1 <2 <3 เครื่องหมายน้อยกว่า (<) หน้าตัวเลขแต่ละตัวเป็นการบอกทิศทางของเลขนั้นๆว่าเป็นทิศทางซ้าย ในทางกลับกันเครื่องหมายมากกว่า (>) ที่ตามหลังตัวเลขหมายถึงทิศทางขวา

 3> <1 <2 จากตัวอย่างข้างต้นแสดงให้เห็นว่าเลข 3 มีทิศทางขวา

 ตัวเลขที่เปลี่ยนที่ได้ 
ขั้นตอนวิธีนี้จะเรียกตัวเลขซึ่งมีตัวเลขที่อยู่ติดกันในทิศทางที่ระบุไว้มีค่าน้อยกว่าว่า ตัวเลขที่เปลี่ยนที่ได้ ยกตัวอย่างเช่น 3> <1 <2 ในกรณีนี้จะเรียกเลข 2 และเลข 3 ว่าตัวเลขที่เปลี่ยนที่ได้

 ถ้าตัวเลขอยู่ทางขวาสุด และมีทิศทางขวา หรือตัวเลขอยู่ทางซ้ายสุดและมีทิศทางซ้าย จะเรียกเลขนั้นว่าตัวเลขที่เปลี่ยนที่ไม่ได้

 ขั้นตอนวิธี 

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

 แสดงตามขั้นตอนวิธี 
 มีเลขจำนวน 3 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 6 วิธี
 <1 <2 <3
 <1 <3 <2
 <3 <1 <2 เลข 3 ไม่สามารถเปลี่ยนที่ได้แล้ว เนื่องจากอยู่ทางซ้ายสุดและมีทิศทางซ้าย จึงเปลี่ยนมาทำการสลับที่เลข 2 แทน
 3> <2 <1 เลข 3 เปลี่ยนทิศทาง เนื่องจากเมื่อ <2 สลับกับ <1 ขั้นตอนวิธีจะมีการตรวจสอบว่ามีตัวเลขที่มีค่ามากกว่าเลข 2 หรือไม่ ซึ่งก็มีคือเลข 3 จึงเปลี่ยนทิศทางของเลข 3 จากทิศทางซ้ายไปเป็นทิศทางขวา เลข 3 กลับมาเป็นเลขที่มีค่ามากที่สุดที่เปลี่ยนที่ได้
 <2 3> <1
 <2 <1 3>
 ขั้นตอนวิธีนี้สิ้นสุดลงเนื่องจากไม่มีตัวเลขที่สามารถเปลี่ยนที่ได้อีกแล้ว
 <2 เปลี่ยนที่ไม่ได้ เนื่องจากอยู่ทางซ้ายสุดและมีทิศทางซ้าย
 <1 เปลี่ยนที่ไม่ได้ เนื่องจากเลขที่อยู่ทางซ้ายมือของ 1 มีค่าไม่น้อยกว่า 1
 3> เปลี่ยนที่ไม่ได้ เนื่องจากอยู่ทางขวาสุดและมีทิศทางขวา

 ตัวอย่าง เมื่อมีตัวเลขจำนวน 4 ตัว 
 มีเลขจำนวน 4 ตัว จะทำให้มีวิธีเรียงสับเปลี่ยน 24 วิธี
 <1 <2 <3 <4
 <1 <2 <4 <3
 <1 <4 <2 <3
 <4 <1 <2 <3
 4> <1 <3 <2
 <1 4> <3 <2
 <1 <3 4> <2
 <1 <3 <2 4>
 <3 <1 <2 <4
 <3 <1 <4 <2
 <3 <4 <1 <2
 <4 <3 <1 <2
 4> 3> <2 <1
 3> 4> <2 <1
 3> <2 4> <1
 3> <2 <1 4>
 <2 3> <1 <4
 <2 3> <4 <1
 <2 <4 3> <1
 <4 <2 3> <1
 4> <2 <1 3>
 <2 4> <1 3>
 <2 <1 4> 3>
 <2 <1 3> 4>

 ประสิทธิภาพการทำงาน 
ขั้นตอนวิธีนี้มีเวลาในการทำงานเป็น Θ(n!) เมื่อ n คือจำนวนตัวเลขที่ต้องการหาวิธีการเรียงสับเปลี่ยน เนื่องจากจำนวนวิธีการเรียงสับเปลี่ยนคือ  เพราะฉะนั้นการใช้ขั้นตอนวิธีในการแจกแจงวิธีการเรียงสับเปลี่ยนจึงต้องใช้  ด้วย

 ตัวอย่างการประยุกต์ใช้งาน 
ในปริศนาควีนแปดตัวN-Queensสามารถนำขั้นตอนวิธีนี้ไปใช้ในการเลือกตำแหน่งการวางควีน เนื่องจากควีนไม่สามารถอยู่ในแถวหรือหลักเดียวกันได้มากกว่าหนึ่งตัว จึงไม่ทำให้เกิดเลขซ้ำกัน การใช้วิธีการเรียงสับเปลี่ยนจึงเป็นทางเลือกหนึ่งสำหรับการแก้ปัญหาประเภทนี้