การเรียงลำดับเป็นการดำเนินการพื้นฐานที่องค์ประกอบของอาร์เรย์ถูกจัดเรียงตามลำดับเฉพาะเพื่อเพิ่มความสามารถในการค้นหา ด้วยคำง่าย ๆ ข้อมูลจะถูกจัดเรียงเพื่อให้สามารถค้นหาได้ง่าย
แผนภูมิเปรียบเทียบ
| พื้นฐานสำหรับการเปรียบเทียบ | เรียงแทรก | เรียงลำดับการเลือก |
|---|---|---|
| ขั้นพื้นฐาน | ข้อมูลจะถูกจัดเรียงโดยการแทรกข้อมูลลงในไฟล์ที่เรียงลำดับที่มีอยู่ | ข้อมูลจะถูกจัดเรียงโดยการเลือกและวางองค์ประกอบต่อเนื่องในตำแหน่งที่เรียงลำดับ |
| ธรรมชาติ | มีเสถียรภาพ | ไม่แน่นอน |
| กระบวนการที่จะปฏิบัติตาม | องค์ประกอบเป็นที่รู้จักกันล่วงหน้าในขณะที่สถานที่ที่จะวางพวกเขาถูกค้นหา | ก่อนหน้านี้เป็นที่รู้จักกันในขณะที่มีการค้นหาองค์ประกอบ |
| ข้อมูลทันที | การเรียงลำดับการแทรกเป็นเทคนิคการเรียงลำดับแบบสดซึ่งสามารถจัดการกับข้อมูลได้ทันที | มันไม่สามารถจัดการกับข้อมูลได้ทันทีมันจะต้องมีการแสดงที่จุดเริ่มต้น |
| ความซับซ้อนของกรณีที่ดีที่สุด | บน) | O (n 2 ) |
ความหมายของการจัดเรียงการแทรก
การเรียงลำดับการแทรก ทำงานโดยการแทรกชุดของค่าในไฟล์ที่เรียงลำดับที่มีอยู่ มันสร้างอาร์เรย์ที่เรียงลำดับโดยการแทรกองค์ประกอบเดียวในเวลา กระบวนการนี้จะดำเนินต่อไปจนกระทั่งเรียงลำดับทั้งหมด แนวคิดหลักที่อยู่เบื้องหลังการเรียงลำดับการแทรกคือการแทรกแต่ละรายการลงในที่ที่เหมาะสมในรายการสุดท้าย วิธีการเรียงลำดับการแทรกจะบันทึกจำนวนหน่วยความจำที่มีประสิทธิภาพ
การทำงานของการเรียงลำดับการแทรก
- มันใช้สองชุดของอาร์เรย์ที่หนึ่งเก็บข้อมูลที่เรียงลำดับและอื่น ๆ ในข้อมูลที่ไม่เรียงลำดับ
- อัลกอริทึมการเรียงลำดับทำงานจนกว่าจะมีองค์ประกอบในชุดที่ไม่เรียงลำดับ
- สมมติว่ามีองค์ประกอบจำนวน 'n' ในอาร์เรย์ เริ่มแรกองค์ประกอบที่มีดัชนี 0 (LB = 0) มีอยู่ในชุดเรียงลำดับ องค์ประกอบที่เหลืออยู่ในพาร์ติชันที่ไม่เรียงลำดับของรายการ
- องค์ประกอบแรกของส่วนที่ไม่เรียงลำดับมีดัชนีอาร์เรย์ 1 (ถ้า LB = 0)
- หลังจากการวนซ้ำแต่ละครั้งจะเลือกองค์ประกอบแรกของพาร์ติชันที่ไม่เรียงลำดับแล้วแทรกเข้าไปในตำแหน่งที่เหมาะสมในชุดเรียงลำดับ
ข้อดีของการจัดเรียงการแทรก
- ดำเนินการได้ง่ายและมีประสิทธิภาพมากเมื่อใช้กับชุดข้อมูลขนาดเล็ก
- ความต้องการพื้นที่หน่วยความจำเพิ่มเติมของการเรียงลำดับการแทรกน้อยกว่า (เช่น O (1))
- ซึ่งถือว่าเป็นเทคนิคการเรียงลำดับแบบสดเนื่องจากสามารถเรียงลำดับรายการได้เมื่อได้รับองค์ประกอบใหม่
- มันเร็วกว่าอัลกอริทึมการเรียงลำดับอื่น ๆ
ตัวอย่าง:
ความหมายของการเรียงลำดับการเลือก
การเรียงลำดับการเลือก ดำเนินการเรียงลำดับโดยค้นหาหมายเลขค่าต่ำสุดและวางลงในตำแหน่งแรกหรือตำแหน่งสุดท้ายตามลำดับ (ขึ้นหรือลง) กระบวนการค้นหาคีย์ต่ำสุดและวางในตำแหน่งที่เหมาะสมจะดำเนินต่อไปจนกว่าองค์ประกอบทั้งหมดจะถูกวางในตำแหน่งที่เหมาะสม
การทำงานของการเรียงลำดับการเลือก
- สมมติว่าอาร์เรย์ ARR ที่มีองค์ประกอบ N ในหน่วยความจำ
- ในการผ่านครั้งแรกคีย์ที่เล็กที่สุดจะถูกค้นหาพร้อมกับตำแหน่งของมันจากนั้น ARR [POS] จะถูกสลับกับ ARR [0] ดังนั้น ARR [0] จึงถูกจัดเรียง
- ในรอบที่สองตำแหน่งของค่าที่น้อยที่สุดจะถูกกำหนดอีกครั้งใน subarray ขององค์ประกอบ N-1 แลกเปลี่ยน ARR [POS] ด้วย ARR [1]
- ใน pass N-1 จะมีการดำเนินการกระบวนการเดียวกันเพื่อเรียงลำดับองค์ประกอบ N จำนวน
ตัวอย่าง:
ความแตกต่างที่สำคัญระหว่างการเรียงลำดับการแทรกและการเรียงลำดับการเลือก
- การเรียงลำดับการแทรกมักจะทำการดำเนินการแทรก ในทางตรงกันข้ามเรียงลำดับการเลือกดำเนินการเลือกและการวางตำแหน่งขององค์ประกอบที่จำเป็น
- การเรียงลำดับการแทรกถูกกล่าวว่ามีความเสถียรในขณะที่การเรียงลำดับการเลือกไม่ใช่อัลกอริทึมที่เสถียร
- ในขั้นตอนวิธีการเรียงลำดับการแทรกองค์ประกอบเป็นที่รู้จักกันก่อนหน้านี้ ในทางตรงกันข้ามการเรียงลำดับการเลือกมีตำแหน่งไว้ล่วงหน้า
- การเรียงลำดับการแทรกเป็นเทคนิคการเรียงลำดับแบบสดที่องค์ประกอบที่มาถึงจะถูกจัดเรียงในรายการทันทีในขณะที่การเรียงลำดับการเลือกไม่สามารถทำงานได้ดีกับข้อมูลทันที
- การเรียงลำดับการแทรกมีเวลาทำงาน O (n) ในกรณีที่ดีที่สุด เมื่อเทียบกับความซับซ้อนของเวลารันไทม์ของการเรียงลำดับการเลือกที่ดีที่สุดคือ O (n2)
ความซับซ้อนของการเรียงลำดับการแทรก
ความซับซ้อนของกรณีที่ดีที่สุดของการเรียงลำดับการแทรกคือ O (n) คูณนั่นคือเมื่อเรียงลำดับอาเรย์ก่อนหน้านี้ ในทำนองเดียวกันเมื่อเรียงลำดับตามลำดับย้อนหลังองค์ประกอบแรกของอาร์เรย์ที่ไม่เรียงลำดับจะถูกเปรียบเทียบกับแต่ละองค์ประกอบในชุดเรียงลำดับ ดังนั้นในกรณีที่เลวร้ายที่สุดเวลารันของการเรียงลำดับการแทรกคือกำลังสองคือ O (n2) โดยทั่วไปแล้วจะต้องทำการเปรียบเทียบขั้นต่ำ (k-1) / 2 ดังนั้นกรณีเฉลี่ยยังมีเวลารันกำลังสอง O (n2)
ความซับซ้อนของการเรียงลำดับการเลือก
เนื่องจากการทำงานของการเลือกการเรียงลำดับไม่ได้ขึ้นอยู่กับลำดับดั้งเดิมขององค์ประกอบในอาร์เรย์ดังนั้นจึงไม่มีความแตกต่างระหว่างกรณีที่ดีที่สุดและความซับซ้อนของกรณีที่แย่ที่สุดของการเรียงลำดับการเลือก
การเรียงลำดับการเลือกจะเลือกองค์ประกอบค่าต่ำสุดในกระบวนการเลือกองค์ประกอบทั้งหมด 'n' จะถูกสแกน ดังนั้นจึงทำการเปรียบเทียบ n-1 ในรอบแรก จากนั้นองค์ประกอบจะถูกสับเปลี่ยน ในทำนองเดียวกันในรอบที่สองยังหาองค์ประกอบที่เล็กที่สุดที่สองที่เราต้องการสแกนขององค์ประกอบที่เหลือ n-1 และกระบวนการจะดำเนินการต่อไปจนถึงเรียงลำดับทั้งหมด
ดังนั้นความซับซ้อนของเวลาในการเรียงลำดับการเลือกจึงเป็น O (n2)
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
ข้อสรุป
ระหว่างอัลกอริทึมการเรียงลำดับทั้งสองการเรียงลำดับการแทรกนั้นรวดเร็วมีประสิทธิภาพและมีเสถียรภาพในขณะที่การเลือกการเรียงลำดับจะทำงานได้อย่างมีประสิทธิภาพเมื่อมีองค์ประกอบขนาดเล็กเข้ามาเกี่ยวข้อง จำนวนการเปรียบเทียบที่ทำโดยการเรียงลำดับการเลือกมากกว่าการเคลื่อนไหวที่ทำในขณะที่การเรียงแทรกจำนวนครั้งที่องค์ประกอบถูกย้ายหรือสลับกันมีค่ามากกว่าการเปรียบเทียบที่ทำ
