การเรียงลำดับการแทรกคืออะไร และทำงานอย่างไร (พร้อมตัวอย่าง)

© BEST-BACKGROUNDS/Shutterstock.com

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

การเรียงลำดับการแทรกคืออะไร

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

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

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

เนื่องจากการจัดเรียงแบบแทรกเป็นอัลกอริทึมที่ค่อนข้างง่าย จึงเหมาะที่สุดสำหรับชุดข้อมูลที่มีขนาดค่อนข้างเล็ก รวมถึงชุดข้อมูลที่ค่อนข้างถูกจัดเรียงแล้ว ด้วยวิธีนี้ เรียกได้ว่าเป็นอัลกอริทึมที่ปรับเปลี่ยนได้และมีประสิทธิภาพ ต่อไป เราจะพูดถึงทฤษฎีเบื้องหลังการทำงานของการเรียงลำดับการแทรก

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

วิธีการเรียงลำดับการแทรกสามารถแสดงอย่างกระชับด้วยรหัสจำลองต่อไปนี้:

insertionSort (อาร์เรย์) ทำเครื่องหมายองค์ประกอบแรกว่าเรียงลำดับสำหรับแต่ละองค์ประกอบที่ไม่เรียงลำดับ X’แยก’องค์ประกอบ X สำหรับ j-lastSortedIndex ลงไปที่ 0 ถ้าองค์ประกอบปัจจุบัน j > X ย้ายองค์ประกอบที่เรียงลำดับไปทางขวา 1 วงแบ่งและใส่ X ที่นี่สิ้นสุด insertionSort

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

การทำงานภายในของการเรียงลำดับการแทรก

ตอนนี้เราได้กล่าวถึงวิธีการทำงานของการเรียงลำดับการแทรกและทฤษฎีที่อยู่เบื้องหลัง ถึงเวลาแสดงกระบวนการ ด้วยอาร์เรย์ที่เหมาะสม หากเราพิจารณาชุดข้อมูลต่อไปนี้:

เราสามารถถือว่าองค์ประกอบแรก 10 ถูกจัดเรียงแล้ว หลังจากนี้ เรานำองค์ประกอบที่สองคือ 14 และจัดเก็บแยกกัน เมื่อเปรียบเทียบ 14 ถึง 10 เราจะเห็นว่ามีค่ามากกว่า ดังนั้นจึงรักษาตำแหน่งเป็นองค์ประกอบที่สอง นี่เป็นการวนซ้ำครั้งแรก เรียกว่าการผ่านครั้งแรก องค์ประกอบแรก 10 ถูกเก็บไว้ในแถบย่อย

โดยที่สีเขียว=อาร์เรย์ที่เรียงลำดับ

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

อัลกอริทึมจะเปรียบเทียบกับองค์ประกอบในแถบย่อยที่เรียงลำดับ 5 ยังเล็กกว่า 10 ดังนั้นจึงย้ายไปที่จุดเริ่มต้นของ subarray อาร์เรย์ที่เรียงลำดับตอนนี้มี 2 องค์ประกอบ — 5 และ 10

ตอนนี้ เราจะไปยังรอบที่สาม ในกรณีนี้ 7 เป็นองค์ประกอบที่เลือก ค่านี้น้อยกว่า 14 ดังนั้นจึงถูกย้ายหนึ่งตำแหน่งไปทางซ้ายและเข้าไปในอาร์เรย์ที่เรียงลำดับ นี่ไม่ใช่ตำแหน่งที่ถูกต้อง เนื่องจาก 7 น้อยกว่า 10 แต่มากกว่า 5 ดังนั้น จึงย้ายไปอีกตำแหน่งหนึ่งทางซ้าย

สำหรับรอบที่สี่ เรากำลังดูตำแหน่งที่สี่ องค์ประกอบ ซึ่งก็คือ 14 ซึ่งถูกจัดเรียงแล้ว ดังนั้นตอนนี้อาร์เรย์ที่จัดเรียงจึงมี 5, 7, 10 และ 14

ผลลัพธ์สุดท้าย

สุดท้าย สำหรับรอบที่ห้า เราใช้องค์ประกอบที่ห้า ซึ่งก็คือ 1 นี่เห็นได้ชัดว่าเล็กกว่า 14 ดังนั้นจึงสลับตำแหน่ง มันยังเล็กกว่า 10 ดังนั้นตำแหน่งจะถูกสลับอีกครั้ง สิ่งนี้ดำเนินต่อไปอีกสองครั้งเนื่องจาก 1 เป็นองค์ประกอบที่เล็กที่สุดในอาร์เรย์ ดังนั้นเราจึงลงเอยด้วยการเรียงลำดับดังนี้:

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

การเรียงลำดับการแทรกสามารถนำไปใช้กับภาษาโปรแกรมต่างๆ จาก C, C# และ C++ เป็น Java, Python, PHP และ Javascript เพื่อจุดประสงค์ในการอธิบาย เราจะทำงานกับ Python กระบวนการทั้งหมดสามารถแสดงได้ในโค้ดต่อไปนี้:

