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

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

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

บทสรุป

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