ในวิทยาการคอมพิวเตอร์ introselect (ย่อมาจาก "introspective selection") เป็นอัลกอริธึมการเลือกที่เป็นลูกผสมระหว่างquickselectและmedian of mediansซึ่งมีประสิทธิภาพเฉลี่ยที่รวดเร็วและประสิทธิภาพในกรณีที่เลวร้ายที่สุดที่ดีที่สุด Introselect เกี่ยวข้องกับอัลกอริธึมการเรียงลำดับintrosort : ทั้งสองเป็นการปรับปรุงที่คล้ายคลึงกันของอัลกอริธึม quickselect และquicksort พื้นฐาน โดยที่ทั้งสองเริ่มต้นด้วยอัลกอริธึมที่รวดเร็ว ซึ่งมีประสิทธิภาพเฉลี่ยที่ดีและค่าใช้จ่ายต่ำ แต่จะกลับไปใช้อัลกอริธึมที่ดีที่สุดในกรณีที่เลวร้ายที่สุด (ที่มีค่าใช้จ่ายสูงกว่า) หากอัลกอริธึมที่รวดเร็วไม่ก้าวหน้าเร็วพอ อัลกอริธึมทั้งสองได้รับการแนะนำโดยDavid Musserใน ( Musser 1997 ) โดยมีวัตถุประสงค์เพื่อจัดหาอัลกอริธึมทั่วไปสำหรับไลบรารีมาตรฐาน C++ที่มีทั้งประสิทธิภาพเฉลี่ยที่รวดเร็วและประสิทธิภาพในกรณีที่เลวร้ายที่สุดที่ดีที่สุด จึงทำให้สามารถเข้มงวดข้อกำหนดด้านประสิทธิภาพได้^{[ 1 ]}

อย่างไรก็ตาม ในการใช้งานไลบรารีมาตรฐาน C++ ส่วนใหญ่ จะใช้อัลกอริธึม "introselect" ที่แตกต่างกัน ซึ่งรวม quickselect และheapselect เข้าด้วยกัน และมีเวลาการทำงานในกรณีที่เลวร้ายที่สุดคือO ( n log n ) ^{[ 2 ]}ร่างมาตรฐาน C++ ณ ปี 2022 ไม่มีข้อกำหนดเกี่ยวกับประสิทธิภาพในกรณีที่เลวร้ายที่สุด ดังนั้นจึงอนุญาตให้เลือกได้^{[ 3 ]}

Introsort ให้ประสิทธิภาพการทำงานที่เทียบเท่ากับ quicksort ในขณะที่ยังคงรักษา ประสิทธิภาพในกรณีที่เลวร้ายที่สุดไว้ที่ O ( n log n ) โดยการสร้างลูกผสมระหว่าง quicksort และheapsort Introsort เริ่มต้นด้วย quicksort ดังนั้นจึงให้ประสิทธิภาพที่คล้ายกับ quicksort หาก quicksort ทำงานได้ และจะเปลี่ยนไปใช้ heapsort (ซึ่งมีประสิทธิภาพในกรณีที่เลวร้ายที่สุดที่ดีที่สุด) หาก quicksort ไม่คืบหน้าเร็วพอ ในทำนองเดียวกัน introselect ผสมผสาน quickselect กับ median of medians เพื่อให้ได้การเลือกเชิงเส้นในกรณีที่เลวร้ายที่สุดด้วยประสิทธิภาพที่คล้ายกับ quickselect

Introselect ทำงานโดยเริ่มต้นอย่างมองโลกในแง่ดีด้วย quickselect และจะเปลี่ยนไปใช้อัลกอริธึมการเลือกแบบเชิงเส้นในกรณีที่เลวร้ายที่สุด (อัลกอริธึมค่ามัธยฐานของ Blum-Floyd-Pratt-Rivest-Tarjan ) ก็ต่อเมื่อมันเรียกซ้ำมากเกินไปโดยที่ไม่มีความคืบหน้าเพียงพอ กลยุทธ์การเปลี่ยนไปใช้อัลกอริธึมอื่นเป็นเนื้อหาทางเทคนิคหลักของอัลกอริธึม การจำกัดการเรียกซ้ำให้มีความลึกคงที่นั้นไม่ดีพอ เนื่องจากจะทำให้อัลกอริธึมเปลี่ยนไปใช้อัลกอริธึมอื่นกับรายการที่มีขนาดใหญ่เพียงพอทั้งหมด Musser ได้กล่าวถึงแนวทางง่ายๆ สองสามวิธี:

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

ทั้งสองแนวทางจำกัดความลึกของการเรียกซ้ำไว้ที่k ⌈log n ⌉ = O (log n ) และเวลาการทำงานทั้งหมดไว้ที่O ( n )

บทความดังกล่าวระบุว่าจะมีงานวิจัยเพิ่มเติมเกี่ยวกับ introselect ในอนาคต แต่ผู้เขียนได้เกษียณอายุในปี 2007 โดยไม่ได้ตีพิมพ์งานวิจัยเพิ่มเติมใดๆ เลย

• อัลกอริทึมฟลอยด์-ริเวสต์