Inset sort: ตัวอย่างการทำงานของอัลกอริทึม

2024 ผู้เขียน: Angel Austin | [email protected]. แก้ไขล่าสุด: 2024-02-02 14:52

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

คำอธิบายของอัลกอริทึม

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

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

การจัดเรียงอาจมีลักษณะดังนี้:

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

เป็นต้นจนจบอาร์เรย์เดิม

การเรียงลำดับการแทรกในชีวิตจริง

เพื่อความชัดเจน ควรยกตัวอย่างวิธีการใช้กลไกการเรียงลำดับนี้ในชีวิตประจำวัน

เอา เช่น กระเป๋าเงิน ธนบัตรหนึ่งร้อยห้าร้อยพันดอลลาร์อยู่ในช่องธนบัตรอย่างไม่เป็นระเบียบ นี่เป็นเรื่องเลอะเทอะในการผสมผสานดังกล่าวเป็นการยากที่จะหากระดาษที่เหมาะสมในทันที ต้องเรียงลำดับธนบัตร

อันแรกคือธนบัตร 1,000 รูเบิลและหลังจากนั้น - 100 เราเอาหนึ่งร้อยมาวางไว้ข้างหน้า ที่สามในแถวคือ 500 รูเบิล สถานที่ที่ถูกต้องคือระหว่างแสนถึงพัน

ในลักษณะเดียวกับที่เราจัดเรียงไพ่ที่ได้รับเมื่อเล่น "คนโง่" เพื่อให้นำทางได้ง่ายขึ้น

ตัวดำเนินการและตัวช่วย

วิธีการจัดเรียงการแทรกใช้เป็นอินพุตอาร์เรย์เริ่มต้นที่จะจัดเรียง ฟังก์ชันเปรียบเทียบ และฟังก์ชันที่กำหนดกฎสำหรับการแจงนับองค์ประกอบ หากจำเป็น ส่วนใหญ่มักใช้แทนคำสั่งวนปกติ

องค์ประกอบแรกคือชุดลำดับ ดังนั้นการเปรียบเทียบจึงเริ่มจากชุดที่สอง

อัลกอริทึมมักใช้ฟังก์ชันตัวช่วยเพื่อแลกเปลี่ยนค่าสองค่า (สลับ) มันใช้ตัวแปรชั่วคราวเพิ่มเติม ซึ่งใช้หน่วยความจำและทำให้โค้ดช้าลงเล็กน้อย

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

อัลกอริธึมสำหรับการจัดเรียงอาร์เรย์ด้วยการแทรก

ตัวอย่างการใช้งาน

การใช้งานเฉพาะส่วนใหญ่ขึ้นอยู่กับภาษาโปรแกรมที่ใช้ ไวยากรณ์และโครงสร้างของมัน

Classic C ใช้งานโดยใช้ตัวแปรชั่วคราวเพื่อแลกเปลี่ยนค่า:


int i, j, อุณหภูมิ; for (i=1; i =0; j--) { if (array[j] < temp) แตก; อาร์เรย์[j + 1]=อาร์เรย์[j]; อาร์เรย์[j]=อุณหภูมิ; } }

การติดตั้ง PHP:

ฟังก์ชั่น insertion_sort(&$a) { สำหรับ ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }


ที่นี่ ก่อนอื่น องค์ประกอบทั้งหมดที่ไม่ตรงกับเงื่อนไขการจัดเรียงจะถูกเลื่อนไปทางขวา จากนั้นองค์ประกอบปัจจุบันจะถูกแทรกลงในพื้นที่ว่าง
รหัส Java ใช้ while loop:


public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }

ความหมายทั่วไปของรหัสยังคงไม่เปลี่ยนแปลง: แต่ละองค์ประกอบของอาร์เรย์จะถูกเปรียบเทียบกับองค์ประกอบก่อนหน้าตามลำดับและสลับกับองค์ประกอบเหล่านี้หากจำเป็น

เวลาทำงานโดยประมาณ
แน่นอน ในกรณีที่ดีที่สุด อินพุตของอัลกอริธึมจะเป็นอาร์เรย์ที่เรียงลำดับแล้วอย่างถูกวิธี ในสถานการณ์นี้ อัลกอริทึมจะต้องตรวจสอบแต่ละองค์ประกอบเพื่อให้แน่ใจว่าอยู่ในตำแหน่งที่ถูกต้องโดยไม่ต้องทำการแลกเปลี่ยน ดังนั้น เวลาทำงานจะขึ้นอยู่กับความยาวของอาร์เรย์ดั้งเดิม O(n). โดยตรง
อินพุตตัวพิมพ์เล็กที่สุดคืออาร์เรย์ที่เรียงลำดับย้อนกลับ สิ่งนี้จะต้องมีการเรียงสับเปลี่ยนจำนวนมาก ฟังก์ชันรันไทม์จะขึ้นอยู่กับจำนวนขององค์ประกอบกำลังสอง
จำนวนการเรียงสับเปลี่ยนที่แน่นอนสำหรับอาร์เรย์ที่ไม่เรียงลำดับทั้งหมดสามารถคำนวณได้โดยใช้สูตร:


n(n-1)/2

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



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


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



Image

ด้านบนนี้เป็นตัวอย่างภาพที่ยอดเยี่ยมของการจัดเรียงการแทรกในการเต้นรำ