การเรียงลำดับการแทรก Java จะประเมินแต่ละรายการในรายการ ถ้ารายการน้อยกว่าก่อนหน้านี้ การเรียงลำดับจะสลับรายการ มิฉะนั้น รายการจะอยู่ที่เดิมและสองรายการถัดไปจะถูกเปรียบเทียบในรายการ
คอมพิวเตอร์สามารถจัดเรียงรายการสิ่งของได้ดี เมื่อใช้การวนซ้ำ คุณสามารถค้นหารายการทั้งหมดในรายการและเปลี่ยนลำดับของรายการจนกว่าจะปรากฏขึ้นในลักษณะใดแบบหนึ่ง
ในการเขียนโปรแกรม มีวิธีการมาตรฐานสองสามวิธีในการเรียงลำดับรายการ เราเรียกอัลกอริธึมการเรียงลำดับเหล่านี้ เรียงลำดับอัลกอริทึมที่อ่านรายการทั้งหมดในรายการและจัดเรียงโดยใช้ชุดคำสั่งเฉพาะ อัลกอริธึมการจัดเรียงที่พบบ่อยที่สุดอย่างหนึ่งที่คุณจะพบคือการเรียงลำดับการแทรก
ในคู่มือนี้ เราจะพูดถึงวิธีการใช้อัลกอริธึมการเรียงลำดับการแทรก Java เราจะอธิบายตัวอย่างตลอดทางเพื่อให้คุณได้เรียนรู้ว่าตรรกะที่อยู่เบื้องหลังการจัดเรียงนี้ทำงานอย่างไร
เริ่มกันเลย!
การเรียงลำดับการแทรก Java คืออะไร
การเรียงลำดับการแทรก Java ทำงานคล้ายกับการเรียงลำดับไพ่ในมือของคุณในเกมไพ่ การเรียงลำดับการแทรกจะตรวจสอบแต่ละรายการในรายการและสลับกับรายการทางด้านซ้าย การสลับรายการหรือไม่นั้นขึ้นอยู่กับว่ารายการนั้นมากกว่าหรือน้อยกว่ารายการก่อนหน้า
ลองนึกภาพสักครู่ว่าคุณกำลังเล่นเกมไพ่ – ไพ่รัมมี่ อะไรก็ได้ เมื่อคุณจัดเรียงไพ่ คุณจะทำอย่างไร
คุณจะเริ่มทางด้านซ้ายและตรวจสอบว่าไพ่ใบที่สองถูกจัดเรียงหรือไม่ หากไพ่ใบนั้นมากกว่าใบสุดท้าย มันควรจะอยู่ในตำแหน่งเดิม ในทางเดียวกัน ควรเลื่อนตำแหน่งในรายการ
81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้
ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก
คุณจะต้องผ่านการ์ดทุกใบในมือของคุณและดำเนินการนี้จนกว่าการ์ดทุกใบจะปรากฏในลำดับที่ถูกต้อง
คุณควรใช้การเรียงลำดับการแทรกเมื่อใด
การเรียงลำดับการแทรกจะใช้มากที่สุดเมื่อมีองค์ประกอบทางด้านซ้ายเพียงไม่กี่รายการที่ต้องจัดเรียง
มีอัลกอริธึมที่มีประสิทธิภาพมากกว่าที่คุณสามารถใช้เพื่อเรียงลำดับรายการข้อมูลขนาดใหญ่ เช่น การเรียงลำดับแบบผสาน นี่คือเหตุผลที่คุณไม่ควรตั้งค่าเริ่มต้นเป็นการใช้การเรียงลำดับการแทรกเสมอ จากที่กล่าวมา การเรียงลำดับการแทรกจะมีประสิทธิภาพมากกว่าการเรียงลำดับแบบฟองและการเรียงลำดับการเลือกที่การเรียงลำดับองค์ประกอบในรายการ
การเรียงลำดับการแทรกเป็นอัลกอริธึมการเรียงลำดับอย่างง่าย ซึ่งหมายความว่าเป็นการดีสำหรับผู้เริ่มต้นที่จะเรียนรู้
แนะนำการเรียงลำดับการแทรก
การแสดงภาพสำรับไพ่ไม่ใช่เรื่องง่ายที่สุดในโลก มาดูตัวอย่างการเขียนโปรแกรมเพื่อเริ่มต้นกัน พิจารณารายการต่อไปนี้:
| 8 | 6 | 3 | 9 |
ในรายการนี้ เราถือว่าองค์ประกอบแรกถูกจัดเรียง
ขั้นตอนต่อไปของเราคือการเปรียบเทียบรายการที่สองในรายการของเรากับรายการแรก หากรายการแรกมากกว่ารายการที่สอง รายการนั้นจะถูกวางไว้ด้านหน้ารายการแรก
ในกรณีนี้ 6 จะมากกว่า 8 ซึ่งหมายความว่า 6 จะย้ายกลับในรายการของเราหนึ่งตำแหน่ง และ 8 จะเลื่อนไปข้างหน้าหนึ่งตำแหน่ง:
| 6 | 8 | 3 | 9 |
ตอนนี้เราต้องเปรียบเทียบองค์ประกอบที่สามกับองค์ประกอบทางด้านซ้าย:3 มากกว่า 8 หรือไม่? ไม่ 8 ย้ายตำแหน่งไปทางขวา:
| 6 | 3 | 8 | 9 |
3 มากกว่า 6 หรือไม่? ไม่ เราเลื่อนเลข 6:
| 3 | 6 | 8 | 9 |
ตอนนี้ เราต้องเปรียบเทียบว่ารายการที่สี่ในรายการของเรา – รายการสุดท้าย – มากกว่ารายการอื่นๆ ในรายการของเราหรือไม่ ในกรณีนี้ 9 มีค่ามากกว่ารายการทั้งหมดที่มาก่อน:8, 6 และ 3
นี่คืออัลกอริทึมที่เราใช้ในการจัดเรียงรายการของเรา:
- จัดเรียงองค์ประกอบแรก
- เปรียบเทียบรายการที่สองกับรายการทางด้านซ้าย
- หากรายการนี้มากกว่าค่าทางด้านซ้าย รายการนั้นก็จะอยู่ที่เดิม มิฉะนั้น เราจะย้ายค่าไปทางซ้าย
- ทำซ้ำจนกว่ารายการทั้งหมดจะปรากฏตามลำดับ
ตอนนี้เรามี sorted array แล้ว การเรียงลำดับการแทรกจะเรียงลำดับทีละรายการ มาพูดคุยถึงวิธีการใช้อัลกอริธึมการเรียงลำดับนี้ใน Java
วิธีการทำการเรียงลำดับการแทรกใน Java
ค่าสูงสุดของสองค่าที่กำลังเปรียบเทียบจะถูกแทรกหนึ่งตำแหน่งไปทางขวาทุกครั้งที่เรียกใช้ฟังก์ชันการเรียงลำดับ
เป็นการพูดถึงเรื่องนี้ในแง่ทฤษฎีเป็นอย่างดี แต่คุณจะนำไปใช้ใน Java ได้อย่างไร? นั่นเป็นคำถามที่ดี มาเขียนชั้นเรียนที่ทำการเรียงลำดับการแทรกในรายการเกรดของนักเรียนกันเถอะ
เตรียมอาร์เรย์ไลบรารี
เริ่มต้นด้วยการนำเข้าไลบรารี Arrays ลงในโปรแกรม Java ของเรา เราจะใช้ไลบรารีนี้เพื่อพิมพ์รายการของเราไปที่คอนโซลเมื่อเราจัดเรียงแล้ว:
นำเข้า java.util.Arrays;
ประกาศวิธีการจัดเรียง
เราจะเริ่มต้นด้วยการประกาศวิธีการที่ผ่านรายการของเราและจัดเรียงข้อมูลของเราในลำดับจากน้อยไปมาก :
<ก่อน> คลาส SortGrades { การแทรกโมฆะโมฆะสาธารณะแบบคงที่ (int [] numbersToSort) { int itemCount =numbersToSort.length; สำหรับ (ค่า int =1; ค่าเราเริ่มต้นด้วยการค้นหาว่ามีกี่รายการในอาร์เรย์อินพุตของเรา ซึ่งช่วยให้เราสร้างการวนซ้ำที่ผ่านทุกรายการในรายการของเรา เราเริ่มต้น for loop ซึ่งจะวนซ้ำจนกว่าเราจะจัดเรียงรายการของเรา
ภายใน for loop ของเรา เราได้ประกาศตัวแปรสองตัว:คีย์และตัวสุดท้าย
ตัวแปร "คีย์" Java ติดตามว่ารายการใดที่เรากำลังจัดเรียงอยู่ ตัวแปร “สุดท้าย” จะติดตามจำนวนรายการที่ต้องจัดเรียงทางด้านซ้ายของรายการ
โปรแกรมของเราจะเปรียบเทียบค่าของ “คีย์” กับแต่ละองค์ประกอบทางด้านซ้ายจนกว่าเราจะพบองค์ประกอบที่เล็กกว่า สิ่งนี้เกิดขึ้นใน Java “while” loop ของเรา
กำหนดฟังก์ชันหลัก
เมื่อเรารันโค้ดนี้ ไม่มีอะไรเกิดขึ้น นั่นเป็นเพราะเรายังไม่ได้กำหนดหน้าที่หลักของเรา มากำหนดฟังก์ชันหลักซึ่งกำหนดอาร์เรย์ int (อาร์เรย์ของตัวเลข) ฟังก์ชันหลักนี้ใช้ insertionSort() ฟังก์ชันที่เราได้ประกาศให้เรียงลำดับตัวเลขเหล่านั้น วางโค้ดนี้หลังจากประกาศวิธีการ insertionSort Java ของคุณ:
public static void main(String args[]) { int[] numbers ={ 8, 6, 3, 9 }; InsertionSort sortNumbers =ใหม่ InsertionSort (); sortNumbers.insertionSort (ตัวเลข); สตริง arrayToString =Arrays.toString (ตัวเลข); System.out.println("รายการที่เรียงลำดับ:" + arrayToString);} ในวิธีการหลักของเรา เราได้ประกาศรายการตัวเลขที่เราต้องการจัดเรียง เราได้สร้างตัวอย่าง InsertionSort() . ของเราแล้ว เมธอดที่เรียกว่า sortNumbers . เราใช้วิธีนี้เพื่อจัดเรียงรายการตัวเลขของเราตามลำดับจากน้อยไปมาก วิธีนี้จะเปลี่ยนค่าภายในอาร์เรย์ "ตัวเลข" ของเรา เรายังไม่ได้ประกาศอาร์เรย์แยกต่างหากสำหรับเก็บค่า
ต่อไป เราใช้ Arrays.toString() วิธีการแปลงอาร์เรย์ตัวเลขของเราเป็นสตริง เราพิมพ์รายการที่เรียงลำดับไปยังคอนโซล
ทบทวนความซับซ้อน
การเรียงลำดับการแทรกมีความซับซ้อนของตัวพิมพ์เฉลี่ย O(n^2) สิ่งนี้จะเกิดขึ้นเมื่อไม่มีการจัดเรียงองค์ประกอบ
ความซับซ้อนของเคสที่ดีที่สุดจะเกิดขึ้นหากมีการจัดเรียงอาร์เรย์ สิ่งนี้จะทำให้เกิดความซับซ้อนของเวลาของ O(n) นี่เป็นเพราะว่าวงในในการเรียงลำดับการแทรกจะไม่ทำงานเลยในกรณีนี้
ในกรณีที่เลวร้ายที่สุด การเรียงลำดับการแทรกจะดำเนินการที่ O(n^2) กรณีนี้จะเกิดขึ้นหากอาร์เรย์อยู่ในลำดับจากน้อยไปมากหรือมากไปหาน้อย และคุณต้องการจัดเรียงแบบผกผัน (เช่น จากมากไปหาน้อย) ซึ่งจะเกี่ยวข้องกับการเปรียบเทียบทุกองค์ประกอบกับองค์ประกอบอื่นๆ ทั้งหมด
บทสรุป
การเรียงลำดับการแทรกเป็นวิธีการจัดเรียงข้อมูลที่มีประสิทธิภาพ การเรียงลำดับการแทรกจะเปรียบเทียบค่าที่เริ่มต้นด้วยค่าที่สองในรายการ หากค่านี้มากกว่าค่าทางด้านซ้าย รายการของเราจะไม่เปลี่ยนแปลง มิฉะนั้น ค่าจะถูกย้ายจนกว่ารายการทางด้านซ้ายจะน้อยกว่าค่านั้น
ตอนนี้คุณพร้อมที่จะเริ่มเขียนอัลกอริทึมการเรียงลำดับการแทรกของคุณเองใน Java แล้ว! หากคุณกำลังมองหาแหล่งข้อมูลการเรียนรู้ Java เพิ่มเติม โปรดดูคู่มือ How to Learn Java
