แนะนำ, 2019

ตัวเลือกของบรรณาธิการ

ความแตกต่างระหว่างการจัดเรียงการแทรกและการเรียงลำดับการเลือก

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

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

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบเรียงแทรกเรียงลำดับการเลือก
ขั้นพื้นฐาน
ข้อมูลจะถูกจัดเรียงโดยการแทรกข้อมูลลงในไฟล์ที่เรียงลำดับที่มีอยู่ข้อมูลจะถูกจัดเรียงโดยการเลือกและวางองค์ประกอบต่อเนื่องในตำแหน่งที่เรียงลำดับ
ธรรมชาติ
มีเสถียรภาพไม่แน่นอน
กระบวนการที่จะปฏิบัติตาม
องค์ประกอบเป็นที่รู้จักกันล่วงหน้าในขณะที่สถานที่ที่จะวางพวกเขาถูกค้นหาก่อนหน้านี้เป็นที่รู้จักกันในขณะที่มีการค้นหาองค์ประกอบ
ข้อมูลทันที
การเรียงลำดับการแทรกเป็นเทคนิคการเรียงลำดับแบบสดซึ่งสามารถจัดการกับข้อมูลได้ทันทีมันไม่สามารถจัดการกับข้อมูลได้ทันทีมันจะต้องมีการแสดงที่จุดเริ่มต้น
ความซับซ้อนของกรณีที่ดีที่สุดบน)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 จำนวน

ตัวอย่าง:

ความแตกต่างที่สำคัญระหว่างการเรียงลำดับการแทรกและการเรียงลำดับการเลือก

  1. การเรียงลำดับการแทรกมักจะทำการดำเนินการแทรก ในทางตรงกันข้ามเรียงลำดับการเลือกดำเนินการเลือกและการวางตำแหน่งขององค์ประกอบที่จำเป็น
  2. การเรียงลำดับการแทรกถูกกล่าวว่ามีความเสถียรในขณะที่การเรียงลำดับการเลือกไม่ใช่อัลกอริทึมที่เสถียร
  3. ในขั้นตอนวิธีการเรียงลำดับการแทรกองค์ประกอบเป็นที่รู้จักกันก่อนหน้านี้ ในทางตรงกันข้ามการเรียงลำดับการเลือกมีตำแหน่งไว้ล่วงหน้า
  4. การเรียงลำดับการแทรกเป็นเทคนิคการเรียงลำดับแบบสดที่องค์ประกอบที่มาถึงจะถูกจัดเรียงในรายการทันทีในขณะที่การเรียงลำดับการเลือกไม่สามารถทำงานได้ดีกับข้อมูลทันที
  5. การเรียงลำดับการแทรกมีเวลาทำงาน 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)

ข้อสรุป

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

Top