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

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

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

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

• อินพุต: อาร์เรย์ A ที่มีองค์ประกอบตัวเลขที่ไม่เรียงลำดับ: A[0,1, n, n-2...]
• เอาต์พุต: อาร์เรย์ที่มีตัวเลขเดียวกันแต่เรียงเต็ม โดยทั่วไปจะเรียกว่า B: B[0]B[1]...B[n-1]

มีหลายวิธีในการใช้การเรียงลำดับการแทรก ซึ่งเป็นวิธีที่ได้รับความนิยมมากที่สุด:

• การเรียงลำดับตัวเลข (ลำดับที่เพิ่มขึ้น): [1, 2, 3, 4, 5]
• การเรียงลำดับตัวเลข (ลำดับลดลง): [5, 4, 3, 2, 1]
• การเรียงลำดับตามตัวอักษร: [a, b, c, d]

หมายเหตุ:หากคุณมีอาร์เรย์ว่างหรือซิงเกิลตัน จะถือว่าจัดเรียงตามค่าเริ่มต้น

ทำความเข้าใจกับทฤษฎีการเรียงลำดับการแทรก

ก่อนที่จะสำรวจโค้ดที่อยู่เบื้องหลังการเรียงลำดับการแทรก เราจะแบ่งอัลกอริทึมโดยใช้ภาษาที่ไม่ใช่ทางเทคนิค เนื่องจากเราจะแสดงโค้ดสำหรับการเรียงลำดับจากน้อยไปมาก จึงควรอธิบายอัลกอริทึมทีละขั้นตอนในโพสต์นี้ ขั้นตอนที่ 1.วนซ้ำระหว่างarr[1]และarr[n]โดยที่nค่าตัวเลขมักจะน้อยกว่า 10 ขั้นตอนที่ 2.เปรียบเทียบองค์ประกอบที่คุณเลือก (เรียกว่าkey) กับตัวเลขก่อนหน้าในลำดับโดยใช้sort()เมธอด ขั้นตอนที่ 3หากองค์ประกอบทั้งหมดมีขนาดเล็กกว่าองค์ประกอบที่ตามมา ให้ทำการเปรียบเทียบซ้ำจนกว่าคุณจะพบค่าที่มากกว่า ขั้นตอนที่ 4สลับค่าที่มากกว่าค่าที่มากกว่าค่าที่เล็กกว่าหนึ่งตำแหน่งเพื่อสร้างลำดับที่สั่ง ขั้นตอนที่ 5ทำซ้ำขั้นตอนจนกว่าคุณจะได้สตริงอักขระที่เรียงลำดับ

การเรียงลำดับอาร์เรย์ดั้งเดิม

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

1. ประกาศอาร์เรย์สำหรับการเรียงลำดับ

ในการเริ่มต้น เรามาสร้างสตริงของค่าที่เราจะแสดงในภายหลังโดยใช้ Java หากต้องการใช้การเรียงลำดับการแทรก คุณต้องสร้างอาร์เรย์ สำหรับสิ่งนั้นให้ใช้int[]

int[] arrayA = {10, 14, 20, 30};

2. ใช้ sort_arr เพื่อใช้อัลกอริทึม

วิธีการ sort_arr เป็นวิธีหนึ่งที่ใช้กันทั่วไปในการเรียงลำดับการแทรก ในทางปฏิบัติดูเหมือนว่า:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. สร้างลูปและตัววนซ้ำ

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

for(int i=0; i< sort_arr.length; ++i){

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

        int j = i;

4. การสร้าง "ลูป while"

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

• ค่าที่กำหนดให้กับ j จะต้องมากกว่า 0
• ค่าที่กำหนดj-1จะต้องมากกว่าjดัชนี

ทันทีที่เงื่อนไขทั้งสองในลูป while เป็นจริง ค่าคีย์ของอาร์เรย์จะเท่ากับjดัชนี

5. การเรียงลำดับอาร์เรย์

หลังจากที่คุณตั้งค่าลูป while ค่าjและj-1จะถูกสลับจนกว่าเงื่อนไขใดเงื่อนไขหนึ่งหรือทั้งสองเงื่อนไขในลูป while จะล้มเหลว ในทำนองเดียวกัน การเรียงลำดับจะถูกทำซ้ำสำหรับทุกค่าใน for loop จนกว่าเงื่อนไข for-loop จะล้มเหลวเช่นกัน ต่อไปนี้คือวิธีการทำงานของการเรียงลำดับการแทรกในทางปฏิบัติ:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

การเรียงลำดับ ArrayList

แม้ว่าการทำความเข้าใจคณิตศาสตร์เบื้องหลังการเรียงลำดับการแทรกจะมีความสำคัญ แต่เมื่อพูดถึงการพัฒนาซอฟต์แวร์ในชีวิตจริง คุณจะต้องเรียงลำดับ ArrayLists มากกว่าลำดับในอาร์เรย์ดั้งเดิม นี่คือคำแนะนำทีละขั้นตอนในการเรียงลำดับ ArrayList:

1. สร้างคลาสใหม่Elementสำหรับรายการที่เป็นของคอลเลกชัน

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. ภายในคอลเลกชัน มีcompareTo()วิธีการ - เราจะใช้สิ่งนี้เพื่อเปรียบเทียบรหัสของสององค์ประกอบ

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. ใช้อัลกอริทึมและสร้างลูปเพื่อจัดเรียงวัตถุใน an ArrayListแทนการเปรียบเทียบ

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. คุณสามารถเพิ่มองค์ประกอบอื่นๆ ลงไปได้ArrayListเช่นกัน ดังที่แสดงด้านล่าง:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. ถึงเวลาจัดเรียง:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

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

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

ปัญหาการฝึกเรียงลำดับการแทรก

ตอนนี้คุณคุ้นเคยกับอัลกอริธึมการเรียงลำดับนี้แล้ว ก็ถึงเวลาทดสอบทักษะทางทฤษฎีและปฏิบัติของคุณ แบบทดสอบทฤษฎี #1 คุณได้รับอาร์เรย์ [1, 4, 6, 8] และเพิ่มองค์ประกอบใหม่ n = 7 เข้าไป คุณต้องทำการเปรียบเทียบจำนวนเท่าใดจึงจะเรียงลำดับตัวเลขได้ ระบุค่าสุดท้ายของดัชนี n ในอาร์เรย์ แบบทดสอบทฤษฎี #2 ในการสัมภาษณ์งาน หัวหน้าทีมขอให้คุณพิสูจน์ว่าการแทรกการจัดเรียงเป็นวิธีที่ไม่มีประสิทธิภาพ เมื่อกำหนดสตริงตัวเลขเป็น [0, 3, 6, 8, 9] ลำดับของลำดับอินพุตของคุณควรเป็นอย่างไรเพื่อเพิ่มเวลาทำงานที่จำเป็นสำหรับการเรียงลำดับให้สูงสุด โจทย์ปัญหา เรียงลำดับอาร์เรย์ [0, 1, 4, 5, 2, 3, 7, 9, 8] จากน้อยไปหามากโดยใช้การเรียงลำดับการแทรกสำหรับ Java

บทสรุป

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