def insertionSort(arr): if (n:=len(arr))=1: return for i in range(1, n): key=arr[i ] j=i-1 ในขณะที่ j >=0 และคีย์ arr[j]: arr[j+1]=arr[j] j-=1 arr[j+1]=ปุ่ม arr=[10, 14, 5, 7, 1] insertionSort(arr) print(arr)

ก่อนอื่น เรากำลังกำหนดตัวเรียงลำดับการแทรกเป็นฟังก์ชันของอาร์เรย์ (arr) จากนั้น เรากำลังบอกว่า ถ้าอาร์เรย์มีความยาว 1 หรือน้อยกว่า อาร์เรย์จะถูกส่งกลับ ต่อไป เราจะกำหนดองค์ประกอบในตำแหน่งที่ i ของอาร์เรย์ที่มีความยาว n เป็นคีย์

เรากำลังใส่ข้อจำกัดในการคำนวณเพื่อให้ j ทำงานได้ก็ต่อเมื่อมีค่ามากกว่าหรือเท่ากับดัชนี 0 เท่านั้น J ถือเป็นค่าทางด้านซ้ายของรายการใดก็ตามที่เรากำลังดู เช่น ต่อ j=ผม-1 ถ้าค่ามากกว่าคีย์ ตำแหน่งจะเลื่อนไปทางขวา

บรรทัดสุดท้าย arr[j+1]=คีย์ กำหนดให้ค่าทางด้านขวาของค่า j นี้กลายเป็นคีย์ใหม่ ดังนั้นตัวเลขที่เหลือจะถูกสลับตามความจำเป็น กระบวนการนี้จะดำเนินต่อไปตั้งแต่ต้น จนกว่าตัวเลขทั้งหมดจะถูกจัดเรียงอย่างถูกต้อง

Insertion Sort in Python: Implementation

เรามาดูกันว่าสิ่งนี้ถูกนำมาใช้ใน Python ภายในสภาพแวดล้อม Spyder อย่างไร เราจะใช้อาร์เรย์เดียวกันกับก่อนหน้านี้เพื่อแสดงให้เห็นอย่างชัดเจน ดูรหัสการใช้งานด้านล่าง:

การใช้การเรียงลำดับการแทรกใน Python

©”TNGD”.com

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

ได้รับข้อความแสดงข้อผิดพลาด

©”TNGD”.com

กรณีการใช้งานการจัดเรียงการแทรกที่ดีที่สุดและแย่ที่สุด

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

ความซับซ้อนของเวลาด้วยการเรียงลำดับการแทรก

ความซับซ้อนของเวลาในแต่ละกรณีสามารถอธิบายได้ในตารางต่อไปนี้:

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

อย่างไรก็ตาม ในกรณีเฉลี่ยและเลวร้ายที่สุด ความซับซ้อนจะเท่ากับ O(n2) กรณีทั่วไปจะเป็นที่ที่องค์ประกอบในอาร์เรย์สับสน ทั้งจากน้อยไปหามากหรือจากมากไปน้อย ในกรณีที่เลวร้ายที่สุด องค์ประกอบจะต้องเรียงกลับกัน

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

ความซับซ้อนของพื้นที่ที่มีการจัดเรียงการแทรก

ความซับซ้อนประเภทอื่นคือความซับซ้อนของพื้นที่ นี่หมายถึงจำนวนพื้นที่หน่วยความจำที่จำเป็นในการเรียกใช้อัลกอริทึม ความซับซ้อนของ O(1) หมายความว่าจำนวนหน่วยความจำที่ต้องการนั้นคงที่ โดยไม่คำนึงถึงขนาดอินพุต

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

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

สรุป

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

ถัดไป

คืออะไร การเรียงลำดับการแทรกและทำงานอย่างไร (พร้อมตัวอย่าง) FAQs (คำถามที่พบบ่อย) 

การเรียงลำดับการแทรกคืออะไร

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

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

เมื่อใดที่คุณควรใช้การเรียงลำดับการแทรก

การเรียงลำดับการแทรกเหมาะที่สุดสำหรับชุดข้อมูลขนาดเล็กและชุดข้อมูลที่มีการเรียงลำดับค่าบางส่วนแล้ว

ภาษาโปรแกรมใดที่สามารถใช้การเรียงลำดับการแทรกได้

มาก ภาษาการเขียนโปรแกรมสามารถใช้การเรียงลำดับการแทรก รวมถึง C, C++, C#, Java, Javascript, PHP และ Python

ข้อดีของการเรียงลำดับการแทรกคืออะไร

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

การจัดเรียงการแทรกได้รับการปรับให้เหมาะสมอย่างไร

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

การเรียงลำดับการแทรกมีการวนซ้ำกี่ครั้ง